What would be the most efficient way to calculate the sum of Fibonacci numbers from F(n) to F(m) where F(n) and F(m) are nth and mth Fibonacci numbers respectively and 0 =< n <= m <109 (with F(0)=0, F(1)=1).
For example, if n=0, m=3, we need to find F(0)+F(1)+F(2)+F(3).
Just by brute force it will take long time for the range of n and m mentioned. If it can be done via matrix exponentiation then how?
Answer
The first two answers (oldest ones) are seemingly incorrect to me. According to this discussion which is already cited in one of the answers, sum of first n Fibonacci numbers is given by:
SumFib(n) = F[n+2] - 1 (1)
Now, lets define SumFib(m, n) as sum of Fibonacci numbers from m to n inclusive (as required by OP) (see footnote). So:
SumFib(m, n) = SumFib(n) - SumFib(m-1)
Note the second term. It is so because SumFib(m) includes F[m], but we want sum from F[m] to F[n] inclusive. So we subtract sum up to F[m-1] from sum up to F[n]. Simple kindergarten maths, isn't it? :-)
SumFib(m, n) = SumFib(n) - SumFib(m-1)
= (F[n+2] - 1) - (F[m-1 + 2] - 1) [using eq(1)]
= F[n+2] - 1 - F[m+1] + 1
= F[n+2] - F[m+1]
Therefore, SumFib(m, n) = F[n+2] - F[m+1] (2)
Example:
m = 3, n = 7
Sum = F[3] + F[4] + F[5] + F[6] + F[7]
= 2 + 3 + 5 + 8 + 13
= 31
And by using (2) derived above:
SumFib(3, 7) = F[7+2] - F[3+1]
= F[9] - F[4]
= 34 - 3
= 31
Bonus:
When m and n are large, you need efficient algorithms to generate Fibonacci numbers. Here is a very good article that explains one way to do it.
Footnote: In the question m and n of OP satisfy this range: 0 =< n <= m, but in my answer the range is a bit altered, it is 0 =< m <= n.