Recursion

a. Write a recursive algorithm for the Towers of Hanoi problem in pseudocode. Assume that there are n disks with diameters 1 cm, 2 cm, 3 cm, , n cm (from top disk to bottom disk). They need to be moved from peg A to peg B using peg C as a buffer. Only one top disk can be moved at a time from one peg to another; a bigger disk should never be placed above a smaller disk.

b. Prove that the number of disk moves is 2ⁿ -1 using the method of Mathematical Induction. It should be based on your pseudocode, and all three steps of Mathematical Induction should be shown.