Aufgabe: Anwendung des Euklidischen Algorithmus auf Fibonacci Zahlen - Laufzeit: Beweis für k größer 2; Schritte des Euklidschen-Algorithmus stets (k-1) wenn Zahlenpaar (f_k und f_k+1)
Problem/Ansatz:
Die Fibonacci Folge sei gegeben für n größer 0 durch: f_n+2=(f_n)+(f_n+1) f_0=0, f_1=1
Beweisen Sie für k größer 2: Schritte des Euklidschen-Algorithmus stets (k-1) ; Anwendung auf Zahlenpaar (f_k und f_k+1)
Ich habe ein wenig Bücher gewälzt und dort stand, dass sich dieser Zusammenhang aus dem Satz von Binet ergibt. Mit ist jedoch nicht ganz klar, inwieweit die Verallgemeinerung des Determinantenproduktsatzes auf diesen Zusammenhang hindeutet. Über Hilfe oder Tipps zu diesen Zusammenhang wäre ich sehr dankbar.
Mein eigner Ansatz lautet wie folgt:
F_1=F_2=1
Anzahl der Schritte des Euklid Algorithmus können geschrieben werden als:
n-ter Quotient=q_n
n-ter Rest= r_n
r_n-2=(q_n)(r_n-1)+r_n n=1,2,3,.....k
wenn r_-1=a r_0=b
r_n-2, r_n-1, r_n,q_n sind Elemente der natürlichen Zahlen ; q_n ist Element von N_0 (ich müsste mal rausfinden wie ich das Zeichen für natürliche Zahlen nicht als normales N schreiben kann...)
Für alle Paare von natürlichen Zahlen existiert demnach eine Zahl e, die die Schritte des Euklid Algorithmus repräsentiert e(a,b)
Ergibt das für euch Sinn?
