2
$\begingroup$

I've found an interesting problem in my Combinatorics class notes but I am unsure how to start or even where to start. The question is:

Prove that $\sum_{j=1}^nf_j^2$ = $f_n$$f_{n+1}$, where $f_j$ are Fibonacci numbers.

Would anyone mind giving me a hint or at least giving me a start?

$\endgroup$
2
$\begingroup$

assume this is true for some $m$. So

$\Sigma_{j=1}^{m} f_j^2= f_mf_{m+1}$.Now for $m+1$, we can write

$\Sigma_{j=1}^{m+1} f_j^2=\Sigma_{j=1}^{m} f_j^2+ f^2_{m+1}= f_mf_{m+1} + f^2_{m+1} = f_{m+1}(f_m+f_{m+1}) =f_{m+1}f_{m+2}$.

So by proof by induction it is true for $n= 2$ ($1^2+1^2+2^2=2*3$) let us say. and if it is true for $m$ then true for $m+1$. Since it is true for n=2, it is true for all natural numbers >=2. Hence the proof

$\endgroup$

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