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?

As others have observed, the sum of fibonacci number up to F(k) seems to be F(k+2) - 1

To explain this, I'll express the number in this form: a*F(1) + b*F(2) + c*F(3)...

a  b c d e f ... k-1 k k+1 k+2  
1  1 1 1 1 1 ...   1 1   0   0 =
0  0 2 1 1 1 ...   1 1   0   0 =
0 -1 1 2 1 1 ...   1 1   0   0 =
0 -1 0 1 2 1 ...   1 1   0   0 =
0 -1 0 0 1 2 ...   1 1   0   0 =
0 -1 0 0 0 0 ...   1 2   0   0 =
0 -1 0 0 0 0 ...   0 1   1   0 =
0 -1 0 0 0 0 ...   0 0   0   1 =

So as you can see, the sum of fibonacci numbers up to F(k) is equal to F(k+2) - F(2), which simplifies to F(k+2)-1.

Edited on July 16, 2004, 3:53 pm

Posted by Tristan on 2004-07-16 15:52:57