1. (25 points) Consider the game of Hanoi-Tower, where on a board with three erected pegs pile of disks of different sizes are initially stacked at one of the pegs, in a size-ordered manner with the largest disk being at the bottom and on top the smallest.

The player is required to relocate the disk pile to any of the rest two pegs, in compliance with the following rules at any time during the play:

• moving one disk at a time from one peg to another;
• when moving a disk to a peg already piled with disks, the disk must be smaller than any in the pile (which would entail that, during the game, a disk pile at any peg will be size-ordered with smaller ones on top of larger ones);

a. (2 points) Suppose that $H^3(n)$ is the number of moves required to relocate a pile of $n$ disks at a peg to any of the rest two pegs. How would you formulate $H^3(n)$ in a recursive manner? And $H^3(n) = ?$

b. (3 points) The game can be extended to the case of 4-peg. Suppose that $H^4(n)$ denotes the number of moves needed to relocate a pile of $n$ disks at a peg to any of the rest three pegs. How would you formulate $H^4(n)$ in a recursive manner? And $H^4(n) = ?$ Is there any connection that you see between $H^3(n)$ and $H^4(n)$?

c. (10 points) Let $H^5(n)$ be the number of moves for relocating a pile of $n$ disks in 5-peg situation. Are there any connections that you see among $H^3(n)$, $H^4(n)$ and $H^5(n)$?

d. (10 points) What can you tell about $H^m(n)$ in the case of an $m$-peg Hanoi-Tower game? And the connections between $H^{m_1}(n)$ and $H^{m_2}(n)$?