# Induction Proof: Formula for Sum of n Fibonacci Numbers

The Fibonacci sequence $$F_0, F_1, F_2, \ldots$$ is defined recursively by $$F_{0}:=0, F_{1}:=1$$ and $$F_{n}:=F_{n-1}+F_{n-2}$$.

Prove that $$\sum_{i=0}^{n} F_{i}=F_{n+2}-1 \qquad \text{for all } n \geq 0 .$$

I am stuck though on the way to prove this statement of fibonacci numbers by induction :

my steps:
definition:

The Hypothesis is: $$\sum_{i=0}^{n} F_{i}=F_{n+2}-1$$ for all $$n > 1$$

Base case: $$n=2$$
$$\sum_{i=0}^{2} F_{i}=F_{0}+F_{1}+F_{2}=0+1+F_{1}+F_{0}=0+1+1+0=2$$ which is equal to $$F_{2+2}-1=F_{4}-1=F_{3}+F_{2}-1=F_{2}+F_{1}+F_{2}-1=1+1+1-1=2$$ OK!

inductive step:
to prove: $$\sum_{i=0}^{n+1} F_{i}=F_{n+3}-1$$ for all $$n > 1$$
$$\sum_{i=0}^{n+1} F_{i}=\sum_{i=0}^{n} F_{i}+F_{n+1}=F_{n+2}-1+F_{n+1}=...help...=F_{n+3}-1$$

i need help to $$..help..$$ please! thanks a lot

Use $F_{n+1}+F_{n+2}=F_{n+3}$, to get:
$$\sum_{i=0}^{n+1} F_{i}=\sum_{i=0}^{n} F_{i}+F_{n+1}=F_{n+2}-1+F_{n+1}=F_{n+1}+F_{n+2}-1=F_{n+3}-1$$
• why $(n+2)+(n+1) = n+3$ in fibobacci ? Nov 24 '12 at 8:52
• So what? Stil $F_{n+3}=F_{n+2}+F_{n+1}$ holds.
• $F_{n + k + 2} = F_{n + k + 1 } + F_{n + k}$ holds true always in the Fibonacci Sequence, as long as $n$ and $k$ are whole numbers. You could even remove the $k$ and get the correct definition. The $k$ was pushed in for better understanding. You could put infinite $k$'s in there—i.e., $k_1 , k_2\ldots$.