Data Structures, Algorithms, & Applications in C++
Chapter 8, Exercise 19
For the induction base we use n = 0.
For this number of disks the program requires no disks to be
moved and so works correctly. For the induction hypothesis, assume
that the program is correct when
the number of disks is some arbitrary nonnegative integer
m. In the induction step we must show that
the program works correctly when the number of disks is
m + 1.
When the number of disks is
m + 1, the program first moves the top
m disks from tower
x to tower
z using tower
y for intermediate storage. The program completely
ignores the fact that disk
m + 1 is at the bottom of tower
x. From the induction hypothesis we conclude that
the program correctly moves the top
m disks to tower
z except possibly for errors caused by the
presence of disk
m + 1 is at the bottom of tower
x. Since disk
m + 1 is the largest disk it can cause no errors.
Next, disk
m + 1 is moved to tower
y. Since this tower has no disk on it, this
move of disk
m + 1 is legal.
Finally the program moves disks 1 through
m from tower
z to tower
y completely ignoring the fact that disk
m + 1 is at the bottom of tower
y. From our correctness proof for the moving
of the top
m disks from tower
x to tower
z, it follows that the moving of these disks
from tower
z to tower
y is done correctly.