The Towers of Hanoi puzzle has 3 towers labeled 0,1, and 2. There are n pegs of sizes 1 to n, initially placed on tower 0 from top to bottom in increasing order of their sizes. The goal of the well-known puzzle is to move all n pegs to another tower, say tower 2. One can only move one peg at a time, and move the top peg on a tower to be placed on the top of another tower, and cannot place a larger peg on top of a smaller peg. The question is, what is the smallest number of moves needed. The three towers are still labeled 0, 1, and 2. There is one additional constraint: You are only allowed to move pegs from a tower labeled i to the next one labeled (i+1) mod 3. You can imagine the towers as being arranged in a circular fashion, in which case, the constraint says that you can only move pegs in an anti-clockwise manner. So, for example, in order to move a peg from tower 0 to tower 2, you would have to first move it to tower 1 (if both 0 → 1 and 1 → 2 are legal moves at this point), and this sequence would cost two moves instead of just one

Required:
a. Prove that starting at any legal configuration, there is at least one legal move.
b. Inductively prove that for any n≥1, this variant of the Towers of Hanoi puzzle (the goal is still moving all n pegs from tower 0 to tower 2) has a solution (consisting of finitely many legal moves.)
c. Give a recurrence of T(n), the least number of moves needed for this variant of the Towers of Hanoi puzzle with n pegs.