The first ten students who turn in solutions to the following problem (deadline: September 14, 9:30 am) get 20 extra credit points.

Given are three pegs standing next to each other. On the first peg there are n rings of different size, the largest one on the bottom, then the second largest one, and so on, the smallest one on the top. The problem is to find the minimum number of moves (denote this number by y_n) required to move all n rings from the first peg to the third peg. A move consists of transferring a single ring from one peg to another with the restriction that a larger ring may not be placed on a smaller ring.

• Find y_1, y_2, y_3, and y_4. Sketch pictures of each starting position, intermediate positions, and final position. There is one intermediate position that will occur in any case. Which one? Sketch this intermediate position, together with the starting and the final positions for n=5.
• Come up with a recurrence relation for y_n.
• Solve it to obtain y_n for any natural number n.