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,