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:

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

  • $\begingroup$ why $(n+2)+(n+1) = n+3 $ in fibobacci ? $\endgroup$
    – doniyor
    Nov 24 '12 at 8:52
  • $\begingroup$ So what? Stil $F_{n+3}=F_{n+2}+F_{n+1}$ holds. $\endgroup$
    – Amr
    Nov 24 '12 at 8:54
  • 2
    $\begingroup$ $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$. $\endgroup$
    – P.K.
    Nov 24 '12 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.