How to solve homogeneous linear recurrence relations with constant coefficients?

Consider a sequence $(a_n)_{n\in\mathbb N}$ defined by $k$ initial values $(a_1,\dots,a_k)$ and

$$a_{n+k}=c_{k-1}a_{n+k-1}+\dots+c_0a_n$$

for all $n\in\mathbb N$.

What are some ways to get closed forms for $a_n$? What are some ways of rewriting $a_n$ that allows it to be computed without going through all previous values?

For example, we have Binet's formula:

$$F_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}$$

Furthermore, what about simultaneously defined linear recurrences? For example:

$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$

How can these be solved?

See also: Wikipedia: Recurrence relations.

This is being repurposed in an effort to cut down on duplicates; see here:

• Coping with abstract duplicate questions

• List of abstract duplicates

Characteristic/Auxiliary Polynomials

The basic solution

1. Suppose that $\alpha$ is a root of the associated polynomial $$x^k=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_0\quad(1)$$ Then it is also true that $$\alpha^{n+k}=c_1\alpha^{n+k-1}+\dots+c_0\alpha^n$$ So $a_n=\alpha^n$ satisfies the recurrence relation (but probably not the initial conditions).

2. Since the relation is linear, if $\alpha_1,\alpha_2,\dots,\alpha_k$ are the roots of the associated polynomial, then $$a_n=A_1\alpha_1^n+\dots+A_k\alpha_k^n$$ also satisfies the recurrence relation. Provided all $k$ roots are distinct, we can then use the $k$ initial conditions to solve for $A_1,\dots,A_k$.

3. Suppose that $\alpha$ is a repeated root. Then $\alpha$ is also a root of the derivative and so we have $$kx^{k-1}=c_{k-1}(k-1)x^{k-2}+\dots+c_0\quad(2)$$ Taking $nx^n(1)+x^{n+1}(2)$ we get $$(n+k)x^{n+k}=c_{k-1}(n+k-1)x^{n+k-1}+\dots+c_0nx^n$$ and so $a_n=n\alpha^n$ is satisfies the recurrence relation.

4. Similarly, we find that if $\alpha$ is a root of order $h$ (so that $(x-\alpha)^h$ divides the polynomial, then $a_n=\alpha^n,n\alpha^n,n^2\alpha^n,\dots,n^{h-1}\alpha^n$ all satisfy the recurrence relation.

5. So in all cases the associated polynomial gives us $k$ solutions to the recurrence relation. We then take a suitable linear combination of those solutions to satisfy the initial conditions.

Additional points

6. If often happens that all but one of the roots $\alpha$ of the polynomial satisfy $|\alpha|<1$ which means that their contribution to $a_n$ is negligible except possibly for small $n$. Since the $a_n$ are usually integers, this means we can often express the solution as $\lfloor A\alpha^n\rfloor$ or $\lceil A\alpha^n\rceil$ (where $\alpha$ is the root with $|\alpha|>1$.

7. We sometimes get simultaneous linear recurrences like the two in the question $$a_{n+1}=2a_n+b_n,b_{n+1}=a_n+2b_n$$ In this case we can eliminate all but one of the sequences, in a similar way to solving ordinary simultaneous equations. In this case we have $b_n=a_{n+1}-2a_n$. Substituting in the other relation; $a_{n+2}-2a_{n+1}=a_n+2a_{n+1}-4a_n$

Matrices

Such recurrences can be computed using matrices. Let $\mathbf a_n=(a_{n+k-1},\dots,a_n)^\intercal$. We can then easily see that the recurrence relation can be rewritten as

$$\mathbf a_{n+1}=C\mathbf a_n\text{ where }C=\begin{bmatrix}c_{k-1}&c_{k-2}&\cdots&c_1&c_0\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}=\begin{bmatrix}\mathbf c\\\mathbf e_0\\\mathbf e_1\\\vdots\\\mathbf e_{k-1}\end{bmatrix}$$

where $\mathbf e_i$ has a $1$ at the $i$th entry and $0$ everywhere else. See also: Companion matrix.

Intuitively we're computing the next term (top row), and then setting each entry as the one above it (a rotation of the values in $\mathbf a_n$ per se).

From this we can easily solve the recurrence, as it now becomes:

$$\mathbf a_n=C^n\mathbf a_0$$

and so the problem reduces to raising $C$ to a power. As it is the case that $C$ is diagonalizable, with eigenvalues given by the roots of the characteristic equation, a closed form can then be found. Even if the roots are not nice to compute, or if one wishes to avoid non-integers for an integer sequence, this can still be computed using exponentiation by squaring.

This also easily generalizes to simultaneously defined sequences. Consider the example:

$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$

Let $\mathbf w_n=(a_n,b_n)^\intercal$. We can then rewrite this as

$$\mathbf w_{n+1}=C\mathbf w_n\text{ where }C=\begin{bmatrix}2&1\\1&2\end{bmatrix}$$

and hence

$$\mathbf w_n=C^n\mathbf w_0$$

To show how this gives an explicit solution, we may diagonalize $C$ as

$$C=VDV^{-1}\\\text{where }D=\begin{bmatrix}1&0\\0&3\end{bmatrix},~V=\begin{bmatrix}-1&1\\1&1\end{bmatrix},~V^{-1}=\frac12V$$

and hence

$$\mathbf w_n=V\begin{bmatrix}1&0\\0&3^n\end{bmatrix}V^{-1}\mathbf w_0=\frac12\begin{bmatrix}(a_0+b_0)3^n+(a_0-b_0)\\(a_0+b_0)3^n-(a_0-b_0)\end{bmatrix}$$

which strongly suggests this specific problem can be solved by observing the behavior of $V^{-1}\mathbf w_n$ i.e. $a_n-b_n$ and $a_n+b_n$.

Generating functions / Z-transforms

Generating functions (unilateral Z-transforms) can be used to transform the recurrence into a formal power series by defining:

$$G=\sum_{n=0}^\infty a_nx^n$$

We can then rearrange this to get

$$G=\sum_{n=0}^{k-1}a_nx^n+G\sum_{n=1}^kc_{k-n}x^{n-1}$$

Solving for $G$ then gives a rational function in $x$. By factoring the denominator (which equates to solving the characteristic equation), applying partial fractions, and using the geometric series or Newton's generalized binomial theorem, the general term in the expansion of $G$ can be computed. Alternatively, by using Taylor's series, we know that

$$a_n=\frac{G^{(n)}(0)}{n!}$$

which can be computed directly by differentiating repeatedly, using Leibniz's rule for example.

Example:

The Fibonacci sequence can be solved this way. Recall that $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$. Now let us take

$$G=\sum_{n=0}^\infty F_nx^n$$

By algebraic manipulation,

$$G=x+(x+x^2)G$$

$$G=\frac x{1-x-x^2}$$

For multiple simultaneously defined sequences, this simply amounts to multiple generating functions, which when solving amounts interestingly to solving a system of equations of functions. After that the rest is the same as above.