Fibonacci

Ein anderes Verfahren


Wir werden zeigen: Wenn v eine Lösung der Gleichung x²-x-1=0 ist, dann ist:

vⁿ = F_nv + F_n-1

Die Behauptung stimmt unbedingt für n=1 und für n=2, denn für n=1 lesen wir v = v und für n=2 lesen wir v² = v+1.
Um die Richtigkeit der Behauptung für n=3 zu zeigen multiplizieren wir die Gleichung für n=2 (die korrekt ist, wie wir gerade bewiesen haben) mit v
v³ = F₂v² + F₁v = F₂(v + 1) + F₁v = (F₂ + F₁)v + F₂ = F₃v + F₂.
Offenbar ist die Formel auch richtig für n=3.
Wir wiederholen diesen Vorgang, indem wir die Formel für n=3 mit v multiplizieren.
v⁴ = F₃v² + F₂v = F₃(v + 1) + F₂v = (F₃ + F₂)v + F₃ = F₄v + F₃.
Augenscheinlich ist die Formel auch richtig für n=4.
Im Allgemeinen: Gesetzt, die Formel sei korrekt für n=N. Dann ist die Formel auch für n=N+1 korrekt, denn:
v^N+1 = F_Nv² + F_N-1v = F_N(v + 1) + F_N-1v = (F_N + F_N-1)v + F_N = F_N+1v + F_N.
Wir können also folgern dass die Formel für jedes n>=0 stimmt.

r = (1 + sqrt(5))/2 und s = (1 - sqrt(5))/2 sind die zwei Lösungen der Gleichung x²-x-1=0. Also gilt:
rⁿ = F_nr + F_n-1 und
sⁿ = F_ns + F_n-1
Wenn wir die zweite Gleichung von der ersten substrahieren, dann bekommen wir
rⁿ-sⁿ = F_n(r-s), oder
F_n = (rⁿ-sⁿ)/(r-s).
Die n-te Lucaszahl L_n wird definiert durch L_n = F_n+1 + F_n-1.
Dann ist L_n = rⁿ + sⁿ.