(6) Suppose the Tower of Hanoi rules are changed so that stones may only be transferred
to an adjacent clearing in one move. Let Isubn 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 Isub1 = 2
(a) By brute force, determine Isub2; and Isub3.
(b) Find a recursive relation for Isubn.
(c) Guess a formula for Isubn.

Question

(6) Suppose the Tower of Hanoi rules are changed so that stones may only be transferred
to an adjacent clearing in one move. Let Isubn 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 Isub1 = 2
(a) By brute force, determine Isub2; and Isub3.
(b) Find a recursive relation for Isubn.
(c) Guess a formula for Isubn.

anonymous · Answer

Can someone tell me why (b) is f(n) = 3 f(n-1) + 2