Die Türme von Hanoi

"Die Türme von Hanoi" ist ein Spiel, bei dem ein Stapel gelochter Ringe von einem Stab auf einen anderen umgesetzt werden soll wobei

• bei einem Schritt nur eine Scheibe umgesetzt werden darf,
• nie eine größere Scheibe auf einer kleineren zu liegen kommt.

Bei n Scheiben ist die kleinste Zahl von Schritten, die zum Umsetzen nötig sind 2ⁿ-1.

Beweis durch vollständige Induktion:

Zum Umsetzen von n Scheiben seien S_n Schritte nötig.

Um n +1 Scheiben umzusetzen muss man die obersten n Scheiben umsetzen, dazu sind Sn Schritte nötig.

Dann setzt man die verbleibende Scheibe um, dazu ist ein weiterer Schritt nötig.

Schließlich setzt man die n Scheiben auf diese Scheibe. Dazu sind wieder Sn Schritte nötig.

Das ergibt die Rekursionsformel S_n+1 = 2·S_n + 1. Laut Induktionsvoraussetzung gilt S_n = 2ⁿ-1.
Für eine Scheibe ist ein Schritt nötig. 2¹-1 = 1 Die Formel stimmt also für n=1
Setzt man in die Rekursionsformel die Induktionsvoraussetzung S_n = 2ⁿ-1, ergibt sich S_n+1 = 2ⁿ⁺¹-1. Somit gilt die Formel für alle n.