There are three pegs on a board. On one peg are n disks, each smaller than the one on which it rests. The problem is to move this pile of disks to another peg. The final order must be the same, but you can move only one disk at a time and can never place a larger disk on a smaller one.

a) What is the smallest number of moves needed to move 3 disks? 4 disks? 2 disks? 1 disk?
b) Conjecture a formula for the smallest number of moves needed to move n disks. Prove it by mathematical induction.