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 S(n) be the sum up to n.

S(n)+F(1)
=F(n)+...+[F(2)+F(1)]+[F(1)+F(0)]
=F(n)+...F(3)+F(3)+F(2)
=F(n)+...+[F(4)+F(3)]+[F(3)+F(2)]
=F(n)+...+F(5)+F(5)+F(4)
=F(n)+...+[F(6)+F(5)]+[F(5)+F(4)]
=F(n)+...+F(7)+F(7)+F(6)
........

So if you notice the pattern, S(n)+F(1) = ŁUF(i), i from k to n, where k is odd, + F(k)+F(k-1)

So if n is odd, take k = n and get
S(n)+F(1)=F(n)+F(n)+F(n-1)
=F(n)+F(n+1) = F(n+2)

If n is even, take k = n+1 and get
S(n)+F(1) = F(n+1)+F(n) = F(n+2)

Therefore, in conclusion, S(n)=F(n+2)-F(1)

Simple induction can prove this case easily.

Posted by Bon on 2004-08-04 18:34:07