The Fibonacci series 0, 1, 1, 2, 3, 5, 8, 13, in which each number is the sum of the two previous, is defined as F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n>1.

What is the sum of F(0)+F(1)+F(2)+...+F(k)?
What is the sum of F(0)^2+F(1)^2+F(2)^2+...+F(k)^2?

Let Q(n) = sum of F(i)^2, i from 1 to n

Q(n) = Q(n)+F(1)*F(0)
= F(n)?...+F(1)?F(1)*F(0)
= F(n)?...+F(2)?F(1)*[F(1)+F(0)]
= F(n)?...+F(2)?F(2)*F(1)
= F(n)?...+F(3)?F(2)*[F(2)+F(1)]
= F(n)?...+F(3)?F(3)*F(2)
.....

So you can see that
Q(n) = F(n)?...+F(k)?F(k)*F(k-1)

Just take k = n and get
Q(n) = F(n)?F(n)*F(n-1)
= F(n)*[F(n)+F(n-1)]
= F(n)*F(n+1)

This can be easily verified thru induction again.

Edited on August 9, 2004, 11:25 pm

Posted by Bon on 2004-08-04 18:59:48