Linear homogeneous recurrence relations with constant coefficients and finite order

This note is about a family of recurrence relations (some people call them also difference equations) that are the easiest to solve. More general cases can also be solved, like some non-homogeneous, some cases of non-constant coefficients, etc. This is only a minimum that is good to have in your toolbox.

Consider a recurrence like

$x_{n+d}=a_{d-1}x_{n+d-1}+a_{d-2}x_{n+d-2}+…+a_1x_{x+1}+a_0x_n$

where $a_0,a_1,…,a_{d-1}$ and $d$ do not depend on $n$. The value $d$ is called the order of the difference equation (or recurrence). It is how far back into the history of the sequence one needs to look, for the recurrence equation to give the next term. The equation is supposed to be satisfied for all $n\geq0$. If someone gives us the values of the first $d$ terms $x_0,x_1,…,x_{d-1}$ of the sequence, then the sequence $x_n$ is uniquely determined.

The name

• Linear: In the equation, there are only $x_k$ multiplied by some constants and added.
• Homogeneous: There is no extra term, like $+n^2$ in $x_{n+2}=3x_{n+1}+n^2$.
• Constant coefficients: Self-explanatory. The coefficients in front of the $a_k$ are constant.
• Finite order: The $d$, the (maximum) amount of history that the equation needs to compute the next term stays the same. Compare the equation above, with $x_{n}=x_{n-1}+x_{n-2}+…+x_1+x_0$. In this one, to compute $x_n$ we need to look back at all previous terms. So, when $n$ increases, so does the amount of terms that the equation requires to compute the next term. Note: We are seeing order as a property of the equation. In this example, it is possible to transform the family of equations into a new one that does have finite order, by subtracting $x_{n}=x_{n-1}+x_{n-2}+…+x_1+x_0$ from $x_{n+1}=x_{n}+x_{n-1}+…+x_1+x_0$.

The recipe for the solution

The polynomial

$t^d=a_{d-1}t^{d-1}+a_{d-2}t^{d-2}+…+a_1t+a_0$

is called its characteristic polynomial. The concept of characteristic polynomial will appear also in linear algebra, associated to linear transformations. They are called the same name because the one here is a particular case of the other.

Assume that

$r_1, r_2,…,r_k$

are the different roots of the characteristic polynomial (complex in general) and that they have multiplicities

$m_1,m_2,…,m_k$, respectively. Note, that in particular $m_1+m_2+…+m_k=d$.

So, the general solution of the recurrence relation is

$x_n=(c_{1,0}+c_{1,1}n+…+c_{1,m_1-1}n^{m_1-1})r_1^n+(c_{2,0}+c_{2,1}n+…+c_{2,m_2-1}n^{m_2-1})r_2^n+…+(c_{k,0}+c_{k,1}n+…+c_{k,m_k-1}n^{m_k-1})r_k^n$

An easy way to remember this is that we take each root $r_i$, raise it to the power $n$ and multiply it by a polynomial $c_{i,0}+c_{i,1}n+…+c_{i,m_i-1}n^{m_i-1}$ of degree at most $m_i-1$ (or less than $m_i$).

Here, all $c_{i,j}$ are some arbitrary constants not depending on $n$.

If someone gives us $d$ consecutive particular values of the sequence, for example $x_0,x_1,…,x_{d-1}$, then we can determine the specific values of the constants $c_{i,j}$.

When you get more comfortable with linear algebra it will be a good exercise to prove that in fact the solution above is the general solution. For the moment, do practice some linear recurrences to make sure you remember how it goes.

Exercises

1. [Fibonacci] Find an algebraic expression for $F_n$ in terms of $n$, if $F_{n+2}=F_{n+1}+F_{n}$ for all $n\in\mathbb{Z}$. Note: The solution will depend on two arbitrary constants. Then impose that $F_0=1$ and $F_1=1$ to get what is known as Binet’s formula for the Fibonacci sequence.
2. Find all solutions of $S_n=2S_{n-1}-S_n$.
3. Find all solutions of $D_{n}=4D_{n-1}-D_{n-2}$.
4. If $X_{n}=5X_{n-1}-6X_{n-2}$, show that $|X_n/3^n|$ is bounded. In other words, that there is some constant $M$ such that for all $n$ we have $|X_n/3^n|\leq M$. Hint: First compute the solution of the recurrence and then divide it by $3^n$.

A little taste of why the general solution looks like that

You can completely ignore this part for the moment.

Let $S$ be the function that takes in a sequence, and returns the same sequence shifted to the right. This is, $Sx_n=x_{n+1}$. This is called the right-shift operator. We will denote $S^k$ to applying the right shift $k$ times. In other words $S^kx_n=x_{n+k}$

So, we can re-write the recurrence relation as

$(S^d-a_{d-1}S^{d-1}-a_{d-2}S^{d-2}-…-a_1S-a_0)x_n=0$

Note that, in parentheses, what we have is the characteristic polynomial evaluated on the operator $S$.

The rest I will do with a particular example, to not overwhelm you with the notation.

Let’s take the recurrence

$X_{n+2}=3X_{n+1}-X_{n}$

We can write it as

$(S^2-3S+2)x_n=0$

We can factor the characteristic polynomial completely (going to complex numbers if needed) as $t^2-3t+2=(t-1)(t-2)$.

So, the recurrence becomes

$(S-1)(S-2)x_n=0$

Now look at this. A sequence like $y_n=C_22^n$, is “killed” by the operator $S-2$. In fact,

$(S-2)y_n=Sy_n-2y_n=y_{n+1}-2y_n=C2^{n+1}-2C2^n=0$

Note that $y_n$ would also be killed by $(S-1)(S-2)$, since already the factor $S-2$ makes it zero.

Similarly, the sequence $z_n=C_11^n$ is killed by the operator $S-1$. Check it. Therefore, $z_n$ is also killed by $(S-1)(S-2)$, since this operator is the same as $(S-1)(S-2)=S^2-3S+2=(S-2)(S-1)$ and when we apply $(S-2)(S-1)z_n$ already the $(S-1)z_n$ is becoming the zero sequence.

Ok, so the sequence $x_n=C_11^n+C_22^n=y_n+z_n$ satisfies the recurrence relation too, since

$(S^2-3S+2)x_n=(S-1)(S-2)y_n+(S-2)(S-1)z_n=0$

Proving that $x_n=C_11^n+C_22^n=y_n+z_n$ are in fact all solutions of $X_{n+2}=3X_{n+1}-2X_n$ is done with a bit of linear algebra. It turns out that we can determine that the dimension of the space of solutions of the linear recurrence has dimension $d$ (the order of the recurrence) ($d=2$ in the example). This, together with checking that the solutions $x_n=C_11^n+C_22^n$ also generate a space of the same dimension, is what ultimately proves that we got them all.

Note: We can use the example to see that we indeed got all solutions. Note that if $x_n$ is an arbitrary solution of the recurrence, then there are $C_1, C_2$ such that $C_11^0+C_22^0=x_0$ and $C_11^1+C_22^1=x_1$. Then, because the recurrence is linear, and $C_11^n+C_22^n$ is a solution, we get that $a_n=x_n-C_11^n-C_22^n$ is also a solution. However, $a_0=a_1=0$. An application of induction shows that for all $n$ we have $a_n=0$. Therefore, $x_n=C_11^n+C_22^n$. Note that the crucial point was that we managed to match whichever values were the initial values $x_0$ and $x_1$.

By the way, the polynomials that appear in the general solution, when roots of the characteristic polynomial have multiplicity is of course because they are killed by the corresponding powers of the shift operator. For example, check that $(C_1+C_2n)2^n$ is killed by $(S-2)^2$.