Towers of Hanoi

Date: 10/08/2000 at 10:22:15
From: Rakesh
Subject: Towers of Hanoi formula and how to get there

What is the general formula for finding the fewest number of moves 
required to finish Towers of Hanoi with n disks, apart from 2^n - 1? I 
also need to know how to prove it works and how you got there.

Thank you.

Date: 10/08/2000 at 10:35:39
From: Doctor Anthony
Subject: Re: Towers of Hanoi formula and how to get there

The rules for Towers of Hanoi can be found our "Towers of Hanoi" FAQ:

   http://mathforum.org/dr.math/faq/faq.tower.hanoi.html   

The formula for the minimum number of moves with 3 pegs and n discs is
2^n - 1. 

The recurrence relation that leads to this result is  

     u(n) = 2*u(n-1) + 1   .....................................[1]

where u(n) is number of moves with n disks present.

To see this, note that to transfer n disks to another peg we must 
first transfer the top n-1 disks to the third peg (taking u(n-1) 
moves) then transfer the largest disk to a vacant peg (1 move) and 
then transfer n-1 disks back to the peg with the largest disk (taking 
another u(n-1) moves.)

Adding these moves we get  

     u(n-1) + 1 + u(n-1) = 2*u(n-1) + 1

Solving this recurrence relation gives 

     u(n) = 2^n - 1

To prove this result you can either use a descending series of partial 
sums based on the recurrence relation (1) above, leading to 

     1 + 2 + 2^2 + 2^3 + ..... + 2^(n-1) = (2^n -1 )/(2-1) = 2^n - 1

or you can prove the result by induction.

Inductive Proof
---------------
First show that the formula is true for n = 1. 

For n = 1 the formula gives 2^1 - 1 = 1 and that is correct.

Next assume it is true for some value n = k, that is we assume the 
truth of

     u(k) = 2^k - 1

Now add one more disk, so that n = k+1.

From the recurrence relation (1) we have

     u(k+1) = 2*u(k) + 1
            = 2(2^k - 1) + 1
            = 2^(k+1) - 2 + 1
            = 2^(k+1) - 1

and this is the same equation we had before, except that k is replaced 
by k+1. So if the result is true for n = k, then it is true for 
n = k+1. But it is true for n=1, therefore it will be true for n = 2, 
and if true for n = 2 it will be true for n = 3, and so on to all 
positive integral values of n, by the Principle of Mathematical 
Induction.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/