De torens van Hanoi.
 
Het spel staat elders op deze website (hier) beschreven.
Je kunt het on-line oefenen op  http://www.cut-the-knot.org/recurrence/hanoi.shtml.

We bewijzen met  inductie de volgende stelling:

Om een toren van n schijven te verplaatsen
zijn 2n - 1 zetten nodig.
Voor n = 1 klopt ie:  een toren van 1 schijf verzet je in 1 zet.

Stel dat de stelling klopt voor een toren van n schijven.
Neem nu een toren van n + 1 schijven.
Die verplaats je als volgt:

1. Zet de toren van de bovenste n schijven naar de naastgelegen plaats.
Dat kost 2n - 1 zetten
2. Zet de onderste schijf naar de derde plaats.  Kost 1 zet
3. Verplaats de toren van n schijven van de naastgelegen naar de derde plaats.
Dat kost weer 2n - 1 zetten.

Samen kost dat dus  (2n - 1) + 1 + (2n - 1) = 2 • 2n  - 1 =   2n + 1 - 1 zetten