Page 540 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 519

Solution: The characteristic polynomial of this recurrence relation is

3
2
r − 6r + 11r − 6.
3 2
The characteristic roots are r = 1, r = 2, and r = 3, because r − 6r + 11r − 6 =
(r − 1)(r − 2)(r − 3). Hence, the solutions to this recurrence relation are of the form

n
n
n
a n = α 1 · 1 + α 2 · 2 + α 3 · 3 .
To find the constants α 1 , α 2 , and α 3 , use the initial conditions. This gives
a 0 = 2 = α 1 + α 2 + α 3 ,
a 1 = 5 = α 1 + α 2 · 2 + α 3 · 3,
a 2 = 15 = α 1 + α 2 · 4 + α 3 · 9.

When these three simultaneous equations are solved for α 1 , α 2 , and α 3 , we find that α 1 = 1,
α 2 =−1, and α 3 = 2. Hence, the unique solution to this recurrence relation and the given initial
conditions is the sequence {a n } with

n
n
a n = 1 − 2 + 2 · 3 . ▲
We now state the most general result about linear homogeneous recurrence relations with
constant coefficients, allowing the characteristic equation to have multiple roots. The key point
is that for each root r of the characteristic equation, the general solution has a summand of the
n
form P (n)r , where P (n) is a polynomial of degree m − 1, with m the multiplicity of this root.
We leave the proof of this result as Exercise 51.

THEOREM 4 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 t distinct roots r 1 ,r 2 ,...,r t with multiplicities m 1 ,m 2 ,...,m t , respectively, so
that m i ≥ 1 for i = 1, 2,...,t and m 1 + m 2 + ··· + m t = 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

a n = (α 1,0 + α 1,1 n + ··· + α 1,m 1 −1 n m 1 −1 )r n
1
+ (α 2,0 + α 2,1 n + ··· + α 2,m 2 −1 n m 2 −1 )r n
2
+ ··· + (α t,0 + α t,1 n + ··· + α t,m t −1 n m t −1 )r n
t
for n = 0, 1, 2,..., where α i,j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ m i − 1.

Example 7 illustrates how Theorem 4 is used to find the general form of a solution of a
linear homogeneous recurrence relation when the characteristic equation has several repeated
roots.