Aufgabe:
Es seien r0, r1 ∈ N mit r0 > r1 und r1 < Fk+1 (= k + 1-te Fibonacci-Zahl) für ein k ≥ 2. Dann erfüllt die Anzahl n der Schritte im Euklidischen Algorithmus (mit rn+1 = 0 und rn = ggT(r0, r1))
n ≤ k − 1.
Problem/Ansatz:
Beweis durch Induktion. Allerdings versteh ich nicht was genau ich zeigen muss. Also mir fehlt der induktionsanfang