Definition Fibonacci-Zahlen. f(n): = f(n-1) + f(n-2). f(0) =0. f(1) = 1.
Man berechne so ein paar Zahlen. f(2) = 1. f(3) = 2, f(4) = 3, f(5) = 5, f(6) = 8, f(7) = 13
Ich lasse im Folgenden Klammern weg, wenn Index aus einem Symbol.
Behauptung:
f2+f4+f6+...+f2k=f(2k+1)-1
Beweis mit Induktion.
Verankerung:
f2 = f3 -1? 1 = 2-1 ok.
Induktionsschritt:
Ind. vor. f2+f4+f6+...+f2k=f(2k+1)-1
Ind. beh. f2+f4+f6+...+f2k + f(2k+2) = f(2k+3)-1
Beweis.
f2+f4+f6+...+f2k + f(2k+2)
|Ind. vor.
= f(2k+1) - 1 + f(2k+2)
=f(2k + 1) + f(2k+2) - 1
| Achtung Vergleich mit Definition f(n): = f(n-1) + f(n-2)
| n-2 = 2k+1, n-1 = 2k+2. D.h. n = 2k+3
= f(2k+3)-1
qed Indukionsschritt.