he Towers of Hanoi is a classic puzzle, as follows. There are three posts (the “towers”); post A starts with n concentric discs stacked from top-to-bottom in order of decreasing radius. We must move...

he Towers of Hanoi is a classic puzzle, as follows. There are three posts (the “towers”); post A starts with n concentric discs stacked from top-to-bottom in order of decreasing radius. We must move all the discs to post B, never placing a disc of larger radius on top of a disc of smaller radius. The easiest way to solve this puzzle is with recursion: (i) recursively move the top n − 1 discs from A to C; (ii) move the nth disc from A to B; and (iii) recursively move the n − 1 discs from C to B. The total number of moves made satisfies T(n) = 2T(n − 1) + 1 and T(1) = 1. Prove that T(n) = 2n − 1.