Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and n disks of different sizes. The object is to move the disks that are...

Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The
Towers of Hanoi problem consists of three pegs and n disks of different
sizes. The object is to move the disks that are stacked, in decreasing order of
their size, on one of the three pegs to a new peg using the third one as a
temporary peg. The problem should be solved according to the following
rules: (1) when a disk is moved, it must be placed on one of the three pegs;
(2) only one disk may be moved at a time, and it must be the top disk on one
of the pegs; and (3) a larger disk may never be placed on top of a smaller
disk.
(a) Show for your algorithm that S (n) = 2
n − 1. (Here S (n) denotes the
number of steps (moves), given an input of n disks.)
(b) Prove that any other algorithm takes at least as many moves as given in