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.