Exercise 1035Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

An identity for Fibonacci numbers

#induction#Fibonacci#identity

Statement

Let $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$ . Prove that $\sum_{k=0}^{n}F_k=F_{n+2}-1$ .

Hint

Base case $n=0$ ; inductive step.

Show solutionHide solution

Base case. $n=0$ : $\sum_{k=0}^0F_k=0=F_2-1=1-1=0$ . ✓

Inductive step. Assume $\sum_{k=0}^nF_k=F_{n+2}-1$ . Then
$\sum_{k=0}^{n+1}F_k=F_{n+2}-1+F_{n+1}=F_{n+3}-1.$

Conclusion. The identity holds for all $n\ge0$ .