Show that each of the following rules for playing the Tower of Hanoi works and state the initial conditions for each recursive relation:

(a) On odd-numbered moves, move the smallest ring clockwise one peg (think of the pegs being at the corners of a triangle), and on even-numbered moves, make the only legal move not using the smallest ring.

(b) Number the rings from 1 to n in order of increasing size. Never move the same ring twice in a row. Always put even-numbered rings on top of odd numbered rings (or on an empty peg) and put odd-numbered rings on top of even-numbered rings (or on an empty peg).