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
Best Answer
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$$