Associated Topics || Dr. Math Home || Search Dr. Math

### 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.)

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/
```
Associated Topics:
High School Number Theory
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search