Als erstes kommt bei einer vollständigen Induktion ja immer der Induktionsanfang, wir müssen also die Aussage für \(n=1\) zeigen. Es ist \(F_{2\cdot1+1}=F_3=3=1+1+1=F_1+F_1+1=\sum_{i=0}^{1-1}F_{2i+1}+F_{2\cdot1-1}+1\). Damit ist der Induktionsanfang abgehakt.

Nun kommt die Induktionsvoraussetzung. Dabei nehmen wir an, dass die Aussage für ein festes \(n\) gilt. Diesen Teil kannst du immer gleich formulieren, z.B. Angenommen, es gilt \(F_{2n+1}=\sum_{i=0}^{n-1}F_{2i+1}+F_{2n-1}+1\) für ein festes \(n\in\mathbb N.\)

Schließlich fehlt nur noch der Induktionsschritt. Hier müssen wir die Aussage unter der Induktionsannahme für \(n+1\) zeigen, zu zeigen ist also \(F_{2(n+1)+1}=\sum_{i=0}^{(n+1)-1}F_{2i+1}+F_{2(n+1)-1}+1\) (ich habe einfach jedes \(n\) mit \(n+1\) ersetzt). Diese Gleichung wollen wir nun zeigen. Dazu fangen wir mal links an und formen solange um, bis wir rechts rauskommen.

\(\begin{align}F_{2n+3}&=F_{2n+1}+F_{2n+2}\\&=\sum_{i=0}^{n-1}F_{2i+1}+F_{2n-1}+1+F_{2n+2}\\&=\sum_{i=0}^{n-1}F_{2i+1}+F_{2n-1}+1+F_{2n}+F_{2n+1}\\&=\left(\sum_{i=0}^{n-1}F_{2i+1}+F_{2n+1}\right)+\left(F_{2n}+F_{2n-1}\right)+1\\&=\sum_{i=0}^nF_{2i+1}+(F_{2n-1}+F_{2n})+1\\&=\sum_{i=0}^nF_{2i+1}+F_{2n+1}+1 \end{align}\)

Jetzt haben wir genau das, was wir zeigen wollten, und damit sind wir fertig. 

Erklärungen zu den einzelnen Rechenschritten: Im ersten Schritt haben wir die Definition der Fibonacci-Zahlen verwendet und im zweiten die Induktionsvoraussetzung. Danach noch einmal die Definition der Fibonacci-Zahlen. Im nächsten Schritt wurde nur umsortiert und umgeklammert. Dann wurde der Term in der ersten Klammer zu der Summe hinzugefügt und im letzten Schritt in der Klammer die Definition der Fibonacci-Zahlen verwendet.