0 Daumen
319 Aufrufe

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

Avatar von

1 Antwort

0 Daumen

Der Induktionsanfang wird für k=2 gemacht.

Avatar von 53 k 🚀

Ja aber für welche Funktion? Wo setzt ich das k bzw das n ein?

Das ist mein Problem. Ich versteh die Aufgaben Stellung nicht wirklich.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community