Beweis durch vollständige Induktion einer Summe mit Fibonacci-Zahlen

Question

Aufgabe: Die Fibonacci–Zahlen sind durch f₀ = 0, f₁ = 1 und f_n+1 =
f_n + f_n−1 für n ≥ 1 definiert.

Zeigen Sie, dass
\( \sum\limits_{k=0}^{n}{(f } \)_k)² =f_n· f_n+1

für n∈ℕ.

Können Sie obige Formel grafisch darstellen?

Problem/Ansatz:

Ich habe es mit vollständiger induktion versucht, komme aber nicht weiter.

IAN: n=1

\( \sum\limits_{k=0}^{1}{(f } \)_k)² =(0) ²+(1)²= 1

f_n· f_n+1= f_n·(f_n+ f_n-1)=1·(1+0)=1

Somit ist dies für n=1 bewiesen.

IV: Da \( \sum\limits_{k=0}^{n}{(f } \)_k)² =f_n· f_n+1 für n gilt, gilt es auch für n+1

IS: zu zeigen: \( \sum\limits_{k=0}^{n+1}{(f } \)_k)² =f_n+1· f_(n+1)+1

Mit IV folgere ich: \( \sum\limits_{k=0}^{n+1}{(f } \)_k)²=\( \sum\limits_{k=0}^{n}{(f } \)_k)²+(n+1)²≤(f_n·f_n+1)+(n+1)²

Weiter bin ich bisher nicht gekommen. Könnte jemand helfen?

LG Blackwolf

Answer 1

Hallo Blackwolf,

Beim Induktionsschritt geht es darum zu zeigen, dass $$\sum\limits_{k=0}^{n+1}{f_k}^2 \stackrel ?{=} f_{n+2}f_{n+1}$$gilt. Und das unter der Voraussetzung der Induktionsannahme.

Und bei den Summenausdrücken beginnt man immer damit, den letzten Summanden - mit dem Index \(n+1\) - zu vereinzeln, da der Rest der Summe bereits durch die Induktionsannahme gegeben ist. Also so:$$\begin{aligned} \sum\limits_{k=0}^{n+1}{f_k}^2 &= \sum\limits_{k=0}^{n}{f_k}^2 \space + f_{n+1}^2 &&\left|\, \sum\limits_{k=0}^{n}{f_k}^2  =f_n\cdot f_{n+1} \right.\\ &= f_n\cdot f_{n+1} + f_{n+1}^2\\ &= (f_n + f_{n+1})f_{n+1}\\ &= f_{n+2}f_{n+1}\\ &\text{q.e.d.} \end{aligned}$$

zu deinem Ansatz:

Mit IV folgere ich: \( \sum\limits_{k=0}^{n+1}{(f } \)k)²=\( \sum\limits_{k=0}^{n}{(f } \)k)²+(n+1)²

das ist falsch, da \(f_{n+1}^2 \ne (n+1)^2\)

Comments

Dankeschön!

LG Blackwolf

Answer 2

Zu beweisen ist, dass das Hinzufügen des nächsten Summanden das Gleiche ergibt, wie das Ersetzen von n+1 für n in Formel IV, also, dass gilt:

f_n+1·f_n+2=f_n·f_n+1+f_n+1² 

Beweis durch Einsetzen der definierenden Gleichung f_n+2=f_n+1+f_n.

Comments

Dankeschön!
LG Blackwolf