Fibonacci

Beweis:

Beweis:
Sei T(k) die Anzahl Einsen in den ersten k Ziffern der Reihe. Dann ist f(k) = T(k) - T(k-1).
Definiere T'(k) = [(k+1)/φ] und f'(k) = T'(k) - T'(k-1).
Wir zeigen dass T = T' (und folglich, dass f = f').
f'(k) = T'(k) - T'(k-1) = [(k+1)/φ] - [k/φ].
f'(k) = 1 dann und nur dann wenn [k/φ] < [(k+1)/φ]
oder wenn eine ganze Zahl m existiert so, dass k/φ < m < (k+1)/φ, das heisst wenn k < mφ < k+1,
oder wenn k = [mφ].
Wir beweisen nun dass T = T' (also dass f = f'):

Mit vollständiger Induktion. T(1) = 1 = [2/φ] = T'(1), also T(k) = T'(k) für k<=F₂, die zweite Reihe.
Setze voraus dass T(k) = T'(k) für k<=F_n, die n-te Reihe (für eine bestimmte n>1).
Wir werden nun zeigen dass f(k) = f'(k) (und deshalb auch dass T(k) = T'(k)) für k<=F_n+1, die n+1-te Reihe.
Betrachte die k-te Ziffer jener n-ten Reihe. Die k-1 Ziffern davor werden umgewandelt in k-1+T(k-1) Ziffern der n+1-ten Reihe.
Für die Eltern der k-ten Ziffer gilt nun f(k + T(k-1)) = 1 sowohl wenn f(k) = 0 als wenn f(k) = 1 und f(k + 1 + T(k-1)) = 0 wenn f(k) = 1.
Die Induktion ist vollständig wenn wir zeigen können dass f(k + T(k-1)) = f'(k + T(k-1)) und dass, falls f(k) = 1,
f(k + 1 + T(k-1)) = f'(k + 1 + T(k-1)).
k + T(k-1) = k + T'(k-1) = k + [k/φ] = k + [k(φ - 1)] = [kφ]      (*)
f'(k + T(k-1)) = f'([kφ]) = 1 = f(k + T(k-1)).
Wir müssen noch zeigen dass f(k + 1 + T(k-1)) = f'(k + 1 + T(k-1)) falls f(k) = 1.
Wenn f(k) = 1, dann ist 1 + T(k-1) = T(k) und also (Sieh (*))
[kφ] + 1 = k + 1 + T(k-1) = k + T(k) = k + T'(k) = k + [(k+1)/φ] = k + [(k+1)(φ - 1)] = [(k+1)φ] - 1.
Wenn f'(k + 1 + T(k-1)) = 1, dann gibt es eine ganze Zahl m so, dass [kφ] + 1 = [mφ] = [(k+1)φ] - 1.
So m > k und m < k+1. Unmöglich, also f'(k + 1 + T(k-1)) = 0 = f(k + 1 + T(k-1)).
Damit ist der Beweis geliefert.