Thread: hanoi towers,induction

need help on this one!

prove that (using mathematical induction) Hanoi Towers Game with n disks cannot be solved in less than 2^n -1 moves.

thnx in advance.

Originally Posted by baz

need help on this one!

prove that (using mathematical induction) Hanoi Towers Game with n disks cannot be solved in less than 2^n -1 moves.

thnx in advance.

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 you can move 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.