Page 542 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 521

where c 1 ,c 2 ,...,c k are real numbers and F(n) is a function not identically zero depending
only on n. The recurrence relation

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

is called the associated homogeneous recurrence relation. It plays an important role in the
solution of the nonhomogeneous recurrence relation.

n
2
EXAMPLE 9 Each of the recurrence relations a n = a n−1 + 2 , a n = a n−1 + a n−2 + n + n + 1, a n =
n
3a n−1 + n3 , and a n = a n−1 + a n−2 + a n−3 + n! is a linear nonhomogeneous recurrence re-
lation with constant coefficients. The associated linear homogeneous recurrence relations are
a n = a n−1 , a n = a n−1 + a n−2 , a n = 3a n−1 , and a n = a n−1 + a n−2 + a n−3 , respectively. ▲
The key fact about linear nonhomogeneous recurrence relations with constant coefficients
is that every solution is the sum of a particular solution and a solution of the associated linear
homogeneous recurrence relation, as Theorem 5 shows.

THEOREM 5 (p)
If {a n } is a particular solution of the nonhomogeneous linear recurrence relation with
constant coefficients

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

(p) (h) (h)
then every solution is of the form {a n + a n }, where {a n } is a solution of the associated
homogeneous recurrence relation

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

(p)
Proof: Because {a n } is a particular solution of the nonhomogeneous recurrence relation, we
know that

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

Now suppose that {b n } is a second solution of the nonhomogeneous recurrence relation, so that

b n = c 1 b n−1 + c 2 b n−2 + ··· + c k b n−k + F(n).

Subtracting the first of these two equations from the second shows that

(p) (p) (p) (p)
b n − a n = c 1 (b n−1 − a ) + c 2 (b n−2 − a ) + ··· + c k (b n−k − a ).
n−1 n−2 n−k
p
It follows that {b n − a n } is a solution of the associated homogeneous linear recurrence,
(h) (p) (h)
say, {a n }. Consequently, b n = a n + a n for all n.
By Theorem 5, we see that the key to solving nonhomogeneous recurrence relations with
constant coefficients is finding a particular solution. Then every solution is a sum of this solution