Subsection 8.10.8 Inductive Proofs of Recursive Programs – The Towers of Hanoi
There’s yet another reason that inductive proofs are so important, particularly to people who write code: When we write programs to solve problems that themselves have a natural recursive structure, the most straightforward way to reason about those programs is by induction.
Recall the Towers of Hanoi problem:
To solve this problem requires that we move all the disks from the starting pole to one of the other poles. But we must do that by following a few rules: Whenever a disk is removed from a pole, it must immediately be placed on some other pole. No disks may be placed on the ground or held. Further, a disk may never be placed on top of a smaller disk.
In some descriptions of this problem, we fix the number of disks, often at 64. But let’s consider what we’ll call the Generalized Towers of Hanoi problem: Find a way to do the job with any number of disks on the poles.
Recall that we proposed the following algorithm for solving this problem:
towersofHanoi(n: positive integer) = 1. If n = 1 then move the disk to the goal pole. 2. Else: 2.1. Use towersofHanoi(n-1) to move the top n-1 disks to the pole that is neither the current one nor the goal. 2.2. Move the bottom disk to the goal pole. 2.3. Use towersofHanoi(n-1) to move the n-1 disks that were just set aside to the goal pole.Summarizing in English what this procedure does: To move n disks, first move n-1 of them out of the way to the third pole. Next, move the bottom disk into place on the goal pole. Finally, move the remaining n-1 disks from their temporary location to the goal pole.
This algorithm is recursive: To move n disks, we first move a smaller number (n-1) of them out of the way. Of course to do that, we must start by moving (n-2) of them out of the way. And so forth.
And notice that, just as in an inductive proof, there is a base case that must be treated specially. In this case: to move exactly one disk, just move it.
Now consider the following claim about this problem and the program we have just written to solve it:
For any number of disks, n, it is possible to solve the problem in 2n – 1 moves.
Notice that we’re not claiming that it’s not possible to do better (although it is possible to prove that). We are claiming, though, that the problem isn’t worse than this.
Our argument that it is possible to solve the problem in 2n – 1 moves is going to be that the program we’ve just presented does so in exactly that number of moves.
Let’s prove the correctness of this claim about the computational complexity of our program.
The proof is by induction on n, the number of disks.
Call the number of moves required for n disks M(n). Then:
\(P(n) \equiv M(n) = 2^n - 1 moves.” \)Base case: n = 1. Our program requires exactly one move when there is one disk. So:
\(M(1) = 1 = 2^1 - 1 = 2^n - 1. \)Induction step: Assuming P(n), prove P(n+1). Analyzing the program, we see that M(n+1) (the total number of moves required to move n+1 disks), for n+1 > 1, is:
M(n+1) = M(n) + 1 + M(n)By the induction hypothesis, we have that M(n) = 2n – 1. So we can rewrite this as:
\begin{gather*} M(n+1) = (2n - 1) + 1 + (2n - 1) = 2 (2n - 1) + 1 \\ = 2n+1 – 1 \end{gather*}
