# 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?

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

• one approach involves matrices – J. W. Tanner Jan 24 '20 at 14:37
• I am not quite sure I understand. Are you trying to get a standard "homogeneous recurrence relation with constant coefficients" question and accepted/upvoted answer, so that we can all use it to mark the endless particular questions as duplicates? – almagest Jan 24 '20 at 14:39
• @almagest That is the purpose of faq's. See the links at the end. I did a decent search and could not find such a question, but a lot of specific cases in (recurrence-relations)'s frequent tab, so decided to make this. – Simply Beautiful Art Jan 24 '20 at 14:41
• I would remove the ill defined "If a closed form cannot be explicitly achieved", for being false for a moderate definition of "closed form" and for the question that follows being useful regardless of its truth value. – OscarRascal Jan 24 '20 at 14:59
• You can use generating functions. – Math1000 Jan 24 '20 at 15:15

# 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.

1. 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$$.

2. 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.