I've been reading through an inductive proof on why the minimum number of moves in a Tower of Hanoi with n disks is $2^n -1$. The proof is based on the fact that the minimum amount of moves for $k+1$ disks is $2T(k) + 1$: $T(k+1) =2T(k)+1$.
I understand that this is because you need to move the top $k$ disks to the center post, which can be done in a minimum of $T(k)$ moves. Then, you need to move the bottom disk to the final post, which can be done in $1$ move. Finally, you need to move the top $k$ disks to the final post, which can be done in a minimum of $T(k)$ moves.
But what I don't understand is why this method of moving disks is the quickest: why isn't there a method of moving disks that is quicker than this, that requires less moves? I haven't been able to devise a method that is quicker than the above, but that doesn't show that the method above is the quickest either!
So my question is, why is this method of moving disks the quickest? How can it be proved?
Thanks in advance.
Best Answer
Here is a reply to the OP's comment:
For $1$ disk, the quickest way is by moving the disk to the rightmost pole, which takes $1$ move.
For $2$ disks, we have one disk on top, which we already figured out how we can move the quickest. We first move the disk on top, then move the disk on the bottom to the final position, then move the disk on top to the final position.
For $3$ disks, consider the top $2$ disks as one object, where we know the quickest way to move the $2$ disks. Then we have to move the bottom disk and the top two disks, which we can treat as two separate objects, and we proceed in the same way like we had with $2$ disks.
In general, given $n$ disks, the top $n-1$ disks are one object which we cannot move any faster. Then by adding another disk on the bottom, we can extend the quickest way of moving to $n$ disks. In other words, we can successively reduce a problem involving $n$ disks to a problem that only includes $2$ objects.
What justifies all of this is that we know the 'fastest method' you mentioned works for $n = 1$. Induction proves that given the base case $n=1$ holds, the next case holds. Repeating the process of induction arbitrarily many times ensures that this can be proved for any $n$.