In: Advanced Math
10. The Tower of Hanoi is a puzzle consisting of a board with three dowels and a collection of n disks of n different radii. The disks have holes drilled through their centers so they can fit on the dowels on the board. Initially, all the disks are on the first dowel arranged in order of their sizes, with the largest one being at the bottom, and the smallest one on the top. The object is to move all the disks to another dowel in as few moves as possible. Each move consists of taking the top disk from one of the stacks and placing it on another with the added condition that you may not place 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 − 1 moves.