Page 179 - Discrete Mathematics and Its Applications

158 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

to provide one or more initial terms together with a rule for determining subsequent terms from
those that precede them.

DEFINITION 4 A recurrence relation for the sequence {a n } is an equation that expresses a n in terms of one or
more of the previous terms of the sequence, namely, a 0 ,a 1 ,...,a n−1 , for all integers n with
n ≥ n 0 , where n 0 is a nonnegative integer. A sequence is called a solution of a recurrence
relation if its terms satisfy the recurrence relation. (A recurrence relation is said to recursively
define a sequence. We will explain this alternative terminology in Chapter 5.)

EXAMPLE 5 Let {a n } be a sequence that satisfies the recurrence relation a n = a n−1 + 3 for n = 1, 2, 3,...,
and suppose that a 0 = 2. What are a 1 , a 2 , and a 3 ?
Solution: We see from the recurrence relation that a 1 = a 0 + 3 = 2 + 3 = 5. It then follows
that a 2 = 5 + 3 = 8 and a 3 = 8 + 3 = 11. ▲

EXAMPLE 6 Let {a n } be a sequence that satisfies the recurrence relation a n = a n−1 − a n−2 for n =
2, 3, 4,..., and suppose that a 0 = 3 and a 1 = 5. What are a 2 and a 3 ?

Solution: We see from the recurrence relation that a 2 = a 1 − a 0 = 5 − 3 = 2 and a 3 = a 2 −
a 1 = 2 − 5 =−3. We can find a 4 , a 5 , and each successive term in a similar way. ▲

The initial conditions for a recursively defined sequence specify the terms that precede the
first term where the recurrence relation takes effect. For instance, the initial condition in Example
5is a 0 = 2, and the initial conditions in Example 6 are a 0 = 3 and a 1 = 5. Using mathematical
induction, a proof technique introduced in Chapter 5, it can be shown that a recurrence relation
together with its initial conditions determines a unique solution.
Hop along to Chapter 8
to learn how to find a Next, we define a particularly useful sequence defined by a recurrence relation, known as
formula for the Fibonacci the Fibonacci sequence, after the Italian mathematician Fibonacci who was born in the 12th
numbers. century (see Chapter 5 for his biography). We will study this sequence in depth in Chapters 5
and 8, where we will see why it is important for many applications, including modeling the
population growth of rabbits.

DEFINITION 5 The Fibonacci sequence, f 0 ,f 1 ,f 2 ,..., is defined by the initial conditions f 0 = 0,f 1 = 1,
and the recurrence relation

f n = f n−1 + f n−2

for n = 2, 3, 4,....

EXAMPLE 7 Find the Fibonacci numbers f 2 , f 3 , f 4 , f 5 , and f 6 .

Solution: The recurrence relation for the Fibonacci sequence tells us that we find successive
terms by adding the previous two terms. Because the initial conditions tell us that f 0 = 0 and
f 1 = 1, using the recurrence relation in the definition we find that

f 2 = f 1 + f 0 = 1 + 0 = 1,
f 3 = f 2 + f 1 = 1 + 1 = 2,
f 4 = f 3 + f 2 = 2 + 1 = 3,
f 5 = f 4 + f 3 = 3 + 2 = 5,
▲
f 6 = f 5 + f 4 = 5 + 3 = 8.