Lesson 2

Let the minimum number of moves be denoted by \(M(n)\). Clearly, \(M(1)=1\). It is easy to see that \(M(n) \leq 2M(n-1)+1\): first, move the top \(n-1\) disks (this takes \(M(n-1)\) moves; the largest disk does not interfere), then move the largest disk to the free rod (one move), and finally move the \(n-1\) disks onto the largest disk (another \(M(n-1)\) moves). This gives an upper bound for \(M(n)\).

A lower bound \(M(n) \geq 2M(n-1)+1\) can also be proved. Consider the first moment when the largest disk is moved. At this moment, the rod containing the largest disk has only that disk; there is also an empty rod (since the largest disk can only be moved to an empty rod); therefore, all other disks must be on the remaining rod. This means that at least \(M(n-1)\) moves were spent up to this point.

After this, the largest disk is moved. We again need to move all \(n-1\) disks, requiring at least \(M(n-1)\) moves.

This leads to the recurrence relation: \[M(1)=1, \quad M(n)=2M(n-1)+1 \ .\]