Page 544 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 523

THEOREM 6 Suppose that {a n } satisfies the linear nonhomogeneous recurrence relation

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

where c 1 ,c 2 ,...,c k are real numbers, and

t
n
F(n) = (b t n + b t−1 n t−1 + ··· + b 1 n + b 0 )s ,
where b 0 ,b 1 ,...,b t and s are real numbers.When s is not a root of the characteristic equation
of the associated linear homogeneous recurrence relation, there is a particular solution of the
form

n
t
(p t n + p t−1 n t−1 + ··· + p 1 n + p 0 )s .
When s is a root of this characteristic equation and its multiplicity is m, there is a particular
solution of the form

m t t−1 n
n (p t n + p t−1 n + ··· + p 1 n + p 0 )s .

Note that in the case when s is a root of multiplicity m of the characteristic equation of
m
the associated linear homogeneous recurrence relation, the factor n ensures that the proposed
particular solution will not already be a solution of the associated linear homogeneous recurrence
relation. We next provide Example 12 to illustrate the form of a particular solution provided by
Theorem 6.

EXAMPLE 12 What form does a particular solution of the linear nonhomogeneous recurrence relation
n n 2 n
a n = 6a n−1 − 9a n−2 + F(n) have when F(n) = 3 , F(n) = n3 , F(n) = n 2 , and F(n) =
2
n
(n + 1)3 ?
Solution: The associated linear homogeneous recurrence relation is a n = 6a n−1 − 9a n−2 . Its
2
2
characteristic equation, r − 6r + 9 = (r − 3) = 0, has a single root, 3, of multiplicity two.
n
To apply Theorem 6, with F(n) of the form P (n)s , where P (n) is a polynomial and s is a
constant, we need to ask whether s is a root of this characteristic equation.
Becauses = 3isarootwithmultiplicitym = 2buts = 2 isnotaroot,Theorem6tellsusthat
2 n n 2 n
a particular solution has the form p 0 n 3 if F(n) = 3 , the form n (p 1 n + p 0 )3 if F(n) =
n
n
2
2
2 n
2
n3 , the form (p 2 n + p 1 n + p 0 )2 if F(n) = n 2 , and the form n (p 2 n + p 1 n + p 0 )3 n
n
2
if F(n) = (n + 1)3 . ▲
Care must be taken when s = 1 when solving recurrence relations of the type covered by
Theorem 6. In particular, to apply this theorem with F(n) = b t n t + b t−1 n t−1 + ··· + b 1 n + b 0 ,
n
the parameter s takes the value s = 1 (even though the term 1 does not explicitly appear). By
the theorem, the form of the solution then depends on whether 1 is a root of the character-
istic equation of the associated linear homogeneous recurrence relation. This is illustrated in
Example 13, which shows how Theorem 6 can be used to find a formula for the sum of the first
n positive integers.
EXAMPLE 13 Let a n be the sum of the first n positive integers, so that
n

a n = k.
k=1