Page 180 - Discrete Mathematics and Its Applications

2.4 Sequences and Summations 159

EXAMPLE 8 Suppose that {a n } is the sequence of integers defined by a n = n!, the value of the factorial
function at the integer n, where n = 1, 2, 3,.... Because n!= n((n − 1)(n − 2)... 2 · 1) =
n(n − 1)!= na n−1 , we see that the sequence of factorials satisfies the recurrence relation
a n = na n−1 , together with the initial condition a 1 = 1. ▲

We say that we have solved the recurrence relation together with the initial conditions when
we find an explicit formula, called a closed formula, for the terms of the sequence.
EXAMPLE 9 Determine whether the sequence {a n }, where a n = 3n for every nonnegative integer n,isa
solution of the recurrence relation a n = 2a n−1 − a n−2 for n = 2, 3, 4,... . Answer the same
n
question where a n = 2 and where a n = 5.
Solution: Suppose that a n = 3n for every nonnegative integer n. Then, for n ≥ 2, we see that
2a n−1 − a n−2 = 2(3(n − 1)) − 3(n − 2) = 3n = a n . Therefore, {a n }, where a n = 3n,isaso-
lution of the recurrence relation.
n
Suppose that a n = 2 for every nonnegative integer n. Note that a 0 = 1, a 1 = 2, and a 2 = 4.
n
Because 2a 1 − a 0 = 2 · 2 − 1 = 3 = a 2 , we see that {a n }, where a n = 2 , is not a solution of
the recurrence relation.
Suppose that a n = 5 for every nonnegative integer n. Then for n ≥ 2, we see that a n =
2a n−1 − a n−2 = 2 · 5 − 5 = 5 = a n . Therefore, {a n }, where a n = 5, is a solution of the recur-
rence relation. ▲

Manymethodshavebeendevelopedforsolvingrecurrencerelations.Here,wewillintroduce
a straightforward method known as iteration via several examples. In Chapter 8 we will study
recurrence relations in depth. In that chapter we will show how recurrence relations can be used
to solve counting problems and we will introduce several powerful methods that can be used to
solve many different recurrence relations.

EXAMPLE 10 Solve the recurrence relation and initial condition in Example 5.

Solution: We can successively apply the recurrence relation in Example 5, starting with the
initial condition a 1 = 2, and working upward until we reach a n to deduce a closed formula for
the sequence. We see that

a 2 = 2 + 3
a 3 = (2 + 3) + 3 = 2 + 3 · 2
a 4 = (2 + 2 · 3) + 3 = 2 + 3 · 3
.
.
.
a n = a n−1 + 3 = (2 + 3 · (n − 2)) + 3 = 2 + 3(n − 1).

We can also successively apply the recurrence relation in Example 5, starting with the
term a n and working downward until we reach the initial condition a 1 = 2 to deduce this same
formula. The steps are

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