Section5.2Linear recurrence relations of order \(k\)
In this section by a sequence we mean an ordered list
\begin{equation*}
\halmaz{a_n}_{n=0}^{\infty}, a_n\in S
\end{equation*}
for some set \(S\text{.}\) For example
\begin{equation*}
1,2,4,8,16,32,64,\ldots
\end{equation*}
is a sequence containing non-negative powers of 2.
Definition5.2.1
A sequence \(\halmaz{a_n}_{n=0}^{\infty}\) is said to satisfy a linear recurrence relation of order \(k\) if
\begin{equation*}
a_n=c_{n-1}a_{n-1}+c_{n-2}a_{n-2}+\ldots+c_{n-k}a_{n-k}+b_n, c_{n-k}\neq 0, n\geq k\text{,}
\end{equation*}
where \(c_{n-1},\ldots,c_{n-k},b_n\) are some constants. If \(b_n=0\text{,}\) then we say that the sequence satisfies a homogeneous linear recurrence relation of order \(k\text{.}\) In case of a linear recurrence relation of order \(k\) the values of \(a_0,a_1,\ldots,a_{k-1}\) are called the initial values of the sequence.
For example the sequence appeared in case of Tower of Hanoi is a sequence of order 1:
\begin{align*}
T_0\amp =0,\\
T_n\amp =2T_{n-1}+1 \mbox{ for } n\geq 1\text{.}
\end{align*}
Theorem5.2.2
Let \(\halmaz{a_n}_{n=0}^{\infty}\) be a linear recurrence relation of order 1, that is,
\begin{equation*}
a_n=ua_{n-1}+v
\end{equation*}
for some constants \(u,v\text{.}\) If \(u=1\text{,}\) then
\begin{equation*}
a_n=a_0+nv\text{,}
\end{equation*}
otherwise
\begin{equation*}
a_n=u^na_0+\frac{u^n-1}{u-1}v\text{.}
\end{equation*}
Proof
If \(u=1\text{,}\) then the defining equation simplifies as follows
\begin{equation*}
a_n=a_{n-1}+v\text{.}
\end{equation*}
We prove the statement by induction. The initial value of the sequence is \(a_0\text{.}\) Using the above formula for \(a_n\) we obtain
\begin{align*}
a_1\amp =a_0+v,\\
a_2\amp =a_1+v=a_0+2v,\\
a_3\amp =a_2+v=a_0+3v\text{.}
\end{align*}
Hence the statement is clearly true for \(n=1,2\) and 3. Assume that the statement is true for \(n=k\text{,}\) that is,
\begin{equation*}
a_k=a_0+kv\text{.}
\end{equation*}
The statement for \(n=k+1\) is that \(a_{k+1}=a_0+(k+1)v\text{.}\) By the recurrence definition we have \(a_{k+1}=a_{k}+v\text{.}\) By induction we obtain that
\begin{equation*}
a_{k+1}=a_0+kv+v=a_0+(k+1)v\text{,}
\end{equation*}
which is the desired result for \(n=k+1\text{.}\)
Now assume that \(u\neq 1\text{.}\) We apply induction again. As in the previous case we compute the first few values of the sequence
\begin{align*}
a_1\amp =ua_0+v,\\
a_2\amp =ua_1+v=u^2a_0+uv+v,\\
a_3\amp =ua_2+v=u^3a_0+u^2v+uv+v\text{.}
\end{align*}
It follows that the statement is true if \(n=1,2,3\text{.}\) Assume that the statement is true for \(n=k\text{,}\) that is,
\begin{equation*}
a_k=u^ka_0+\frac{u^k-1}{u-1}v\text{.}
\end{equation*}
We need to show that the statement is true for \(n=k+1\text{,}\) so \(a_{k+1}=u^{k+1}a_0+\frac{u^{k+1}-1}{u-1}v\text{.}\) The recurrence definition yields that \(a_{k+1}=ua_{k}+v\text{.}\) Using the assumption one has that
\begin{equation*}
a_{k+1}=ua_{k}+v=u\cdot \left(u^ka_0+\frac{u^k-1}{u-1}v\right)+v=u^{k+1}a_0+u\frac{u^k-1}{u-1}v+v\text{.}
\end{equation*}
From the well-known identity \(u^m-1=(u-1)\cdot (u^{m-1}+u^{m-2}+\ldots+u+1)\) one gets that
\begin{equation*}
\frac{u^m-1}{u-1}=u^{m-1}+u^{m-2}+\ldots+u+1
\end{equation*}
for \(u\neq 1\text{.}\) So we have \(u\frac{u^k-1}{u-1}\cdot v+v=(u^k+u^{k-1}+\ldots+u)v+v=(u^k+u^{k-1}+\ldots+u+1)\cdot v\text{.}\) Finally we obtain that
\begin{equation*}
a_{k+1}=u^{k+1}a_0+(u^k+u^{k-1}+\ldots+u+1)v=u^{k+1}a_0+\frac{u^{k+1}-1}{u-1}v\text{,}
\end{equation*}
and the statement follows.
It is easy to compute an explicit formula for the sequence \(T_n\) related to the problem of Tower of Hanoi. Here \(T_n\) is defined as
\begin{align*}
T_0\amp =0,\\
T_n\amp =2T_{n-1}+1 \mbox{ for } n\geq 1\text{,}
\end{align*}
that is, \(u=2\) and \(v=1\text{.}\) The theorem implies that
\begin{equation*}
T_n=u^nT_0+\frac{u^n-1}{u-1}v=2^n\cdot 0+\frac{2^n-1}{2-1}\cdot 1=2^n-1\text{.}
\end{equation*}
Consider another example, let \(a_n\) be a sequence defined by
\begin{align*}
a_0\amp =3,\\
a_n\amp =2a_{n-1}+2 \mbox{ for } n\geq 1\text{.}
\end{align*}
We apply the theorem and we have
\begin{equation*}
a_n=2^n\cdot 3+\frac{2^n-1}{2-1}\cdot 2=2^n\cdot 3+2^{n+1}-2=5\cdot 2^n-2\text{.}
\end{equation*}
We have proved a theorem about linear recurrence relations of order 1, given such a recurrence we are able to provide an explicit formula. What about higher order linear recurrence relations? To make the presentation simpler we will consider homogeneous linear recurrence relations of order \(k\text{,}\) where \(k\geq 2\text{.}\) So we study the structure of the recurrence given by
\begin{equation}
a_n=c_{n-1}a_{n-1}+c_{n-2}a_{n-2}+\ldots+c_{n-k}a_{n-k}, c_{n-k}\neq 0, n\geq k\text{,}\label{hlr}\tag{5.2.1}
\end{equation}
where \(c_{n-1},\ldots,c_{n-k}\) are some constants.
Theorem5.2.3
Assume that \(U_n\) and \(V_n\) are sequences satisfying (5.2.1) and \(s,t\) are constants. The linear combination
\begin{equation*}
W_n=sU_n+tV_n
\end{equation*}
gives another solution of (5.2.1).
Proof
Since \(U_n\) and \(V_n\) satisfy (5.2.1) we have
\begin{align*}
U_n\amp =c_{n-1}U_{n-1}+c_{n-2}U_{n-2}+\ldots+c_{n-k}U_{n-k},\\
V_n\amp =c_{n-1}V_{n-1}+c_{n-2}V_{n-2}+\ldots+c_{n-k}V_{n-k}\text{.}
\end{align*}
Substituting these formulas into the definition of \(W_n\) we get
\begin{align*}
W_n=\amp s(c_{n-1}U_{n-1}+c_{n-2}U_{n-2}+\ldots+c_{n-k}U_{n-k})+\\
\amp t(c_{n-1}V_{n-1}+c_{n-2}V_{n-2}+\ldots+c_{n-k}V_{n-k})=\\
\amp c_{n-1}(sU_{n-1}+tV_{n-1})+c_{n-2}(sU_{n-2}+tV_{n-2})+\ldots+\\
\amp +c_{n-k}(sU_{n-k}+tV_{n-k})=\\
\amp c_{n-1}W_{n-1}+c_{n-2}W_{n-2}+\ldots+c_{n-k}W_{n-k}\text{.}
\end{align*}
It turned out that \(W_n\) is also a solution of (5.2.1).
The previous theorem suggests a strategy to determine explicit formula for higher order linear homogeneous recurrence relations. First we look for solutions of the concrete recurrence relation, then we consider linear combinations of them and we try to fix the constants in such a way that the initial values of the given sequence are the same as in case of the sequence obtained by linear combination. What kind of solutions should we look for? Here we need some numerical experiences. Consider the example
\begin{align*}
a_0\amp =2,\\
a_1\amp =2,\\
a_n\amp =2a_{n-1}+3a_{n-2}, n\geq 2\text{.}
\end{align*}
The above sequence is a homogeneous linear recurrence sequence of order \(2\text{.}\) We can easily compute the first few elements of the sequence, \(a_2=10, a_3=26, a_4=82\text{.}\) Let us consider the ratio of consecutive elements of the sequence.
|
|
|
|
| \(n\) |
\(\frac{a_n}{a_{n-1}}\) |
\(n\) |
\(\frac{a_n}{a_{n-1}}\) |
|
|
|
|
| 1 |
\(1\) |
5 |
\(\approx 2.951\) |
|
|
|
|
| 2 |
\(5\) |
6 |
\(\approx 3.017\) |
|
|
|
|
| 3 |
\(2.6\) |
7 |
\(\approx 2.995\) |
|
|
|
|
| 4 |
\(\approx 3.154\) |
8 |
\(\approx 3.002\) |
|
|
|
|
The ratios are very close to a constant, in this case very close to 3 for \(n\in\halmaz{4,5,6,7,8}\text{.}\) At the beginning of this chapter we studied sequences for which the ratio of consecutive elements is a constant, these are geometric progressions. Let us look for geometric progressions satisfying the same recurrence relation as \(a_n\text{.}\) If \(g_n\) is a sequence given by the formula
\begin{equation*}
g_n=rg_{n-1}\text{,}
\end{equation*}
where \(r\) is the common ratio of the sequence with initial value \(g_0\text{,}\) then we have that \(g_n=g_0r^n\text{.}\) That is, \(g_n\) is a geometric progression. Let us assume that for some initial value \(g_0\) and for some \(r\) the progression satisfies the same recurrence relation as \(a_n\text{.}\) Now we obtain
\begin{equation*}
g_n=2g_{n-1}+3g_{n-2}\text{.}
\end{equation*}
It follows that
\begin{equation*}
g_0r^n=2g_0r^{n-1}+3g_0r^{n-2}\text{.}
\end{equation*}
The constant zero progression is not useful for our purposes we assume that \(g_0\neq 0\) and \(r\neq 0\text{.}\) After dividing by \(g_0r^{n-2}\) we get
\begin{equation*}
r^2=2r+3\text{.}
\end{equation*}
If there is such a progression, then \(r\) is a root of the quadratic polynomial \(r^2-2r-3\text{.}\) One can determine the roots by the well-known formula, which is in our case
\begin{equation*}
\frac{2\pm\sqrt{4-4(-3)}}{2}\text{.}
\end{equation*}
That is, the roots are \(3\) and \(-1\text{.}\) We have two different solutions of the recurrence relation and Theorem 5.2.3 implies that linear combinations of these two solutions yield another solutions. Let us consider the sequence \(W_n=s3^n+t(-1)^n\text{.}\) We should fix \(s,t\) in such a way that
\begin{align*}
\amp W_0=a_0=2,\\
\amp W_1=a_1=2\text{.}
\end{align*}
We get a system of equations in two unknowns
\begin{align*}
W_0=2\amp \Rightarrow s\cdot 3^0+t\cdot (-1)^0=2,\\
W_1=2\amp \Rightarrow s\cdot 3^1+t\cdot (-1)^1=2\text{.}
\end{align*}
The first equation implies that \(t=2-s\text{.}\) The second equation can be written as \(3s+(2-s)(-1)=2\text{,}\) that is, \(4s=4\) and we get that \(s=1,t=1\text{.}\) Now we have a sequence \(W_n=3^n+(-1)^n\) which satisfies the appropriate recurrence relation and has the same initial values as \(a_n\text{.}\) Thus \(W_n=a_n\text{.}\) In this way we obtained an explicit formula for the recurrence sequence \(a_n\) given by
\begin{equation*}
3^n+(-1)^n\text{.}
\end{equation*}
We may try to apply the above method to determine an explicit formula for the famous Fibonacci sequence:
\begin{align*}
F_0\amp =0,\\
F_1\amp =1,\\
F_n\amp =F_{n-1}+F_{n-2}, n\geq 2\text{.}
\end{align*}
Let \(g_n\) be a geometric progression such that \(g_n=g_0r^n\) for some \(g_0\) and \(r\text{.}\) Assume that \(g_n\) satisfies the recurrence relation. It follows that
\begin{equation*}
r^2=r+1\text{.}
\end{equation*}
The two roots of this quadratic polynomial are
\begin{equation*}
\frac{1-\sqrt{5}}{2}\mbox{ and } \frac{1+\sqrt{5}}{2}\text{.}
\end{equation*}
Let \(W_n\) be a linear combination of the appropriate geometric progressions, that is,
\begin{equation*}
W_n=s\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n+t\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n\text{.}
\end{equation*}
It remains to find \(s\) and \(t\) for which
\begin{align*}
\amp W_0=F_0=0,\\
\amp W_1=F_1=1\text{.}
\end{align*}
The above equations imply that
\begin{align*}
s+t\amp =0\\
s\cdot \left(\frac{1-\sqrt{5}}{2}\right)+t\cdot \left(\frac{1+\sqrt{5}}{2}\right)\amp =1\text{.}
\end{align*}
We immediately get that \(t=-s\text{.}\) Therefore
\begin{equation*}
s\cdot \left(\frac{1-\sqrt{5}}{2}\right)-s\cdot \left(\frac{1+\sqrt{5}}{2}\right)=1\text{.}
\end{equation*}
The latter equation yields that \(s=\frac{-\sqrt{5}}{5}\text{,}\) so \(t=\frac{\sqrt{5}}{5}\text{.}\) The explicit formula in case of the Fibonacci sequence is
\begin{equation*}
F_n=\frac{-\sqrt{5}}{5}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n+\frac{\sqrt{5}}{5}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n\text{.}
\end{equation*}
Let us see if the previous argument works for homogeneous linear recurrence sequence of order greater than 2. We define \(a_n\) as
\begin{align*}
a_0\amp =5,\\
a_1\amp =-3,\\
a_2\amp =11,\\
a_n\amp =-a_{n-1}+4a_{n-2}+4a_{n-3}, n\geq 3\text{.}
\end{align*}
The sequence \(a_n\) is a homogeneous linear recurrence sequence of order 3, since \(a_n\) depends on the previous 3 elements of the sequence. We try to find a geometric progression \(g_n=g_0r^n\) satisfying the above recurrence
\begin{equation*}
g_0r^n=-g_0r^{n-1}+4g_0r^{n-2}+4g_0r^{n-3}\text{.}
\end{equation*}
Again we exclude the case \(g_0r=0\text{,}\) so we may simplify the equation by \(g_0r^{n-3}\text{.}\) So we obtain
\begin{equation*}
r^3+r^2-4r-4=0\text{.}
\end{equation*}
This time we have a cubic polynomial and finding the roots of a cubic is more difficult than determining the roots of a quadratic polynomial. We may try to find some special roots e.g. integral roots. To find integral roots we can rewrite the equation in the form
\begin{equation*}
r\cdot (r^2+r-4)=4\text{.}
\end{equation*}
If \(r\) is an integer, then the expression on the left-hand side is a multiple of two integers. The multiple of two integers is equal to 4, that is, we have only a few possibilities since \(r\) has to divide 4. That is \(r\in\halmaz{-4,-2,-1,1,2,4}\text{.}\) Evaluate the cubic polynomial at these values:
|
|
| \(r\) |
\(r^3+r^2-4r-4\) |
|
|
| -4 |
-36 |
|
|
| -2 |
0 |
|
|
| -1 |
0 |
|
|
| 1 |
-6 |
|
|
| 2 |
0 |
|
|
| 4 |
60 |
|
|
We are lucky, there are 3 integral roots: \(-2,-1\) and 2. It means by Theorem 5.2.3 that any linear combinations of the geometric progressions \((-2)^n, (-1)^n\) and \(2^n\) will satisfy the same recurrence relation as \(a_n\text{.}\) Now define \(W_n=s(-2)^n+t(-1)^n+u2^n\text{.}\) Our task is to fix \(s,t\) and \(u\) such that
\begin{align*}
\amp W_0=a_0=5,\\
\amp W_1=a_1=-3,\\
\amp W_2=a_2=11\text{.}
\end{align*}
These equations yield a system of equations in three unknowns.
\begin{align*}
s+t+u\amp =5\\
-2s-t+2u\amp =-3\\
4s+t+4u\amp =11\text{.}
\end{align*}
We can eliminate \(s\) and \(u\) using the first and the third equations. To do so we multiply the first equation by 4:
\begin{align*}
4s+4t+4u\amp =20\\
-2s-t+2u\amp =-3\\
4s+t+4u\amp =11\text{.}
\end{align*}
We subtract the third equation from the first one and we get
\begin{equation*}
3t=9\text{,}
\end{equation*}
that is, \(t=3\text{.}\) The system of equations can be simplified now:
\begin{align*}
s+u\amp =2\\
-2s+2u\amp =0\text{.}
\end{align*}
The second equation implies that \(s=u\text{,}\) so from the first equation we have that \(s=u=1\text{.}\) The explicit formula for the sequence \(a_n\) is
\begin{equation*}
(-2)^n+3\cdot (-1)^n+2^n\text{.}
\end{equation*}
We remark that the previous argument does not work if we have a root with multiplicity greater than 1. Without providing the details of the theory we note that it is also possible to handle such cases. For example assume that a linear recurrence of order 2 is given and the corresponding quadratic polynomial has a double root \(r\text{.}\) We have that \(r^n\) and \(nr^n\) are solutions of the same recurrence. In general, if we have a linear recurrence of order \(k\) and the corresponding polynomial has a root \(r\) with multiplicity \(m\text{,}\) then
\begin{equation*}
r^n, nr^n,\ldots n^{m-1}r^n
\end{equation*}
are solutions of the same recurrence. Let us consider an example.
\begin{align*}
u_0\amp =4,\\
u_1\amp =-1,\\
u_2\amp =-1,\\
u_3\amp =-43,\\
u_n\amp =5u_{n-1}-6u_{n-2}-4u_{n-3}+8u_{n-4}, n\geq 4\text{.}
\end{align*}
The corresponding quartic polynomial \(r^4-5r^3+6r^2+4r-8\) can be written as \((r+1)(r-2)^3\text{,}\) that is, \(-1\) is a simple root and 2 is a root with multiplicity 3. Therefore we define \(W_n\) as
\begin{equation*}
s\cdot (-1)^n+t\cdot 2^n+xn\cdot 2^n+yn^2\cdot 2^n\text{.}
\end{equation*}
Then we obtain four equations in four unknowns
\begin{align*}
s+t\amp =4\\
-s+2t+2x+2y\amp =-1\\
s+4t+8x+16y\amp =-1\\
-s+8t+24x+72y\amp =-43\text{.}
\end{align*}
We get that \(s=4-t\text{,}\) hence
\begin{align*}
3t+2x+2y\amp =3\\
3t+8x+16y\amp =-5\\
9t+24x+72y\amp =-39\text{.}
\end{align*}
Using the first equation we can eliminate \(t\) from the second and the third equations.
\begin{align*}
6x+14y\amp =-8\\
18x+66y\amp =-48\text{.}
\end{align*}
The above system has the solution \(x=1, y=-1\text{.}\) We get that \(t=1\) and \(s=3\text{.}\) Thus
\begin{equation*}
u_n=3\cdot (-1)^n+2^n+n\cdot 2^n-n^2\cdot 2^n\text{.}
\end{equation*}
As an application we deal with an inverse problem, let us be given the sequence
\begin{equation*}
u_n=\left(\frac{3-\sqrt{33}}{2}\right)^n+\left(\frac{3+\sqrt{33}}{2}\right)^n, n\geq 0\text{.}
\end{equation*}
Our statement is that \(u_n\) is an integer sequence and 3 divides \(u_n\) for \(n\geq 1\text{.}\) This statement can be proved by induction (Exercise 3.1.12), but now we apply the theory of linear recurrence sequences. We are given an explicit formula and we would like to determine a linear recurrence sequence which has the same closed-form solution. It is easy to see that \(u_0=2\) and \(u_1=3\text{.}\) If we have an appropriate recurrence, then \(\frac{3-\sqrt{33}}{2}\) and \(\frac{3+\sqrt{33}}{2}\) are roots of some quadratic polynomial:
\begin{equation*}
\left(r-\frac{3-\sqrt{33}}{2}\right)\cdot \left(r-\frac{3+\sqrt{33}}{2}\right)=r^2-3r-6\text{.}
\end{equation*}
From this polynomial we have the following recurrence relation \(u_n=3u_{n-1}+6u_{n-2}\text{.}\) That is, we have a recurrence sequence
\begin{align*}
u_0\amp =2,\\
u_1\amp =3,\\
u_n\amp =3u_{n-1}+6u_{n-2}=3(u_{n-1}+2u_{n-2})\text{.}
\end{align*}
Since \(u_0\) and \(u_1\) are integers and \(u_{n-1},u_{n-2}\) have integral coefficients in the recurrence relation, the sequence \(u_n\) is an integral sequence. It is clear that \(u_1=3\) is divisible by 3 and similarly \(u_n=3(u_{n-1}+2u_{n-2})\) is a multiple of 3.
Exercise5.2.4
Find the shortest sequence of moves that transfers a tower of 4 disks from peg \(A\) to peg \(C\text{.}\)
Exercise5.2.5
Find a closed-form formula for the following sequence defined by:
\begin{equation*}
a_n=7a_{n-1}-10a_{n-2}\mbox{ for } n\geq 2\mbox{ and } a_0=0,a_1=2\text{.}
\end{equation*}
Exercise5.2.6
Find an explicit formula for the following sequence defined by:
\begin{equation*}
a_n=4a_{n-1}-3a_{n-2}\mbox{ for } n\geq 2\mbox{ and } a_0=1,a_1=13\text{.}
\end{equation*}
Exercise5.2.7
Find a closed-form formula for the following sequence defined by:
\begin{equation*}
a_n=-2a_{n-1}+a_{n-2}+2a_{n-3}\mbox{ for } n\geq 3\mbox{ and } a_0=0,a_1=1,a_2=2\text{.}
\end{equation*}
Exercise5.2.8
Find an explicit formula for the following sequence defined by:
\begin{equation*}
a_n=6a_{n-1}-11a_{n-2}+6a_{n-3}\mbox{ for } n\geq 3\mbox{ and } a_0=0,a_1=0,a_2=1\text{.}
\end{equation*}
Exercise5.2.9
Find a closed-form formula for the following sequence defined by:
\begin{equation*}
a_n=4a_{n-1}-4a_{n-2}\mbox{ for } n\geq 2\mbox{ and } a_0=-1,a_1=0\text{.}
\end{equation*}
Exercise5.2.10
Find an explicit formula for the following sequence defined by:
\begin{equation*}
a_n=5a_{n-1}-3a_{n-2}-9a_{n-3}\mbox{ for } n\geq 3\mbox{ and } a_0=3,a_1=4,a_2=29\text{.}
\end{equation*}
Exercise5.2.11
Prove that the sequence defined by
\begin{equation*}
u_n=\left(\frac{5-3\sqrt{5}}{2}\right)^n+\left(\frac{5+3\sqrt{5}}{2}\right)^n, n\geq 0
\end{equation*}
contains only integers and \(u_n\) is divisible by 5 if \(n\geq 1\text{.}\)
Exercise5.2.12
Prove that the sequence defined by
\begin{equation*}
(4-\sqrt{2})^n+(4+\sqrt{2})^n, n\geq 0
\end{equation*}
contains only integers divisible by 2.