Fibonacci Zahlen definiert und für alle n aus N0 zeigen

Question

Aufgabe:

Die Fibonacci-Zahlen f₀, f₁, f₂, . . . werden durch die Rekursion f₀ := 0, f₁ := 1, f_n+1 := f_n-1 + f_n
(n ≥ 1) definiert. Zeigen Sie, dass fur alle n ∈ N₀ gilt:

\( \sum\limits_{i=0}^{n} \) * f_{1 =} f_n+2 - 1

Answer 1

Hallo,

das lässt sich leicht über Induktion zeigen. Ich unterstelle, es soll gezeigt werden, dass $$\sum_{i=0}^{n} f_i = f_{n+2} - 1$$Zunächst der Induktionsanfang für \(n=1\). Es ist$$n =1 \implies 0 + 1 = 2 - 1 \space \checkmark$$das passt. Dann der Übergang von \(n\) nach \(n+1\):$$\begin{aligned} \sum_{i=0}^{n+1} f_i &= \sum_{i=0}^{n} f_i \space + f_{n+1} \\ &=  f_{n+2} - 1 +  f_{n+1} \\ &= f_{n+3} - 1 \\ &\text{q.e.d.} \end{aligned}$$

Comments

fn+3 - 1 ist dann die Lösung, aber was hat es mit der Rekursion auf sich muss man die nicht auch zeigen oder reicht das allein schon als Beweis?

---

fn+3 - 1 ist dann die Lösung

nicht so ganz. Die Lösung ist, dass die Aussage \(\sum_{i=0}^n f_i = f_{n+2} - 1\) für alle \(n \ge 1\) wahr ist.

was hat es mit der Rekursion auf sich muss man die nicht auch zeigen

Die Rekursion \(f_{n+1} = f_{n-1} + f_n\) musst Du nicht zeigen. Die ist definiert. Die Folge der Fibonacci-Zahlen ist genau über diese Rekursion defniert. Und das gilt natürlich für jedes \(n \in \mathbb N_0\); also auch für \(f_{n+3} = f_{n+2} + f_{n+1}\).

Jede Fibonacci-Zahl ist die Summe seiner beiden Vorgänger.