The Tower of Hanoi often appears in textbooks and entrance exam problems as material for recurrence relations and mathematical induction in high school math. In this article, we practice the ideas by working through examples. The disks are numbered 1, 2, 3… from smallest to largest, and we write the fewest moves to move a tower of n disks as aₙ.
Example 1: Set Up a Recurrence Relation
Problem: There are three poles A, B and C, and n disks of different sizes are stacked on A, largest at the bottom. Move the disks one at a time, never putting a large disk on a small disk, until all the disks are moved to C. Writing the fewest number of moves as aₙ, express aₙ₊₁ in terms of aₙ.
Solution: Focus on the largest disk (disk n+1). To move this disk to C, at that moment the top n disks must all be stacked on B.
- Move the top n disks from A to B … at least aₙ moves
- Move disk n+1 from A to C … 1 move
- Move the n disks on B to C … at least aₙ moves
With this procedure you can move n+1 disks, so aₙ₊₁ ≦ 2aₙ + 1. Conversely, whatever the procedure, the moves in 1 to 3 are always needed, so aₙ₊₁ ≧ 2aₙ + 1. Therefore,
aₙ₊₁ = 2aₙ + 1 (a₁ = 1)
In entrance exams you may be asked to show both ”≦” and ”≧” and state the equality outright. A detailed explanation is in the minimum-moves formula.
Example 2: Find the General Term
Problem: Find the general term of the sequence defined by a₁ = 1 and aₙ₊₁ = 2aₙ + 1.
Solution: A recurrence relation of the form aₙ₊₁ = paₙ + q is rewritten using the α that satisfies α = 2α + 1. Since α = −1, add 1 to both sides to get
aₙ₊₁ + 1 = 2(aₙ + 1).
The sequence aₙ + 1 is a geometric sequence with first term a₁ + 1 = 2 and common ratio 2. So aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, and
aₙ = 2ⁿ − 1.
As a check, confirm that a₁ = 1, a₂ = 3 and a₃ = 7 fit the recurrence relation.
Example 3: Prove by Mathematical Induction
Problem: Prove by mathematical induction that the fewest moves to move n disks is 2ⁿ − 1.
Solution:
- When n = 1, one disk can be moved in 1 move and cannot be done in fewer, so the fewest moves is 1 = 2¹ − 1, and it holds.
- Assume that when n = k, the fewest moves is 2ᵏ − 1. When n = k+1, by the idea of Example 1 the fewest moves is 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, so it also holds when n = k+1.
- From 1 and 2, it holds for all natural numbers n.
The key point is that “both ≦ and ≧” from Example 1 are used in step 2 of the induction.
Example 4: When Disks Can Move Only to Adjacent Poles
Problem: Poles A, B and C are in a row, and disks can move only between A and B, and between B and C (they cannot move directly from A to C). Find the fewest moves bₙ to move n disks from A to C.
Solution: The largest disk n must move twice, A → B → C.
- Move the top n − 1 disks from A to C … bₙ₋₁ moves (to move n to B, B must be empty)
- Move disk n from A to B … 1 move
- Move the n − 1 disks from C to A … bₙ₋₁ moves (to move n to C, C must be empty)
- Move disk n from B to C … 1 move
- Move the n − 1 disks from A to C … bₙ₋₁ moves
So bₙ = 3bₙ₋₁ + 2 (b₁ = 2). From α = 3α + 2, α = −1, so bₙ + 1 = 3(bₙ₋₁ + 1). The sequence bₙ + 1 is a geometric sequence with first term 3 and common ratio 3, so
bₙ = 3ⁿ − 1.
For 1 to 6 disks, we have also confirmed by a calculation that checks all the arrangements that this is the fewest number of moves. Interestingly, during the 3ⁿ − 1 moves, the solution passes through all 3ⁿ arrangements exactly once (the number of arrangements is in the article on patterns).
Example 5: Practice Problems
Finally, try solving them yourself. The answers are below.
- Find the fewest moves for 10 disks.
- For how many disks or more does the fewest number of moves exceed 1,000?
- When moving n disks in the fewest moves, how many times does the smallest disk move?
Answers: 1. 2¹⁰ − 1 = 1,023 moves. 2. From 2ⁿ − 1 > 1000, 2ⁿ > 1001. Since 2⁹ = 512 and 2¹⁰ = 1024, it is 10 disks or more. 3. 2ⁿ⁻¹ times (the reason is in “The Number of Times Each Disk Moves” in the article on patterns).
