There are many ways to compute the n-th Fibonacci number easily: there is a well-known close formula. Another approach is matrix multiplication.

Let’s take a look at this approach first.

As we all know, F_k+2 = F_k+1 + F_k. Thus, we can expand this equation to a matrix equation:

[1]

Now, it’s easy to see the following:

[2]

Now, we only need to compute this n-th power of a magic matrix for Fibonacci numbers.

If one 2-by-2-matrix-multiplication costs you $1, you only need to pay $n-1 to compute the n-th power. Or, even better, you only need about $log₂ n with some fancy optimization; I believe I learned this in CS 100/211. See the following pseudo-code:

int power(int x, int n) // computes x ^ n
{
if (n == 0) return 1;
if (n % 2 == 1) return power(x, n-1) * x;
int tmp = power(x, n/2);
return tmp * tmp;
}

Then, how about the SUM of first n terms of Fibonacci numbers? How about the sum of numbers between n-th term and m-th term? One easy way is to compute each number and add them up; this will cost you too much.

Let us call the magic matrix above M.

In order to get the sum of first n Fibonacci numbers, we need to compute M, M², M³, … , Mⁿ. This will cost you roughly $n²/2. Can we do better?

We want our final matrix to be M + M² + M³ + … + Mⁿ. Now recall how we compute xⁿ with O(log n) multiplications. Suppose we have the matrix M + M² + M³ + … + M^n/2. If we multiply M^n/2 to this sum of matrices, and then add it to the original sum, we finally get M + M² + M³ + … + Mⁿ. We are using similar optimization here.

Matrix powerSum(M, n)
{
if (n == 0) return E; // unit 2-by-2 matrix
if (n == 1) return M;
if (n % 2 == 1)
{
S = powerSum(M, (n-1)/2);
T = S * M^(n-1)/2; // we can optimize computing M^(n-1)/2, too.
return S + T + M^n; // M^n can be computed from M^(n-1)/2.

} else {
S = powerSum(M, n/2);
T = S * M^(n/2);
return S + T;
}
}

You can easily see that we do NOT use matrix multiplication n^2 times; it’s O(log n) if we optimize computation of M^(n/2) - we can do this by forcing this powerSum method to return M^n as well when it returns the sum of M, M^2, …, M^n - then, the caller can use this result to compute M^2n or M^(2n+1), and so on.

References

[1] http://upload.wikimedia.org/math/3/d/c/3dcf66f1eb82acf058a19800b2094fa9.png

[2] http://upload.wikimedia.org/math/a/6/0/a6083f85f39b468210f5715a8e30d572.png