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.
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.