A puzzle called the Towers of Hanoi consists of a board with 3 pegs and several disks of...

A puzzle called the Towers of Hanoi consists of a board with 3 pegs and several disks of differing diameters that fit over the pegs. In the starting position all the disks are placed on one peg, with the largest at the bottom, and the others with smaller and smaller diameters up to the top disk (see the figure). A move is made by lifting the top disk off a peg and placing it on another peg so that there is no smaller disk beneath it. The object of the puzzle is to transfer all the disks from one peg to another.

With a little practice, perhaps using coins of various sizes, you should convince yourself that if there are 3 disks, the puzzle can be solved in 7 moves. With 4 disks, 15 moves are required. Use the PMI to prove that with n disks, the puzzle can be solved in 2ⁿ – 1 moves. (Hint: In the inductive step you must describe the moves with n + 1 disks, and use the hypothesis of induction to count them.)