(The Towers of Hanoi) Ada is playing a game consisting of three vertical needles on which disks of different sizes can be placed. In the initial configuration, $n$ disks are placed on the left needle, the widest at the base and the others, increasingly narrower, stacked to the top. Ada can move the disks from one needle to another by following two rules: she can only move one disk at a time, and she cannot place a disk on a smaller disk. Can Ada succeed in moving all the rings to the right needle? If so, what is the minimum number of moves required?
Let $u_{n}$ be the minimum number of moves required to transfer a column of size $n$ from one peg to another. To transfer a column of size $n+1$ from the left peg to the right peg, it is necessary to move the top $n$ disks to the middle peg, then move the largest disk to the right peg, and finally move the $n$ other disks on top of it. This allows us to derive the following recurrence relation: $u_{n+1}=2 u_{n}+1$. We initialize with $u_{1}=1$, and we can prove by induction that $u_{n}=2^{n}-1$ (the base case is obvious, and the inductive step works because $\left.2\left(2^{n}-1\right)+1=2^{n+1}-1\right)$. It is not possible to do better because to move the largest disk from left to right, it is necessary to go through a configuration where all the other disks are in the middle.