Finding the sum of Fibonacci Numbers

Question

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 <10⁹ (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 1

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.

Answer 2

Given that "the sum of the first n Fibonacci numbers is the (n + 2)nd Fibonacci number minus 1." (thanks, Wikipedia), you can calculate F(m + 2) - F(n + 2) (shouldn't have had -2, see Sнаđошƒаӽ's answer for what I'd overlooked). Use Binet's Fibonacci number formula to quickly calculate F(m + 2) and F(n + 2). Seems fairly efficient to me.

Update: found an old SO post, "nth fibonacci number in sublinear time", and (due to accuracy as mjv and Jim Lewis have pointed out in the comments), you can't really escape an O(n) solution to calculate F(n).

Answer 3

F(m+2) - F(n+2) - 2 (discussion)

Literally, the sum of your upper bound m, minus the sum of your lower bound n.

Answer 4

Algorithm via matrix property explanation found here and here

class Program
{
    static int FibMatrix(int n, int i, int h, int j, int k)
    {
        int t = 0;

        while (n > 0)
        {
            if (n % 2 == 1)
            {
                t = j * h;
                j = i * h + j * k + t;
                i = i * k + t;
            }
            t = h * h;
            h = 2 * k * h + t;
            k = k * k + t;
            n = n / 2;
        }

        return j;            
    }

    static int FibSum(int n, int m)
    {
        int sum = Program.FibMatrix(n, 1, 1, 0, 0);

        while (n + 1 <= m)
        {
            sum += Program.FibMatrix(n + 1, 1, 1, 0, 0);
            n++;
        }

        return sum;
    }

    static void Main(string[] args)
    {
        // Output : 4
        Console.WriteLine(Program.FibSum(0, 4).ToString());

        Console.ReadLine();
    }
}

Answer 5

The answer is:

f(m+2)-f(n+1)

Example:

for n = 3 to m = 8

Ans1 = f(m+2) = f(10) = 55

Ans2 = f(n+1) = f(4) = 3 

Answer = 55 - 3 = 52

Now to calculate the Nth fibonacci in O(logN) you can use matrix Exponentiation method

Link:- http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/