10. The Tower of Hanoi is a puzzle consisting of a board withthree dowels and a collection of n disks of n different radii. Thedisks have holes drilled through their centers so they can fit onthe dowels on the board. Initially, all the disks are on the firstdowel arranged in order of their sizes, with the largest one beingat the bottom, and the smallest one on the top. The object is tomove all the disks to another dowel in as few moves as possible.Each move consists of taking the top disk from one of the stacksand placing it on another with the added condition that you may notplace a larger disk on top of a smaller one. Prove: For every n ?1, the Tower of Hanoi puzzle with n disks can be solved in 2^n ? 1moves.
