An order d linear homogeneous recurrence relation with constant coefficients is an equation of the form:

$$ a_n = c_1a_{n-1} + c_2a_{n-2} + \dots + c_da_{n-d} \\ \therefore a_n - c_1a_{n-1} - c_2a_{n-2} - \dots - c_da_{n-d} \\ \label{eq:rl1} $$

A sequence which satisfies a relation of this form is called a linear recursive sequence. The initial conditions (\(a_0,\dots,a_{d-1}\)) can be taken to be any values but thereafter the linear recurrence relation determines the sequence uniquely. There are therefore an infinite many number of sequences which will satisfy the linear recurrence relation and are termed solutions.

Solutions to linear recurrence relations may be derived by substituting \(a_n=r^n\) into equation \eqref{eq:rl1}:

$$ a_n - c_1a_{n-1} - c_2a_{n-2} - \dots - c_da_{n-d} = r^n - c_1r^{n-1} - c_2r^{n-2} - \dots - c_dr^{n-d} = 0\\ \label{eq:rl2} $$

Therefore, \(a_n=r^n\) is a solution to the linear recurrence relation if r is a root of:

$$ r^n - c_1r^{n-1} - c_2r^{n-2} - \dots - c_dr^{n-d} = r^{n-d}\left(r^d - c_1r^{d-1} - c_2r^{d-2} - \dots - c_d\right) = 0\\ \label{eq:rl3} $$

The above equation is termed the characteristic equation and may be solved for the d roots (\(\lambda_1,\dots,\lambda_2\)). There are therfore d solutions (\(\lambda_1^n,\dots,\lambda_d^n\)) to the linear recurrence relation (not including the trivial case \(r=0\)). Each solution may generate a unique sequence but all will satisfy the original linear recurrence relation. If the roots are real and distinct, the general solution of a linear recurrence relation is a linear combination of the d solutins:

$$ a_n = b_1\lambda_1^n + b_2\lambda_2^n + b_3\lambda_3^n + \dots + b_d\lambda_d^n\\ \label{eq:rl4} $$

If d consecutive initial values of the linear recurrence relation are known, a unique solution can be obtained by evaluating the d arbitary constants (\(b_1,\dots,b_n\)). The sequence generated by this equation will match the sequence generated by the linear recurrence relation exactly.

If the sequence defined by the linear recurrence relation approaches zero as \(n \rightarrow \infty\), the sequence is defined as stable. The condition that \(a_n \rightarrow 0\) as \(n \rightarrow \infty\) is equivalent to \(|\lambda_i| < 1\) (since \(\lambda_i^n \rightarrow 0\) as \(n \rightarrow \infty\) if \(|\lambda_i| < 1\)).

Example

Find the general solution to the linear recurrence relation:

$$ a_n = 5a_{n-1} - 6a_{n-2} \\ \label{eq:rl5} $$

The characteristic equation may therfore be written as:

$$ r^2 - 5r + 6 = (x-2)(x-3) = 0 \\ \label{eq:rl6} $$

Therefore, \(\lambda_1 = 2\) and \(\lambda_2 = 3\). The general solution may be written as:

$$ a_n = b_12^n + b_23^n\\ \label{eq:rl7} $$

If the initial values of the linear recurrence relation are defined as \(a_0 = 9\) and \(a_1 = 20\), the constants \(b_1\) and \(b_2\) may be determined:

$$ a_0 = b_12^0 + b_23^0 = b_1 + b_2 = 9 \\ a_1 = b_12^1 + b_23^1 = 2b_1 + 3b_2 = 20 \\ \label{eq:rl8} $$

Solving the system of equations in two unknowns:

$$ b_1 = 7 \\ b_2 = 2 \\ \label{eq:rl9} $$

Therefore, the particular solution is:

$$ a_n = 7(2^n) + 2(3^n) \\ \label{eq:rl10} $$

Note that, since \(|\lambda_1| > 1\) (and also since \(|\lambda_2| > 1\)) the linear recurrence relation is not stable.