Fibonacci

Beweis:

Im vorigen Beweis wurde gezeigt, dass die Anzahl Einsen in den ersten k Gliedern der Reihe 1 0 1 1 0 1 0 1 1 0 1 1 ... gleich [(k+1)/φ ist.
Wir werden nun zeigen, dass die Anzahl Nullen in den ersten k Gliedern gleich S(k) = [(k+1)/φ²] ist.
Wir wollen also zeigen dass [(k+1)/φ + [(k+1)/φ²] = k.
[(k+1)/φ + [(k+1)/φ²] =
[(k+1)(φ-1)] + [(k+1)(2-φ)] =
[(k+1)φ - (k + 1) + 2(k + 1) - [(k+1)φ - 1 = k.
Das k-te Glied der Reihe ist Null, dann und nur dann wenn S(k) - S(k-1) = 1.
Wir werden nun zeigen dass S(k) - S(k-1) = 1 dann und nur dann wenn man k schreiben kann als [nφ²] für eine gewisse ganze Zahl n.
S(k) - S(k-1) = [(k+1)/φ²] - [k/φ²].
S(k) - S(k-1) = 1 dann und nur dann wenn [k/φ²] < [(k+1)/φ²]
oder wenn es eine ganze Zahl m gibt so, dass k/φ² < m < (k+1)/φ², das heißt, wenn k < mφ² < k+1,
oder wenn man k schreiben kann als [mφ²].

Wir haben bisher gezeigt dass jede natürliche Zahl entweder dargestellt werden kann als [kφ, oder als [kφ²].
Wenn a_n = [nφ, dann ist b_n = a_n + n = [nφ + n = [n(φ + 1)] = [nφ²].
Wir zeigen mal dass für jedes n gilt a_n = [nφ.
Aus der Definition folgt sofort dass die Zahlenfolge a₁, b₁, a₂, b₂, ... eine wachsende Reihe sein soll.
(Mit Verlaufsinduktion) a₁ = [1.φ. Es sei a_k = [kφ für k<K.
Nun ist a_K = [mφ, mit m = K (weil a_K die kleinste Zahl ist die noch nicht in der Reihe erschienen ist), oder a_K = [mφ²] für gewisses m.
Im letzten Fall ist [mφ kleiner als [mφ²], so (Induktionsvoraussetzung) [mφ = a_m für gewisses m < K, uns b_m = [mφ²]. Offenbar kam [mφ²] schon früher vor in der Reihe, was im Widerspruch steht mit den Regeln.
Wir stellen fest: a_k = [kφ für jedes k.

Ausserdem: φ² = φ + 1, ergo nφ² = nφ + n und [nφ²] = [nφ + n. Kurz, jede natürliche Zahl kann representiert werden als [nφ²] - [nφ für gewisses n.



---


Ich zeige dass F_2n = [F_2n-1φ.
F_2n-1 = (r^2n-1 - s^2n-1)/(r - s), mit r = φ und rs = -1.
Dann ist F_2n-1φ = (r²ⁿ + s^2(n-1))/(r - s) > (r²ⁿ - s²ⁿ)/(r - s) = F_2n und
(r²ⁿ + s^2(n-1))/(r - s) - (r²ⁿ - s²ⁿ)/(r - s) = (1/r^2(n-1) + 1/r²ⁿ)/5 < 1.
Also F_2n = [F_2n-1φ.
Dann ist [F_2n-1φ²] = [F_2n-1φ + F_2n-1 = F_2n + F_2n-1 = F_2n+1
Jedes F_n mit geradem n ist also ein a_k, also jedes F_n mit ungeradem n ist ein b_k. Eine ähnliche Geschichte gilt für Lucaszahlen.