Sei ´p(n) := sum_(k=0)^n F_(2k+1) = F_(2n+2)´ mit ´Fn:´ Fibonacci- Zahl von ´n´.

Zu zeigen : ´AAn in NN : p(n)´

Induktionsbasis:

Sei ´n = 0´, zu Zeigen: ´p(0)´ ist wahr. ´sum_(k=0)^0 F_(2k+1) = F_1 = F_2 = F_(2 * 0+2)´

Induktionsschritt:

Zu zeigen: ´AA n in NN : p(n) => p(n + 1)´ Sei ´n in N´ beliebig aber fest.

´p(n)´ ´=> sum_(k=0)^n F_(2k+1) = F_(2n+2)´ ´| +F_(2(n+1)+1)´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2(n+1)+1) + F_(2n+2)´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2n+2) + F_(2n+3)´ ´|"Definition" Fib´ ´=> F_(2(n+1)+1) + sum_(k=0)^n F_(2k+1) = F_(2n+4)´ ´|"Defintion" Sigma´ ´=> sum_(k=0)^(n+1) F_(2k+1) = F_(2(n+1)+2)´ ´=> p(n+1)´

Aus der Induktionsbasis und dem Induktionsschritt folgt die Korrektheit von ´p(n)´ für alle ´n in N´.