Sum of Fibonacci Series

The first few terms(Fn) of Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
For given N find the sum (Sn) of 0 to nth term of a fibonacci series.

Sn = Fn+ Fn-1+ …+ F1+ F0 // Naive Method
Sn = Fn+2 – 1 // Advanced method

Examples:

Naive method:
S4 = F4 + F3 + F2 + F1 + F0
S4 = 3 +2 +1 +1 +0
S4 = 7

Advance method:
S4 = S6-1
S4 = 8-1
S4 = 7

How does this formula works:

with F0=0, F1=1 , F2=1 , Fn=Fn-1+ Fn-2.

we know that:
Sn = Fn+ Fn-1+…..+ F1+ F0
Sn + 1 = Fn+ Fn-1+…..+ F1+ F0 +1 (adding 1 to both side)
Sn + 1 = Fn+ Fn-1+…..+ F1+ F0 +F1 (put 1= F1)
Sn + 1 = Fn+ Fn-1+…..+F2 + F1+ F2 (F0+ F1=F2)
Sn + 1 = Fn+ Fn-1+…..+F3 + F2+ F3 (F1+ F2=F3)
Sn + 1 = Fn+ Fn-1+…..+F4 + F2+ F4 (F2+ F3=F4)
Sn + 1 = Fn+ Fn-1 + Fn
Sn + 1 = Fn+ Fn+1 (Fn-1 + Fn = Fn+1)
Sn + 1 = Fn+2
Sn = Fn+2 -1

Approach:
A simple Approach is to sum all the terms from 0th to nth and print the output, which takes O(n) time and extra O(n) space to store each terms in addition of n terms. In advance approach we are using the formula Sn = Fn+2-1 i.e. ( (n+2)term -1 ). So it takes only O(log n) time and no extra space at all. Note that we can find n’th Fibonacci number in O(Log n) time.

Below is the C++ Implementation of the above approach.

// Advance Method
#include <iostream>
using namespace std;

/* Functions to find Fn in O(log n) time */
void power(int F[2][2], int n);

int fib(int n) {
    int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}

void multiply(int F[2][2], int M[2][2]) {
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(int F[2][2], int n) {
    int i;
    int M[2][2] = {{1, 1}, {1, 0}};

    // n - 1 times multiply the matrix to {{1,0},{0,1}}
    for (i = 2; i <= n; i++)
        multiply(F, M);
}

// Driver Program
int main() {
    int n;
    n = 6;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum = sum + fib(i); // calculation of sum of series by adding n terms
    }
    cout << sum;
    return 0;
}

Output:

Time Complexity: O(log n) due to the power function.
Space Complexity: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.