100 3 Real Analysis
3.1.2 Linear Recursive Sequences
In this section we give an overview of the theory of linear recurrences with constant
coefficients. You should notice the analogy with the theory of ordinary differential
equations. This is not an accident, since linear recurrences are discrete approximations
of differential equations.
Akth-order linear recurrence with constant coefficients is a relation of the form
xn=a 1 xn− 1 +a 2 xn− 2 +···+akxn−k,n≥k,satisfied by a sequence(xn)n≥ 0.
The sequence(xn)nis completely determined byx 0 ,x 1 ,...,xk− 1 (the initial condi-
tion). To find the formula for the general term, we introduce the vector-valued first-order
linear recursive sequencevn=(v^1 n,v^2 n,...,vkn)defined byv^1 n=xn+k− 1 ,vn^2 =xn+k− 2 ,
..., vnk=xn. This new sequence satisfies the recurrence relationvn+ 1 =Avn,n≥0,
where
A=
⎛
⎜
⎜⎜
⎜⎜
⎜
⎜
⎝
a 1 a 2 a 3 ···ak− 1 ak
100 ··· 00
010 ··· 00
001 ··· 00
..
...
.
..
.
... ..
.
..
.
000 ··· 10
⎞
⎟
⎟⎟
⎟⎟
⎟⎟
⎠
.
It follows thatvn=Anv 0 , and the problem reduces to the computation of thenth power
ofA. A standard method employs the Jordan canonical form.
First, we determine the eigenvalues ofA. The characteristic polynomial is
PA(λ)=∣∣
∣∣
∣
∣∣
∣∣
∣∣
∣∣
λ−a 1 −a 2 −a 3 ···ak− 1 −ak
− 1 λ 0 ··· 00
0 − 1 λ ··· 00
00 − 1 ··· 00
..
...
.
..
.
... ..
.
..
.
000 ··· − 1 λ∣∣
∣∣
∣
∣∣
∣∣
∣∣
∣∣
.
When expanding by the first row it is easy to remark that all minors are triangular, so the
determinant is equal toλk−a 1 λk−^1 −a 2 λk−^2 −···−ak. The equation
PA(λ)=λk−a 1 λk−^1 −a 2 λk−^2 −···−ak= 0is called the characteristic equation of the recursive sequence.
Letλ 1 ,λ 2 ,...,λkbe the roots of the characteristic equation, which are, in fact, the
eigenvalues ofA. If these roots are all distinct, the situation encountered most often, then