Formel für Fibonacci-Zahlen mit vollständiger Induktion beweisen

Question

Aufgabe:

Gegeben sei die n-te Fibonacci Zahl f_n. D.h. f₀ = 1 und f₁ = 1 es gilt
f_n = f_n−1 + f_n−2.

Beweisen sie durch vollständige Induktion (unter Benutzung der Rekursion) die Gleichung:

\( \sum\limits_{k=0}^{n}{ kf_k = nf_{n+2} − f_{n+3} + 2} \)   

für ganze Zahlen n ≥ 0.

die Gleichung nochmal :  kf_k = nf_n+2 − f_n+3 + 2

Comments

Wo scheiterst du? Verifizierung für n=0,1? aufstellen der Formel für n+1? Einsetzen der Induktionsvors? Verwenden der Rekursion?

Was hast du bisher gemacht?

lul

---

defintiv beim Verwenden der Rekursion.

---

Dann zeig mal, wie weit du gekommen bist!

lul

Answer 1

Σ (k = 0 bis n + 1) (k·f(k)) = (n + 1)·f(n + 1 + 2) - f(n + 1 + 3) + 2

Σ (k = 0 bis n) (k·f(k)) + (n + 1)·f(n + 1) = (n + 1)·f(n + 3) - f(n + 4) + 2

n·f(n + 2) - f(n + 3) + 2 + (n + 1)·f(n + 1) = (n + 1)·f(n + 3) - f(n + 4) + 2

n·f(n + 1) + n·f(n + 2) - n·f(n + 3) + f(n + 1) + f(n + 4) - 2·f(n + 3) = 0

n·(f(n + 1) + f(n + 2) - f(n + 3)) + f(n + 1) + f(n + 4) - 2·f(n + 3) = 0

nutze f(n + 1) + f(n + 2) = f(n + 3) --> f(n + 1) = f(n + 3) - f(n + 2)

n·(f(n + 3) - f(n + 3))  - f(n + 2) + f(n + 4) - f(n + 3) = 0

nutze - f(n + 2) - f(n + 3) = - f(n + 4)

n·(f(n + 3) - f(n + 3)) + f(n + 4) - f(n + 4) = 0