Solve homogenous, constant coefficient and linear recurrence relations

Recurrence Relations

Recurrence relations, often known as recurrence equations or difference equations, are equations that express each term of a sequence in terms of its predecessors.
Homogeneous, constant coefficient, and linear recurrence relations are a specific type of recurrence relations that follow certain rules.

Solving Homogeneous Recurrence Relations

Homogeneous recurrent relations have the property that the value of each term can be expressed as a linear combination of its previous terms without an additional constant.
Write the recurrence relationship in the form Un = aUn-1 + bUn-2.
If the sequence starts with U0 and U1, attempt a solution of the form Un = rn.
Replace Un, Un-1 and Un-2 in the given relationship with rn, rn-1 and rn-2 respectively.
The roots r of the resulting quadratic equation are called the characteristic roots of the homogeneous recurrence relation.
If there are two distinct roots (r1 and r2), the solution is Un = Ar1^n + Br2^n where A and B are constants determined by the initial conditions.
If there are only two repeating roots (r and r), the solution is Un = (An + B) r^n where A and B are constants determined by the initial conditions.

Solving Constant Coefficient Recurrence Relations

In a constant coefficient recurrence relation, the coefficients (the multiples of the earlier terms) stay the same. These are often written as Un = aUn-1 + bUn-2 where a and b are constants.
With constant coefficients, the techniques to find the solution are the same as the steps described for homogeneous recurrence relations.

Solving Linear Recurrence Relations

The term linear in linear recurrence relations refers to the fact that each term of the sequence is a linear function of its preceding terms.
Linear recurrence relations can be solved using techniques of generating functions or characteristic roots similar to the methods laid out for homogeneous recurrence relations.
If the recurrence relationship is non-homogeneous, it can still be solved by first obtaining a solution to the corresponding homogeneous relationship and then obtaining a particular solution to the non-homogeneous relationship. These can then be combined to obtain the general solution.
A particular solution can usually be guessed based on the form of the non-homogeneous term.

Key Concepts to Remember

Initial conditions are a key aspect of solving recurrence relations, both in determining the form of the solution and the exact values of the constants involved.
Always consider the full sequence, not just the initial terms or the difference equation itself, when approaching these problems.
The solutions to recurrence relations sometimes fall into different categories, depending on the nature of the characteristic roots. The roots could be real and distinct, real and equal, or complex.