Fibonacci

Fast richtig

Zwischen 3 aufeinanderfolgenden Fibonaccizahlen mit ungeradem Index gibt es die Relation
F_2n+3F_2n-1 - F_2n+1² = 1
Beweis: (für diejenigen die bekannt sind mit Matrizen)
Man kann dies auf eine nette Weise mittels Matrizen und Determinanten zeigen.
Die nächste Matrixrelation ist einfach durch Induktion zu beweisen.

Berechne nun die Determinante vom linken und rechten Glied.

Wir dividieren oben stehende Formel durch F_2n-1F_2n+1. Das gibt:
F_2n+3/F_2n+1 - F_2n+1/F_2n-1 = 1/(F_2n-1F_2n+1)

Das besagt für die Folge der Fibonaccizahlen mit ungeradem Index 1,2,5,13,34,... dass der Quotient zweier aufeinanderfolgenden Zahlen aus dieser Zahlenfolge ständig wächst (das heißt F_2n+3/F_2n+1 > F_2n+1/F_2n-1 für alle n).
Ausserdem: Wenn wir von einer Zahl aus dieser Zahlenfolge 1 substrahieren, (also F_2n+3 ersetzen durch F_2n+3-1), dann ist diese Eigenschaft nicht mehr erfüllt
(denn (F_2n+3-1)/F_2n+1 - F_2n+1/F_2n-1 = 1/(F_2n-1F_2n+1) - 1/F_2n+1 ≤ 0 )


Wir betrachten jetzt im allgemeinen Zahlenfolgen a₁, a₂, a₂, ... mit der Eigenschaft
a_n+2/a_n+1 > a_n+1/a_n und (a_n+2-1)/a_n+1 ≤ a_n+1/a_n (für n > 0).
Wenn wir die ersten zwei Terme einer solchen Zahlenfolge kennen, können wir anhand dieser zwei Formeln alle übrige Terme berechnen. Wenn a₁ = 1 und a₂ = 2, dann bekommen wir die oben erwähnte Folge von Fibonaccizahlen mit ungeradem Index. Wenn wir mit zwei anderen Fibonaccizahlen anfangen, a₁ = 8 und a₂ = 55, dann bekommen wir eine Zahlenfolge die anscheinend der nächsten Recursion genügt
a_n+4 = 6a_n+3 + 7a_n+2 - 5a_n+1 - 6a_n.
Anscheinend, denn es stellt sich heraus dass die Formel nur richtig ist für die ersten 11056 Terme. Dann geht alles daneben.


Für diese Rekursion a_n+4 = 6a_n+3 + 7a_n+2 - 5a_n+1 - 6a_n gilt (in Übereinstimmung mit Methode 3) dass der Quotient a_n+1/a_n mit wachsendem n-Wert gegen eine Nullstelle der Gleichung
x⁴ - 6x³ - 7x² + 5x + 6 = 0 konvergiert.
Diese Gleichung hat zwei reelle Nullstellen. Mit einem Taschenrechner kann man prüfen dass
x⁴ - 6x³ - 7x² + 5x + 6 = (x - c₁)(x - c₂)(x² + d₁x + e₁) mit c₁ > 1 und -1 < c₂ < 1 und 0 < e₁ < 1.
Nun ist c₁ⁿ für große n-Werte fast eine ganze Zahl. Wir werden dies gleich anhand eines anderen Beispiels verdeutlichen.
Noch allgemeiner gilt dass wenn ein Polynom x^k + d_k-1x^k-1 + ... + d₁x + d₀ mit ganzen Koeffizienten und m reellen Nullstellen in
(x - c₁)(x - c₂)...(x - c_m)(x² + d₁x + e₁)...(x² + d_k-mx + e_k-m)
zergliedert wird und wenn c₁ > 1 und -1 < c_i < 1 für 1 < i ≤ m und 0 < e_i < 1 für i ≤ k-m, (also alle Nullpunkte bis auf eins liegen innerhalb des Einheitskreises)
dann is c₁ⁿ für große n-Werte fast eine ganze Zahl (was mit Hilfe der Methode aus Ein algebraisches Verfahren zu zeigen ist).
Wir nehmen ein konkretes Beispiel.
Für die Fibonacci-Rekursion F_n+2 = F_n+1 + F_n (und die Lucas-Rekursion L_n+2 = L_n+1 + L_n) gilt (sieh Methode 3) dass der Quotient F_n+1/F_n (L_n+1/L_n) mit steigendem n-Wert zu einem Nullpunkt der Gleichung
x² - x - 1 = 0 strebt.
Die Nullpunkte dieser Gleichung sind c₁ = (1+5)/2 und c₂ = (1-5)/2.
Also x² - x - 1 = (x - c₁)(x - c₂) mit c₁ > 1 und -1 < c₂ < 1.
Nun sind F_n = (c₁ⁿ - c₂ⁿ)/(c₁ - c₂) = c₁ⁿ/5 - c₂ⁿ/5 und
L_n = c₁ⁿ + c₂ⁿ ganze Zahlen.
-1 < c₂ < 1 also c₂ⁿ ist für große n-Werte fast gleich 0, also (schreibe φ für c₁)
φⁿ/5 ist etwa gleich F_n (eine ganze Zahl) und φⁿ ist etwa gleich L_n (eine ganze Zahl).
Zum Beispiel, φ¹⁰⁰⁰/5 enthält 209 Ziffern vor dem Komma; die erste 209 Ziffern hinter dem Komma sind gleich 0.
Bei φ¹⁰⁰⁰ sind die ersten 209 Ziffern hinter dem Komma Neunen.
Das ist eine besondere Eigenschaft, denn für fast jede irrationale Zahl p (= nicht-Bruch p) sind die Zahlen pⁿ-int(pⁿ) gleichmäßig über das Intervall (0,1) verteilt.
(Mit pⁿ-int(pⁿ) ist gemeint dass wir den Teil vor dem Komma durch eine 0 ersetzen.)

Betrachten wir noch einmal die besonderen Polynome die uns freundlicherweise einen Nullpunkt c₁ mit der aussergewöhnlichen Eigenschaft liefern, dass c₁ⁿ für große ganze n-Werte beinahe eine ganze Zahl ist.
Also die Polynome x^k + d_k-1x^k-1 + ... + d₁x + d₀ mit ganzen Koeffizienten und (sage) m reellen Nullpunkten und mit der Zerlegung (x - c₁)(x - c₂)...(x - c_m)(x² + d₁x + e₁)...(x² + d_k-mx + e_k-m)
wobei c₁ > 1 und -1 < c_i < 1 für 1 < i ≤ m und 0 < e_i < 1 für i ≤ k-m.
Von allen Polynomen mit diesen Eigenschaften gibt es genau eines dass die kleinst mögliche c₁ liefert (Wir werden diesen c₁-Wert c_min nennen). Es ist das Polynom x³ - x - 1.
c_min ist ein einsamer Punt, damit meine ich, dass es eine kleine positive Zahl s gibt so dass zwischen c_min-s und c_min+s keine c₁-Werte irgendeines Polynoms von oben erwähnter Sorte vorkommen.
Betrachte jetzt die Menge der mögelichen c₁-Werte und entferne daraus alle einsame Punte. Dann bleibt eine Menge c₁-Werte übrig, wovon der kleinste der goldene Schnitt ist, also eine Nullstelle von x² - x - 1 = 0.