Recall the Towers of Hanoi problem that we discussed in class. Given
3 needles and n graduated disks on one of the needles, the goal is to
move all of the disks from one needle to another
subject to the following rules:
- Only one disk can be moved at a time.
- A larger disk can never be placed on top of a smaller disk.
If M(n) is the number of moves required to move n disks from one
needle to another under the rules above,
- Write a recurrence relation
and initial condition for M.
- Use the expand-guess-verify method to find a closed form solution for M.