# Tower of Hanoi

## Problem

There is a tower of $n$ disks, stacked in decreasing size on one of $3$ pegs. The object of the exercise is to move the disks onto a different peg, obeying the rules:

$(1): \quad$ Only one disk can be moved at a time
$(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it.

How many moves are needed to move all the disks onto a different peg?

### Variant

$(1): \quad$ Only one disk can be moved at a time
$(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it
$(3): \quad$ The disks must all be moved from the peg $1$ to peg $3$
$(4): \quad$ A move consists of transferring a disk from the peg $1$ to peg $2$, or back, or from peg $2$ to peg $3$, or back
$(5): \quad$ No disk can cross over peg $2$ if it contains a smaller disk.

## Solution

For a tower of $n$ disks, it takes $2^n - 1$ moves.

## Proof

### Setting up a Recurrence Rule

Let $T_n$ be the number of moves needed to transfer $n$ disks from one peg to another.

Clearly we have:

$T_0 = 0$
$T_1 = 1$

Now, we note that in order to move a tower of $n$ disks, we need to do the following:

$(1): \quad$ Move the tower of $n - 1$ disks from off the top of the $n$th disk onto another of the pegs
$(2): \quad$ Move the $n$th disk to the destination peg
$(3): \quad$ Move the tower of $n - 1$ disks from where it was put temporarily onto the top of the $n$th disk.

It is clear that steps $1$ and $3$ above each take $T_{n - 1}$ moves, while step $2$ takes one move.

Hence we have:

$T_n \le 2 T_{n - 1} + 1$

The inequality applies here because we have established that although we know we can always get the job done in no more than $2 T_{n-1} + 1$ moves, we are not at this stage certain that there is not a better strategy which needs fewer moves.

So: is there a way of moving the disks that uses fewer moves?

Consider that at some point we need to move disk $n$.

When we do this, we must have moved the $n - 1$ disks above it onto a vacant peg. That must have taken $T_{n - 1}$ moves to do, whatever $T_{n - 1}$ happens to be.

Having moved that final disk for the first (and hopefully last) time, we then need to transfer the $n - 1$ smaller disks (which all need to be on a single peg, otherwise there won't be a spare peg to move disk $n$ onto) back onto disk $n$. This also takes $T_{n - 1}$ moves to do.

So now we see that there is not a better way to move the disks, i.e.:

$T_n \ge 2 T_{n - 1} + 1$

Thus we arrive at our recurrence rule:

$T_n = 2 T_{n - 1} + 1$

### Solution of Recurrence

Using induction, we show that $T_n = 2^n - 1$.

The base case is straightforward:

$T_0 = 0 = 2^0 - 1$
$T_1 = 1 = 2^1 - 1$

Now assume the induction hypothesis:

$T_k = 2^k - 1$

and try to show:

$T_{k + 1} = 2^{k + 1} - 1$

Hence the induction step:

 $\displaystyle T_{k + 1}$ $=$ $\displaystyle 2 T_k + 1$ $\displaystyle$ $=$ $\displaystyle 2 \left({2^k - 1}\right) + 1$ $\displaystyle$ $=$ $\displaystyle 2^{k + 1} - 2 + 1$ $\displaystyle$ $=$ $\displaystyle 2^{k + 1} - 1$

Hence the result by induction.

$\blacksquare$