Lösung Türme von Hanoi

Für die Lösung der Aufgabe beginnt man mit kleinen n und betrachtet dann immer eine Scheibe mehr.
Es bietet sich z. B. an, mit  die Anzahl der optimalerweise benötigten Züge für eine Pyramide der Höhe  zu bezeichnen.

: triviales Problem
: Die kleine Scheibe wird auf 2 gelegt, die große auf 3 und dann die kleine auf 3.
: 1→3; 1→2; 3→2; 1→3; 2→1; 2→3; 1→3
: 1→2; 1→3; 2→3; 1→2; 3→1; 3→2; 1→2; 1→3; 2→3; 2→1; 3→1; 2→3; 1→2; 1→3; 2→3

Nach einigen  sieht man:

• Für einen Turm mit  Etagen wird zunächst analog vorgegangen wie für  Etagen, mit dem Unterschied, dass der Turm abzüglich der untersten Etage auf Stab 2 verschoben wird und nicht auf Stab 3. Hierfür benötigt man so viele Züge wie für den Fall .
• Im Anschluss wird die unterste Scheibe von 1 nach 3 bewegt, was einen weiteren Zug benötigt.
• Zuletzt wird der zuvor nach 2 verschobene Turm der Höhe  auf die Scheibe auf Stab 3 verschoben. Hierfür benötigt man abermals so viele Züge wie für den Fall

Es gilt also offenbar  und

Man sieht: