Page 526 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 505
EXAMPLE 3
Tower of Hanoi puzzle, except that four pegs are used.You may find it surprising that no one has
been able to establish the minimum number of moves required to solve this puzzle for n disks.
However, there is a conjecture, now more than 50 years old, that the minimum number of moves
required equals the number of moves used by an algorithm invented by Frame and Stewart
in 1939. (See Exercises 38–45 and [St94] for more information.)
Example 3 illustrates how recurrence relations can be used to count bit strings of a specified
length that have a certain property.
Find a recurrence relation and give initial conditions for the number of bit strings of length n
that do not have two consecutive 0s. How many such bit strings are there of length five?
Solution: Let a n denote the number of bit strings of length n that do not have two consecutive 0s.
To obtain a recurrence relation for {a n }, note that by the sum rule, the number of bit strings of
length n that do not have two consecutive 0s equals the number of such bit strings ending with
a 0 plus the number of such bit strings ending with a 1. We will assume that n ≥ 3, so that the
bit string has at least three bits.
The bit strings of length n ending with 1 that do not have two consecutive 0s are precisely the
bit strings of length n − 1 with no two consecutive 0s with a 1 added at the end. Consequently,
there are a n−1 such bit strings.
Bit strings of length n ending with a 0 that do not have two consecutive 0s must have 1
as their (n − 1)st bit; otherwise they would end with a pair of 0s. It follows that the bit strings
of length n ending with a 0 that have no two consecutive 0s are precisely the bit strings of
length n − 2 with no two consecutive 0s with 10 added at the end. Consequently, there are a n−2
such bit strings.
We conclude, as illustrated in Figure 4, that
a n = a n−1 + a n−2
for n ≥ 3.
The initial conditions are a 1 = 2, because both bit strings of length one, 0 and 1 do not have
consecutive 0s, and a 2 = 3, because the valid bit strings of length two are 01, 10, and 11. To
obtain a 5 , we use the recurrence relation three times to find that
a 3 = a 2 + a 1 = 3 + 2 = 5,
a 4 = a 3 + a 2 = 5 + 3 = 8,
a 5 = a 4 + a 3 = 8 + 5 = 13. ▲
Number of bit strings
of length n with no
two consecutive 0s:
Any bit string of length n –1 with
End with a 1: 1 a
no two consecutive 0s n–1
Any bit string of length n –2 with
End with a 0: 1 0 a
no two consecutive 0s n–2
Total: a = a n–1 + a n–2
n
FIGURE 4 Counting Bit Strings of Length n with No Two Consecutive 0s.