Suppose we’ve got the Tower of Hanoi puzzle with three pegs and discs. We will show that for the usual starting and finishing configurations of discs, all discs sitting on one peg, the shortest solution involves
moves. For any other pair of starting configurations the shortest solution involves at most
moves.
First let’s consider the game with one disc. Clearly solving the puzzle only involves one move. Since the result is true for
.
Now suppose you’re playing the game with discs using the usual starting and finishing configurations and assume that the result is true for the
-disc version of the game: the smallest number of moves required is
To solve the
-disc version, first move the
smaller discs onto one of the free pegs using the shortest method which takes
moves. Now move the largest disc onto the remaining free peg. Then shift the
-tower on top of it, again using the method that takes
moves. You’ve now solved the puzzle in
moves. It’s easy to see that this is the shortest solution as you cannot get away from moving the
-tower at least twice and the largest disc at least once. Therefore, the shortest number of moves required to solve the
-disc version of the game is
![]() |
This shows that if the result is true for it is true for
. So we have proved by induction that the result is true for all
.
Now suppose you are playing the game with arbitrary starting and finishing configurations of discs. We will show that at most moves are required to solve the puzzle.
Again we start with in which case there are only three possible configurations separated pairwise by one move. So the result is true.
Now assume it is true for and see what happens for
.
In the Hanoi graph write
and
for the nodes representing the starting and finishing configurations respectively and write
for the length of the shortest path taking you from
to
. (By the length of the path we mean the number of edges it traverses.) The Hanoi graph
consists of three copies of the Hanoi graph
joint pairwise by one edge. If
and
lie within the same copy of
then
![]() |
by our hypothesis that the result is true for . Suppose they lie in two different copies, copy 1 and copy 2 of
. You can get from
to
by moving from
to the vertex in copy 1 that is linked to copy 2, traversing the linking edge and then moving to
within copy 2. By our assumption that the result is true for
the first and the last part of this route have length at most
. Thus,
![]() |
QED