Suppose the Tower of Hanoi rules are changed so that the stones may only be transferred to an adjacent clearing in one move. Let In be the minimum number of moves required to transfer tower from clearing A to clearing C?
Find a recursive relation for In.
Guess a formula for In.