fibonacci series - recursive summation

fibonacci, java, math, recursion

Solution

Your modification to your `fibonacci` program does indeed work to calculate sums. However, the way you have used recursion is inefficient. One way to deal with this is with a "dynamic programming" approach, where calculated values are cached so that they can be re-used by the second recursive call. However, the n-th Fibonacci number can be forward calculated from the base. A recursive implementation of this would be:

public static int fib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fib_r(b, a+b, n-1);
}

public static int fib (int n) {
    return fib_r(0, 1, (n > 0) ? n : 1);
}

The corresponding code for the sum would be:

public static int sumfib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return sumfib_r(b, a+b+1, n-1);
}

public static int sumfib (int n) {
    return sumfib_r(0, 1, (n > 0) ? n : 1);
}

Tail recursion will often be changed by the compiler/interpreter into a simple loop as part of tail call removal.

You asked:

I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??

This question is really about understanding the algorithm, which I would suppose is topical on SO. But, math is required to describe why the algorithm works. So, this is really a math question. There is a well known theorem regarding the sum of Fibonacci numbers. If `F[i]` is the i-th Fibonacci number, and `S[n]` is the sum of the first `n` Fibonacci numbers, then the theorem above states:

    S[n] = F[n+2] - 1

So, if we consider that by definition of `S[n+2]`,

S[n+2] = S[n+1] + F[n+2]

Then, substituting `S[n] + 1` for `F[n+2]`:

S[n+2] = S[n+1] + S[n] + 1

Which you should recognize is your "add 1 modified" `fibonacci` function.

Below is a proof by induction that your program computes the sum that I provided in my original answer. Let `F` represent your `fibonacci` function, and let `S` represent your "add 1 modified" `fibonacci` function.

F[1] = 0
F[2] = 1
F[i] = F[i-1] + F[i-2] for i > 1

S[1] = 0
S[2] = 1
S[i] = S[i-1] + S[i-2] + 1 for i > 1

Then, you want a proof that for `k > 0`:

         k
       .---  
S[k] =  >   F[i]
       `---
       i = 1

Note that the above summation is true if and only if:

S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1

The proof is fairly straight forward. The base cases are trivially true.

S[1] = F[1] = 0
S[2] = F[2] + F[1] = 1
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2

The induction step is: Given that for some `k > 2`, `S[j+1] = F[j+1] + S[j]` for `0 < j < k+1`, prove that the equality holds true if `j = k+1`, that is: `S[k+2] = F[k+2] + S[k+1]`.

    S[k+2] = S[k+1] + S[k] + 1
=>  S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1
=>  S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1)
=>  S[k+2] = F[k+2] + S[k+1]

This completes the proof.

Problem

Original source