Du solltest dir zuerst überlegen, ob der Algorithmus für \(n=0\) (1 Scheibe) korrekt funktioniert. Das ist der Induktionsanfang.

Nimm dann an, dass der Algorithmus für \(n\) Scheiben korrekt funktioniert (Induktionsvoraussetzung). Nun musst du zeigen, dass dies auch für \(n+1\) Scheiben gilt (Induktionsschritt).  Dazu verwendest du in Zeilen 4 und Zeile 6 die Induktionsvoraussetzung, da ja hier jeweils \(n+1-1=n\) Scheiben bewegt werden. Du weißt also, dass der Algorithmus damit beginnt, \(\mathtt{MOVE(n,A,C,B)}\) aufzurufen. Nach Induktionsvoraussetzung funktioniert das korrekt, d.h. \(n\) Scheiben werden von \(A\) über \(C\) nach \(B\) verschoben. Was bewirken die restlichen Schritte? Kommt dann das richtige Ergebnis heraus?