Page 543 - Discrete Mathematics and Its Applications

522 8 / Advanced Counting Techniques

and a solution of the associated homogeneous recurrence relation. Although there is no general
method for finding such a solution that works for every function F(n), there are techniques that
work for certain types of functions F(n), such as polynomials and powers of constants. This is
illustrated in Examples 10 and 11.

EXAMPLE 10 Find all solutions of the recurrence relation a n = 3a n−1 + 2n. What is the solution with a 1 = 3?

Solution:To solve this linear nonhomogeneous recurrence relation with constant coefficients, we
need to solve its associated linear homogeneous equation and to find a particular solution for the
given nonhomogeneous equation. The associated linear homogeneous equation is a n = 3a n−1 .
(h) n
Its solutions are a n = α3 , where α is a constant.
We now find a particular solution. Because F(n) = 2n is a polynomial in n of degree
one, a reasonable trial solution is a linear function in n, say, p n = cn + d, where c and d are
constants.To determine whether there are any solutions of this form, suppose that p n = cn + d is
such a solution. Then the equation a n = 3a n−1 + 2n becomes cn + d = 3(c(n − 1) + d) + 2n.
Simplifying and combining like terms gives (2 + 2c)n + (2d − 3c) = 0. It follows that cn + d
is a solution if and only if 2 + 2c = 0 and 2d − 3c = 0. This shows that cn + d is a solution if
(p)
and only if c =−1 and d =−3/2. Consequently, a n =−n − 3/2 is a particular solution.
By Theorem 5 all solutions are of the form

3
(p) (h) n
a n = a n + a n =−n − + α · 3 ,
2
where α is a constant.
To find the solution with a 1 = 3, let n = 1 in the formula we obtained for the general
solution. We find that 3 =−1 − 3/2 + 3α, which implies that α = 11/6. The solution we seek
n
is a n =−n − 3/2 + (11/6)3 . ▲

EXAMPLE 11 Find all solutions of the recurrence relation

n
a n = 5a n−1 − 6a n−2 + 7 .

Solution: This is a linear nonhomogeneous recurrence relation. The solutions of its associated
homogeneous recurrence relation

a n = 5a n−1 − 6a n−2
(h) n n n
are a n = α 1 · 3 + α 2 · 2 , where α 1 and α 2 are constants. Because F(n) = 7 , a reason-
(p) n
able trial solution is a n = C · 7 , where C is a constant. Substituting the terms of this se-
n
n
quence into the recurrence relation implies that C · 7 = 5C · 7 n−1 − 6C · 7 n−2 + 7 . Factoring
out 7 n−2 , this equation becomes 49C = 35C − 6C + 49, which implies that 20C = 49, or that
(p) n
C = 49/20. Hence, a n = (49/20)7 is a particular solution. By Theorem 5, all solutions are
of the form
n
n
n
a n = α 1 · 3 + α 2 · 2 + (49/20)7 . ▲
In Examples 10 and 11, we made an educated guess that there are solutions of a particular
form. In both cases we were able to find particular solutions. This was not an accident.Whenever
F(n) is the product of a polynomial in n and the nth power of a constant, we know exactly what
form a particular solution has, as stated in Theorem 6. We leave the proof of Theorem 6 as
Exercise 52.