Page 538 - Discrete Mathematics and Its Applications

8.2 Solving Linear Recurrence Relations 517

for some constants α 1 and α 2 . From the initial conditions, it follows that

a 0 = 2 = α 1 + α 2 ,
a 1 = 7 = α 1 · 2 + α 2 · (−1).

Solving these two equations shows that α 1 = 3 and α 2 =−1. Hence, the solution to the recur-
rence relation and initial conditions is the sequence {a n } with

n
n
a n = 3 · 2 − (−1) . ▲

EXAMPLE 4 Find an explicit formula for the Fibonacci numbers.

Solution: Recall that the sequence of Fibonacci numbers satisfies the recurrence relation
f n = f n−1 + f n−2 and also satisfies the initial conditions f 0 = 0 and f 1 = 1. The roots of the
√
√
2
characteristic equation r − r − 1 = 0 are r 1 = (1 + 5)/2 and r 2 = (1 − 5)/2. Therefore,
from Theorem 1 it follows that the Fibonacci numbers are given by
√ n √ n
1 + 5 1 − 5
f n = α 1 + α 2 ,
2 2
for some constants α 1 and α 2 . The initial conditions f 0 = 0 and f 1 = 1 can be used to find these
constants. We have

f 0 = α 1 + α 2 = 0,
√ √

1 + 5 1 − 5
f 1 = α 1 + α 2 = 1.
2 2
The solution to these simultaneous equations for α 1 and α 2 is

√ √
α 1 = 1/ 5, α 2 =−1/ 5.

Consequently, the Fibonacci numbers are given by

√ √
n n
1 1 + 5 1 1 − 5
f n = √ − √ . ▲
5 2 5 2
Theorem 1 does not apply when there is one characteristic root of multiplicity two. If
n
this happens, then a n = nr is another solution of the recurrence relation when r 0 is a root of
0
multiplicity two of the characteristic equation. Theorem 2 shows how to handle this case.

2
THEOREM 2 Let c 1 and c 2 be real numbers with c 2 = 0. Suppose that r − c 1 r − c 2 = 0 has only one
root r 0 . A sequence {a n } is a solution of the recurrence relation a n = c 1 a n−1 + c 2 a n−2 if and
n
n
only if a n = α 1 r + α 2 nr , for n = 0, 1, 2,..., where α 1 and α 2 are constants.
0
0
The proof of Theorem 2 is left as Exercise 10. Example 5 illustrates the use of this theorem.