In the Tower of Hanoi puzzle, suppose our goal is to transfer all $n$ disks from peg $1$ to peg $3,$ but we cannot move a disk directly between pegs $1$ and $3.$ Each move of a disk must be a move involving peg $2.$ As usual, we cannot place a disk on top of a smaller disk.
- Find a recurrence relation for the number of moves required to solve the puzzle for n disks with this added restriction.
- Solve this recurrence relation to find a formula for the number of moves required to solve the puzzle for n disks.
- How many different arrangements are there of the n disks on three pegs so that no disk is on top of a smaller disk?
- Show that every allowable arrangement of the n disks occurs in the solution of this variation of the puzzle.
