Chapter 8.5, Problem 40E

Tower of Hanoi The result in Exercise 39 suggest that the minimum number of moves required to transfer n disks from one peg to another is given by the formula $2^n-1$. Use the following outline to prove that this result is correct using mathematical induction.

a) Verify the formula for $n=1$.

b) Write the induction hypothesis.

c) How many moves are needed to transfer all but the largest of $k+1$ disks to another peg?

d) How many moves are needed to transfer the largest disk to an empty peg?

e) How many moves are needed to transfer the first k disks back onto the largest one?

f) How many moves are needed to accomplish steps c, d, and e?

g) Show that part f can be written in the form $2^{\left(k+1\right)}-1$.

h) Write the conclusion of the proof.