Crucial insight: in order to move all n disks from pole A to pole B, you must first move the top n-1 disks from A to C so that youcanmove the bottom disk. Then, of course, you move that bottom disk from A to B, then move the n-1 disks from C to B. If M(n) is the number of moves required to move n disks from one pole to another, M(n)= M(n-1)+ 1+ M(n-1)= 2M(n-1)+ 1.