Page 524 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 503

Solution: Denote by f n the number of pairs of rabbits after n months. We will show that f n ,
n = 1, 2, 3,..., are the terms of the Fibonacci sequence.
The rabbit population can be modeled using a recurrence relation. At the end of the first
month, the number of pairs of rabbits on the island is f 1 = 1. Because this pair does not
breed during the second month, f 2 = 1 also. To find the number of pairs after n months, add
The Fibonacci numbers
the number on the island the previous month, f n−1 , and the number of newborn pairs, which
appear in many other
places in nature, including equals f n−2 , because each newborn pair comes from a pair at least 2 months old.
the number of petals on Consequently, the sequence {f n } satisfies the recurrence relation
flowers and the number of
spirals on seedheads.
f n = f n−1 + f n−2
for n ≥ 3 together with the initial conditions f 1 = 1 and f 2 = 1. Because this recurrence relation
and the initial conditions uniquely determine this sequence, the number of pairs of rabbits on
the island after n months is given by the nth Fibonacci number. ▲

Example 2 involves a famous puzzle.

EXAMPLE 2 The Tower of Hanoi A popular puzzle of the late nineteenth century invented by the French
mathematician Édouard Lucas, called the Tower of Hanoi, consists of three pegs mounted on
a board together with disks of different sizes. Initially these disks are placed on the first peg
in order of size, with the largest on the bottom (as shown in Figure 2). The rules of the puzzle
allow disks to be moved one at a time from one peg to another as long as a disk is never placed
on top of a smaller disk. The goal of the puzzle is to have all the disks on the second peg in
order of size, with the largest on the bottom.
Let H n denote the number of moves needed to solve the Tower of Hanoi problem with n
disks. Set up a recurrence relation for the sequence {H n }.

Solution: Begin with n disks on peg 1. We can transfer the top n − 1 disks, following the rules
of the puzzle, to peg 3 using H n−1 moves (see Figure 3 for an illustration of the pegs and disks
at this point). We keep the largest disk fixed during these moves. Then, we use one move to
transfer the largest disk to the second peg. We can transfer the n − 1 disks on peg 3 to peg 2
using H n−1 additional moves, placing them on top of the largest disk, which always stays fixed
on the bottom of peg 2. Moreover, it is easy to see that the puzzle cannot be solved using fewer
Schemes for efficiently
steps. This shows that
backing up computer files
on multiple tapes or other
media are based on the H n = 2H n−1 + 1.
moves used to solve the
Tower of Hanoi puzzle. The initial condition is H 1 = 1, because one disk can be transferred from peg 1 to peg 2,
according to the rules of the puzzle, in one move.

Peg 1 Peg 2 Peg 3

FIGURE 2 The Initial Position in the Tower of Hanoi.