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?

 [T(0)-T(-1)]+[T(1)-T(0)]+...+[T(N)-T(N-1)]=T(N)-T(-1) due to almost complete cancellation. The analogy to the definite integral is clear. Given a function G, if we can find an antidifference function T such that T(N)-T(N-1)=G(N) then we have the evaluation G(0)+G(1)+...+G(N)=T(N)-T(-1). For the two T's given below, T(-1)=0, so the "answer" is just T(N).

1) T(N)=F(N+2)-1, G(N)=F(N)=Nth Fibonacci Number: (F(-1)=1, F(0)=0, F(1)=1, F(N+2)=F(N+1)+F(N). T(N)-T(N-1)=F(N+2)-1-[F(N+1)-1]=F(N+2)-F(N+1)=F(N).

2) T(N)=F(N)F(N+1), G(N)=[F(N)]^2 since T(N)-T(N-1)=F(N)F(N+1)-F(N-1)F(N)=F(N)[F(N-1)+F(N)]-F(N-1)F(N)=[F(N)]^2.

It is a less than straightforward process to divine an antidifference function, just like for an antiderivative. For 1), a table of the values compared with a table of values of the Fibonacci numbers (if one would think to do that) would certainly work, and for 2) it is conceivable that such a formula could be conjectured, especially if one again is looking at tables of values and expecting to find a connection. While both results are mentioned in previous comments, before I had read any of them I used a special method of my own: Google "sum of Fibonacci" (quotes included).

Edited on July 16, 2004, 4:04 pm

Posted by Richard on 2004-07-15 22:54:46