Page 523 - Discrete Mathematics and Its Applications

502 8 / Advanced Counting Techniques
EXAMPLE 1
Reproducing pairs
(at least two months old)
FIGURE 1
let a n be the number of bacteria at the end of n hours. Because the number of bacteria doubles
every hour, the relationship a n = 2a n−1 holds whenever n is a positive integer. This recurrence
relation, together with the initial condition a 0 = 5, uniquely determines a n for all nonnegative
integers n. We can find a formula for a n using the iterative approach followed in Chapter 2,
n
namely that a n = 5 · 2 for all nonnegative integers n.
Some of the counting problems that cannot be solved using the techniques discussed in
Chapter 6 can be solved by finding recurrence relations involving the terms of a sequence, as
was done in the problem involving bacteria. In this section we will study a variety of counting
problems that can be modeled using recurrence relations. In Chapter 2 we developed methods
for solving certain recurrence relation. In Section 8.2 we will study methods for finding explicit
formulae for the terms of sequences that satisfy certain types of recurrence relations.
Weconcludethissectionbyintroducingthealgorithmicparadigmofdynamicprogramming.
After explaining how this paradigm works, we will illustrate its use with an example.
Modeling With Recurrence Relations
We can use recurrence relations to model a wide variety of problems, such as finding compound
interest (see Example 11 in Section2.4), counting rabbits on an island, determining the number
of moves in the Tower of Hanoi puzzle, and counting bit strings with certain properties.
Example 1 shows how the population of rabbits on an island can be modeled using a
recurrence relation.
Rabbits and the Fibonacci Numbers Consider this problem, which was originally posed by
Leonardo Pisano, also known as Fibonacci, in the thirteenth century in his book Liber abaci.A
young pair of rabbits (one of each sex) is placed on an island. A pair of rabbits does not breed
until they are 2 months old. After they are 2 months old, each pair of rabbits produces another
pair each month, as shown in Figure 1. Find a recurrence relation for the number of pairs of
rabbits on the island after n months, assuming that no rabbits ever die.
Young pairs Reproducing Young Total
(less than two months old) Month pairs pairs pairs
1 0 1 1
2 0 1 1
3 1 1 2
4 1 2 3
5 2 3 5
6 3 5 8
Rabbits on an Island.