Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

I am trying to learn Fibonacci tricks and I have one that I can not prove. I know it works because Ive tried it multiple times but I have not a clue how to prove. Here it is:

f(0)^2 + f(1)^2 + f(2)^2 + f(3)^2 = f(3)f(3+1)
  0    +   1    +   1    +   4    =   2  *  3
            = 6                          =6 

Is there a way to prove this?

share|cite|improve this question

marked as duplicate by Martin Sleziak, Davide Giraudo, Najib Idrissi, amWhy, AlexR Apr 3 '14 at 13:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Do you mean to prove that $$f(n)^2+f(n+1)^2+f(n+2)^2+f(n+3)^2=f(n+3)f(n+4)?$$ – Alex Becker Apr 3 '14 at 4:37
I think he means to prove that $\sum_{i=0}^n f(i)^2=f(n)f(n+1)$. – Nishant Apr 3 '14 at 4:38
Yes Nishant is correct. – user081608 Apr 3 '14 at 4:41
Do try induction. One (short) line. – André Nicolas Apr 3 '14 at 4:46
Im sorry but what do you mean by that Andre? – user081608 Apr 3 '14 at 4:47
up vote 10 down vote accepted

Basis : ok

Inductive step : Assume $∑_{i=0}^{n}f(i)^2=f(n)f(n+1)$. $$∑_{i=0}^{n+1}f(i)^2=f(n)f(n+1)+f(n+1)^2$$$$∑_{i=0}^{n+1}f(i)^2=f(n+1)(f(n)+f(n+1))$$$$∑_{i=0}^{n+1}f(i)^2=f(n+1)f(n+2)$$

There is a geometric interpretation:


share|cite|improve this answer
+1 for the geometric interpretation (and of course the correct proof). – Chris Apr 3 '14 at 11:05

You've already proven that it works for one example $k=3$. Now write up the general equation $$ \sum_{k=0}^n F_k^2 = F_n\cdot F_{n+1} $$ and add $F_{n+1}^2$ on both sides. You get $$ F_{n+1}^2+ \sum_{k=0}^n F_k^2 =\sum_{k=0}^{n+1} F_k^2 = F_{n+1}^2+ F_n\cdot F_{n+1}=\left(F_{n+1}+ F_n\right)\cdot F_{n+1} $$ and use $F_{n+2}=F_{n+1}+ F_n$, the definition of Fibonacci numbers.

share|cite|improve this answer

Since the base case is true, assume that $$ \sum_{i=0}^{n}f(i)^2=f(n)f(n+1)$$ is also true and use this assumption to prove that $$ \sum_{i=0}^{n+1}f(i)^2=f(n+1)f(n+2).$$

share|cite|improve this answer

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