Hallo Klinei,
F0=1, F1=1, F2=2, F3=3
eher nicht! Dann stimmt schon Dein Induktionsanfang nicht. Besser:$$F_0=0, \, F_1=1, \, F_2=1, \, F_3=2, \, F_4= 3\, \dots$$Es soll gezeigt werden, dass$$F_{2(n+1)} = F_{n+1}(F_{n+2} + F_{n})$$Hier brauchen wir einen doppelten Induktionsanfang. Es ist sowohl $$F_2 = F_1(F_2+F_1) = 1 \cdot(1 + 0) = 1$$als auch $$F_4 = F_2(F_3 + F_1) = 1 \cdot (2 + 1) = 3$$Wir haben also für die ersten zwei auf einander folgender Werte für \(n\) gezeigt, dass die Formel korrekt ist.
Bevor es zum Induktionsschritt kommt, will ich noch zeigen, dass $$F_{2(n+2)} = 3F_{2(n+1)} - F_{2n}$$ es ist $$\begin{aligned} F_{2(n+1)}&= F_{2n+1} + F_{2n} \\ \implies F_{2n+1} &=F_{2(n+1)} - F_{2n} \\ F_{2(n+2)} &= F_{2n+3} + F_{2(n+1)} \\ &= F_{2(n+1)} + F_{2n+1} + F_{2(n+1)} \\ &= 2 F_{2(n+1)} + F_{2(n+1)} - F_{2n} \\ &= 3 F_{2(n+1)} - F_{2n} \end{aligned}$$und für die beiden Vorgänger setze ich nun die Voraussetzung aus dem (doppelten) Induktionsanfang ein:$$ \begin{aligned} F_{2(n+2)} &= 3F_{n+1}(F_{n+2} + F_{n}) - F_{n}(F_{n+1} + F_{n-1}) \\ &= 3 F_{n+2} F_{n+1} + 2F_{n+1}F_n -F_nF_{n-1} \\ &= 3 F_{n+2} F_{n+1} + F_{n+1}F_n + F_n(F_{n+1} -F_{n-1}) \\ &= 3 F_{n+2} F_{n+1} + F_{n+1}F_n + F_n^2 \\ &= 3F_{n+2} F_{n+1} + F_n(F_{n+1}+ F_n) \\ &= 3F_{n+2} F_{n+1} + F_n F_{n+2} \\ &= 3F_{n+2} F_{n+1} + F_n F_{n+2} \\ &= F_{n+2} (3F_{n+1} + F_n) \\ &= F_{n+2} (2F_{n+1} + F_{n+2}) \\ &= F_{n+2} (F_{n+3} + F_{n+1}) \quad \text{q.e.d.}\end{aligned}$$Gruß Werner
