1

Given the Fibonacci sequence $F_{0}=0 \;,\; F_{1}=1 \;,\; F_{n+2}= F_{n+1}+ F_{n+1} ; \;\; n\geq 0$

Prove that $ \sum _{i=1}^{2n}F_{i}F_{i-1} = F_{2n}^{2}\\$

Base Cases: $ F_{1}F_{0} = F_{0}^{2}\\ 0 = 0 \\ F_{2}F_{1} = F_{2}^{2}\\ 1 = 1 $

Which are true.

Now, with $\;n=k\;$ we have the inductive step,

$ \sum _{i=1}^{2k}F_{i}F_{i-1} = F_{2k}^{2}\\$

We have to prove then that for $n = k+1$

$ \sum _{i=1}^{2k+2}F_{i}F_{i-1} = F_{2k+2}^{2}\\$

We can do the following:

$ F_{2k+2}F_{2k+1} +\sum _{i=1}^{2k}F_{i}F_{i-1} = F_{2k+2}^{2}\\$

and from the inductive step we can do, $ F_{2k+2}F_{2k+1} + F_{2k}^{2}= F_{2k+2}^{2}\\$

I get stuck here, please help me.

Nosferatu
  • 53

2 Answers2

1

$$ \begin{align*} \sum _{i=1}^{2(k+1)}F_{i}F_{i-1} &= F_{2k+2}F_{2k+1} + F_{2k+1}F_{2k} + \sum_{i=1}^{2k}F_{i}F_{i-1}\\ &=F_{2k+2}F_{2k+1} + F_{2k+1}F_{2k}+F_{2k}^2\\ &=F_{2k+2}F_{2k+1} + F_{2k}(F_{2k+1}+F_{2k})\\ &=F_{2k+2}F_{2k+1} + F_{2k}(F_{2k+2})\\ &=F_{2k+2}(F_{2k+1} + F_{2k})\\ &=F_{2k+2}(F_{2k+2})\\ &=F_{2k+2}^2 \end{align*} $$

Darius
  • 1,111
0

You are missing a term in the sum for $n=k+1$. It should be $$ \sum_{i=1}^{2k+2}F_{i}F_{i-1} = F_{2k+1}F_{2k} + F_{2k+2}F_{2k+1} + \sum_{i=1}^{2k}F_{i}F_{i-1}\,. $$

Now try see if you can finish the proof.

Andre of Astora
  • 745