Page 536 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 515

Linear homogeneous recurrence relations are studied for two reasons. First, they often occur
in modeling of problems. Second, they can be systematically solved.

Solving Linear Homogeneous Recurrence Relations
with Constant Coefficients

The basic approach for solving linear homogeneous recurrence relations is to look for solutions
n
n
of the form a n = r , where r is a constant. Note that a n = r 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
n
r = c 1 r n−1 + c 2 r n−2 + ··· + c k r n−k .
When both sides of this equation are divided by r n−k and the right-hand side is subtracted from
the left, we obtain the equation

k k−1 k−2
r − c 1 r − c 2 r − ··· − c k−1 r − c k = 0.
n
Consequently, the sequence {a n } with a n = r is a solution if and only if r is a solution of this
last equation. We call this the characteristic equation of the recurrence relation. The solutions
of this equation are called the characteristic roots of the recurrence relation. As we will see,
these characteristic roots can be used to give an explicit formula for all the solutions of the
recurrence relation.
We will first develop results that deal with linear homogeneous recurrence relations with
constant coefficients of degree two. Then corresponding general results when the degree may be
greater than two will be stated. Because the proofs needed to establish the results in the general
case are more complicated, they will not be given here.
We now turn our attention to linear homogeneous recurrence relations of degree two. First,
consider the case when there are two distinct characteristic roots.

2
THEOREM 1 Let c 1 and c 2 be real numbers. Suppose that r − c 1 r − c 2 = 0 has two distinct roots r 1
and r 2 . Then the sequence {a n } is a solution of the recurrence relation a n = c 1 a n−1 + c 2 a n−2
n
n
if and only if a n = α 1 r + α 2 r for n = 0, 1, 2,..., where α 1 and α 2 are constants.
1 2
Proof: We must do two things to prove the theorem. First, it must be shown that if r 1 and r 2
are the roots of the characteristic equation, and α 1 and α 2 are constants, then the sequence {a n }
n
n
with a n = α 1 r + α 2 r is a solution of the recurrence relation. Second, it must be shown that
1 2
n
n
if the sequence {a n } is a solution, then a n = α 1 r + α 2 r for some constants α 1 and α 2 .
2
1
n
n
Now we will show that if a n = α 1 r + α 2 r , then the sequence {a n } is a solution
1 2
2
of the recurrence relation. Because r 1 and r 2 are roots of r − c 1 r − c 2 = 0, it follows
2
2
that r = c 1 r 1 + c 2 , r = c 1 r 2 + c 2 .
1 2
From these equations, we see that
c 1 a n−1 + c 2 a n−2 = c 1 (α 1 r n−1 + α 2 r n−1 ) + c 2 (α 1 r n−2 + α 2 r n−2 )
1 2 1 2
= α 1 r n−2 (c 1 r 1 + c 2 ) + α 2 r n−2 (c 1 r 2 + c 2 )
1 2
n−2 2 n−2 2
= α 1 r r + α 2 r r
1 1 2 2
n
= α 1 r + α 2 r 2 n
1
= a n .
n
n
This shows that the sequence {a n } with a n = α 1 r + α 2 r is a solution of the recurrence relation.
2
1