Page 539 - Discrete Mathematics and Its Applications

518 8 / Advanced Counting Techniques

EXAMPLE 5 What is the solution of the recurrence relation

a n = 6a n−1 − 9a n−2

with initial conditions a 0 = 1 and a 1 = 6?

2
Solution: The only root of r − 6r + 9 = 0is r = 3. Hence, the solution to this recurrence
relation is
n
a n = α 1 3 + α 2 n3 n

for some constants α 1 and α 2 . Using the initial conditions, it follows that

a 0 = 1 = α 1 ,
a 1 = 6 = α 1 · 3 + α 2 · 3.

Solving these two equations shows that α 1 = 1 and α 2 = 1. Consequently, the solution to this
recurrence relation and the initial conditions is

n n
a n = 3 + n3 .
▲

We will now state the general result about the solution of linear homogeneous recurrence
relations with constant coefficients, where the degree may be greater than two, under the as-
sumption that the characteristic equation has distinct roots. The proof of this result will be left
as Exercise 16.

THEOREM 3 Let c 1 ,c 2 ,...,c k be real numbers. Suppose that the characteristic equation

k
r − c 1 r k−1 − ··· − c k = 0
has k distinct roots r 1 ,r 2 ,...,r k . Then a sequence {a n } is a solution of the recurrence relation

a n = c 1 a n−1 + c 2 a n−2 + ··· + c k a n−k

if and only if

n
n
a n = α 1 r + α 2 r + ··· + α k r k n
1
2
for n = 0, 1, 2,..., where α 1 ,α 2 ,...,α k are constants.

We illustrate the use of the theorem with Example 6.

EXAMPLE 6 Find the solution to the recurrence relation

a n = 6a n−1 − 11a n−2 + 6a n−3

with the initial conditions a 0 = 2, a 1 = 5, and a 2 = 15.