Suppose the Tower of Hanoi rules are changed so that 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? For example, it takes two moves to move a one stone tower from A to C: One move from A to B, then a second move from B to C. So I1 = 2
(a) By brute force, determine I2, and I3. (b) Find a recursive relation for In.
(c) Guess a formula for In.

Question

Suppose the Tower of Hanoi rules are changed so that 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? For example, it takes two moves to move a one stone tower from A to C: One move from A to B, then a second move from B to C. So I1 = 2
(a) By brute force, determine I2, and I3. (b) Find a recursive relation for In.
(c) Guess a formula for In.