Advanced book on Mathematics Olympiad

3.1 Sequences and Series 101

Ais diagonalizable. There exists an invertible matrixSsuch thatA=SDS−^1 , whereD

is diagonal with diagonal entries equal to the eigenvalues ofA. From the equality

vn=SDnS−^1 v 0 ,

we conclude that the entries ofvnare linear combinations ofλn 1 ,λn 2 ,...,λnk. In particular,

forxn, which is the first coordinate ofvn, there exist constantsα 1 ,α 2 ,...,αksuch that

xn=α 1 λn 1 +α 2 λn 2 +···+αkλnk, forn≥ 0.

The numbersα 1 ,α 2 ,...,αkare found from the initial condition, by solving the linear

system

α 1 +α 2 +···αk=x 0 ,

λ 1 α 1 +λ 2 α 2 +···λkαk=x 1 ,

λ^21 α 1 +λ^22 α 2 +···λ^2 kαk=x 2 ,

···

λk 1 −^1 α 1 +λk 2 −^1 α 2 +···λkk−^1 αk=xk− 1.

Note that the determinant of the coefficient matrix is Vandermonde, so the system has a

unique solution!

If the roots of the characteristic equation have multiplicities greater than 1, it might

happen thatAis not diagonalizable. The Jordan canonical form ofAhas blocks of

the form

Jm(λi)=

⎛

⎜

⎜⎜

⎜⎜

⎝

λi 10 ··· 0

0 λi 1 ··· 0

00 λi··· 0

..

.

..

.

..

.

... ..

.

000 ···λi

⎞

⎟

⎟⎟

⎟⎟

⎠

.

An exercise in Section 2.3.1 shows that forj≥i, theijentry ofJm(λi)nis

(n

j−i

)

λni+i−j.

We conclude that if the roots of the characteristic equations areλ 1 ,λ 2 ,...,λt and

m 1 ,m 2 ,...,mt their respective multiplicities, then there exist constantsαij, i =

1 , 2 ,...,t,j= 0 , 1 ,...,mi−1, such that

xn=

∑t

i= 1

m∑i− 1

j= 0

αij

(

n

j

)

λni−j, forn≥ 0.

It might be more useful to write this as