Page 537 - Discrete Mathematics and Its Applications

516 8 / Advanced Counting Techniques

To show that every solution {a n } of the recurrence relation a n = c 1 a n−1 + c 2 a n−2
n
n
has a n = α 1 r + α 2 r for n = 0, 1, 2,..., for some constants α 1 and α 2 , suppose that {a n } is a
1 2
solution of the recurrence relation, and the initial conditions a 0 = C 0 and a 1 = C 1 hold. It will
n
be shown that there are constants α 1 and α 2 such that the sequence {a n } with a n = α 1 r + α 2 r n
1 2
satisfies these same initial conditions. This requires that
a 0 = C 0 = α 1 + α 2 ,
a 1 = C 1 = α 1 r 1 + α 2 r 2 .
We can solve these two equations for α 1 and α 2 . From the first equation it follows that
α 2 = C 0 − α 1 . Inserting this expression into the second equation gives
C 1 = α 1 r 1 + (C 0 − α 1 )r 2 .

Hence,

C 1 = α 1 (r 1 − r 2 ) + C 0 r 2 .

This shows that
C 1 − C 0 r 2
α 1 =
r 1 − r 2
and

C 1 − C 0 r 2 C 0 r 1 − C 1
α 2 = C 0 − α 1 = C 0 − = ,
r 1 − r 2 r 1 − r 2
where these expressions for α 1 and α 2 depend on the fact that r 1 = r 2 . (When r 1 = r 2 , this
n
theorem is not true.) Hence, with these values for α 1 and α 2 , the sequence {a n } with α 1 r + α 2 r n
1 2
satisfies the two initial conditions.
n
n
We know that {a n } and {α 1 r + α 2 r } are both solutions of the recurrence relation
1 2
a n = c 1 a n−1 + c 2 a n−2 and both satisfy the initial conditions when n = 0 and n = 1. Because
there is a unique solution of a linear homogeneous recurrence relation of degree two with two
n
n
initial conditions, it follows that the two solutions are the same, that is, a n = α 1 r + α 2 r for
1 2
all nonnegative integers n. We have completed the proof by showing that a solution of the lin-
ear homogeneous recurrence relation with constant coefficients of degree two must be of the
n
n
form a n = α 1 r + α 2 r , where α 1 and α 2 are constants.
1 2
The characteristic roots of a linear homogeneous recurrence relation with constant coeffi-
cients may be complex numbers. Theorem 1 (and also subsequent theorems in this section) still
applies in this case. Recurrence relations with complex characteristic roots will not be discussed
in the text. Readers familiar with complex numbers may wish to solve Exercises 38 and 39.
Examples 3 and 4 show how to use Theorem 1 to solve recurrence relations.
EXAMPLE 3 What is the solution of the recurrence relation

a n = a n−1 + 2a n−2
with a 0 = 2 and a 1 = 7?

Solution: Theorem 1 can be used to solve this problem. The characteristic equation of the
2
recurrence relation is r − r − 2 = 0. Its roots are r = 2 and r =−1. Hence, the sequence {a n }
is a solution to the recurrence relation if and only if

n n
a n = α 1 2 + α 2 (−1) ,