Page 541 - Discrete Mathematics and Its Applications

520 8 / Advanced Counting Techniques

EXAMPLE 7 Suppose that the roots of the characteristic equation of a linear homogeneous recurrence relation
are 2, 2, 2, 5, 5, and 9 (that is, there are three roots, the root 2 with multiplicity three, the root
5 with multiplicity two, and the root 9 with multiplicity one). What is the form of the general
solution?

Solution: By Theorem 4, the general form of the solution is

n
2
n
n
(α 1,0 + α 1,1 n + α 1,2 n )2 + (α 2,0 + α 2,1 n)5 + α 3,0 9 .
▲
We now illustrate the use of Theorem 4 to solve a linear homogeneous recurrence relation
with constant coefficients when the characteristic equation has a root of multiplicity three.
EXAMPLE 8 Find the solution to the recurrence relation

a n =−3a n−1 − 3a n−2 − a n−3
with initial conditions a 0 = 1, a 1 =−2, and a 2 =−1.

Solution: The characteristic equation of this recurrence relation is

2
3
r + 3r + 3r + 1 = 0.
2
3
3
Because r + 3r + 3r + 1 = (r + 1) , there is a single root r =−1 of multiplicity three of
the characteristic equation. By Theorem 4 the solutions of this recurrence relation are of the
form
2
n
n
n
a n = α 1,0 (−1) + α 1,1 n(−1) + α 1,2 n (−1) .
To find the constants α 1,0 ,α 1,1 , and α 1,2 , use the initial conditions. This gives
a 0 = 1 = α 1,0 ,
a 1 =−2 =−α 1,0 − α 1,1 − α 1,2 ,
a 2 =−1 = α 1,0 + 2α 1,1 + 4α 1,2 .

The simultaneous solution of these three equations is α 1,0 = 1, α 1,1 = 3, and α 1,2 =−2.
Hence, the unique solution to this recurrence relation and the given initial conditions is the
sequence {a n } with

n
2
a n = (1 + 3n − 2n )(−1) .
▲
Linear Nonhomogeneous Recurrence Relations
with Constant Coefficients

We have seen how to solve linear homogeneous recurrence relations with constant coefficients.
Is there a relatively simple technique for solving a linear, but not homogeneous, recurrence
relation with constant coefficients, such as a n = 3a n−1 + 2n? We will see that the answer is yes
for certain families of such recurrence relations.
The recurrence relation a n = 3a n−1 + 2n is an example of a linear nonhomogeneous
recurrence relation with constant coefficients, that is, a recurrence relation of the form

a n = c 1 a n−1 + c 2 a n−2 + ··· + c k a n−k + F(n),