Quote:

1. *Tower of Hanoi with Adjacency Requirement*. Suppose that in addition to the requirement that they neer move a larger disk on top of a smaller one, the priests who move the disks of the Tower Hanoi are also required to move disks one by one from one pole to an adjacent pole. Assume poles A and C are at the two ends of the row and pole B is in the middle. Let

an = the minimum number of moves needed to transfer a tower of n disks from pole A to pole C.

The recurrence relation for ak is then ak = 3ak-1+2.

Now let

bk=the minimum number of moves needed to transfer a tower of n disks from pole A to pole B.

a. Find b1, b2, and b3.

b. Show that bk=ak-1+1+bk-1 for all integers k>=2.

c. Show that bk <= 3bk-1+1 for all integers k>=2.