Zeigen Sie, mittels vollständiger Induktion:

Question

Aufgabe:Aufgabe 3. Sei f(n) rekursiv definiert durch



f(1) = 1
f(2) = 1
f(n) = f(n − 1) + f(n − 2) ∀n ∈ N, n ≥ 3.
Zeigen Sie, mittels vollständiger Induktion:
f(2) + f(3) + · · · + f(n) = f(n + 2) − 2 ∀n ≥ 2

Problem/Ansatz:

ich habe den ersten schritt der induktion durch geführt also den induktionsanfang.

nun komme ich nicht mit dem induktionsende zurecht.

kann mir da jemand helfen oder eine lösungsansatz schicken

Answer 1

Induktionsschritt: n → n + 1

f(2) + f(3) + ... + f(n) + f(n + 1) = f((n + 1) + 2) - 2
f(n + 2) - 2 + f(n + 1) = f(n + 3) - 2
f(n + 2) + f(n + 1) = f(n + 3) → wahr

Die letzte Zeile ist ja zufällig gerade die rekursive Definition, dass sich jeder Wert als Summe der beiden vorangehenden Werten ergibt.

Comments

woher wissen wir den genau, dass f(n + 2) + f(n + 1) = f(n + 3) ergibt?

---

woher wissen wir den genau, dass f(n + 2) + f(n + 1) = f(n + 3) ergibt?

Die letzte Zeile ist ja zufällig gerade die rekursive Definition, dass sich jeder Wert als Summe der beiden vorangehenden Werten ergibt.

Answer 2

$$f(n+2)=f(n)+f(n+1)$$

$$ \sum\limits_{k=1}^{n}{f(k)} =f(n+2)-2$$

$$ \sum\limits_{k=1}^{n+1}{f(k)} = \sum\limits_{k=1}^{n}{f(k)} +f(n+1)=$$$$f(n+1)+f(n+2)-2=$$$$f(n+3)-2=$$$$f((n+1)+2)-2$$