5. (25 points) Recall that a classical tower of Hanoi game is as follows: There are 3 rods A, B, C and n disks, where the disks are all in distinct sizes. Initially all disks are on rod A in the order of increasing sizes, the smallest on the top. The objective is to move all disks from rod A to rod B (where the disks in B are also in the order of increasing sizes), with the following rule: Each move takes the top disk from one rod and places that disk to the top of another rod, with the restriction that no larger disk can be placed on top of a smaller disk. (It is well-known that we can solve it recursively: First recursively move the top n - 1 disks from A to C, then move the last, largest disk from A to B, and finally recursively move the n - 1 disks from C to B. If Tn is the minimum number of moves to complete the task for n disks, then we have Tn = 0 when n = 0 and Tn = 2Tn-1 + 1 when n > 0.) Now consider the cyclic tower of Hanoi game: it is the original tower of Hanoi game with an additional restriction: a disk can only be moved from A to B, or from B to C, or from C to A. Under the new rules, let Qn be the minimum number of moves needed to transfer a tower of n disks from A to B, and Rn the minimum number of moves needed to transfer a tower of n disks from B to A. Prove that if n = 0, 2Rn-1+1 if n >0, and RES if n = 0, if n > 0. I Qn +Qn-1+1 (Note: You do not need to solve these recurrences.) (Hint: Think about new recursive algorithms.)