Page 295 - A Course in Linear Algebra with Applications

8.2: Systems of Linear Recurrences 279

We shall only consider the case where the coefficients
constants. One objective might be to find all the functions
Vn , • • • i Vn which satisfy the equations of the system, i.e.,
the general solution. Alternatively, one might want to find a
solution which satisfies certain given conditions,

(1) _ h ,.(2) _ , ( m )
V6 7/ - h

where &i,..., b m are constants. Clearly the rabbit and weasel
problem is of this type.
The method adopted in Example 8.2.1 can be applied
with advantage to the general case. First convert the given
system of recurrences to matrix form byintroducing the matrix
A = [aij] m,m> the coefficient matrix, and defining

\ / 6 i \
yV b 2
= and B =
Y n
\y^J \bmJ

Then the system of recurrences becomes simply

*n+l = AY n,

with the initial condition Y Q — B. The general solution of this
is
n
= A B 0.
Y n
Now assume that A is diagonalizable: suppose that in
l
fact D = S~ AS is diagonal with diagonal entries di,..., d m.
n
1
Then A = SDS' 1 and A n = SD S- , so that
1
n
Y n = SD S~ B
Here of course D n is the diagonal matrix with entries