es geht um eine Induktionsaufgabe bezüglich der Türme von Hanoi. Die Aufgabe ist ja alt und schon bekannt, daher hier meine Abwandlung: Ich habe einen Algorithmus gegeben und soll nun beweisen, dass dieser das Umlegen der Türme in Minimalzeit berechnet.
Mein Ansatz für die Induktion wäre es, einmal zu zeigen, dass der Algorithmus mindestens eine Laufzeit von 2^n-1 hat und danach mit einer zweiten Induktion zu zeigen, dass der Algorithmus höchstens eine Laufzeit von 2^n-1 hat. Ist das grundsätzlich richtig?
Mir fehlt nämlich komplett der Ansatz, da wir bis dato nur herkömmliche (einfache) Induktionen gemacht haben. Hat jemand Rat?