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. Our problem is a variant of the Towers of Hanoi puzzle: 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.(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. (Hint: You may find it useful to also introduce a quantity S(n)for the least number of moves needed to move n pegs from tower 0 to tower 1.)(d) Prove inductively that T(n)≥(√3 + 1)n−1, for all n≥1.