Page 525 - Discrete Mathematics and Its Applications

504 8 / Advanced Counting Techniques

Peg 1 Peg 2 Peg 3

FIGURE 3 An Intermediate Position in the Tower of Hanoi.

We can use an iterative approach to solve this recurrence relation. Note that

H n = 2H n−1 + 1
2
= 2(2H n−2 + 1) + 1 = 2 H n−2 + 2 + 1
2
3
2
= 2 (2H n−3 + 1) + 2 + 1 = 2 H n−3 + 2 + 2 + 1
.
.
.
= 2 n−1 H 1 + 2 n−2 + 2 n−3 + ··· + 2 + 1
= 2 n−1 + 2 n−2 + ··· + 2 + 1
n
= 2 − 1.
We have used the recurrence relation repeatedly to express H n in terms of previous terms of
the sequence. In the next to last equality, the initial condition H 1 = 1 has been used. The last
equality is based on the formula for the sum of the terms of a geometric series, which can be
found in Theorem 1 in Section 2.4.
The iterative approach has produced the solution to the recurrence relation H n = 2H n−1 + 1
with the initial condition H 1 = 1. This formula can be proved using mathematical induction.
This is left for the reader as Exercise 1.
A myth created to accompany the puzzle tells of a tower in Hanoi where monks are trans-
ferring 64 gold disks from one peg to another, according to the rules of the puzzle. The myth
says that the world will end when they finish the puzzle. How long after the monks started will
the world end if the monks take one second to move a disk?
From the explicit formula, the monks require

2 64 − 1 = 18,446,744,073,709,551,615

moves to transfer the disks. Making one move per second, it will take them more than 500 billion
years to complete the transfer, so the world should survive a while longer than it already has. ▲

Remark: Many people have studied variations of the original Tower of Hanoi puzzle discussed
in Example 2. Some variations use more pegs, some allow disks to be of the same size, and some
restrict the types of allowable disk moves. One of the oldest and most interesting variations is the
∗
Reve’s puzzle, proposed in 1907 by Henry Dudeney in his book The Canterbury Puzzles. The
Reve’s puzzle involves pilgrims challenged by the Reve to move a stack of cheeses of varying
sizes from the first of four stools to another stool without ever placing a cheese on one of smaller
diameter. The Reve’s puzzle, expressed in terms of pegs and disks, follows the same rules as the

∗ Reve, more commonly spelled reeve, is an archaic word for governor.