# Sum of Fibonacci Numbers | Set 2

Sum of Fibonacci Numbers | Set 2

Given a positive number N, the task is to find the sum of the first (N + 1) Fibonacci Numbers.

Examples:

Input: N = 3Output: 4Explanation:The first 4 terms of the Fibonacci Series is {0, 1, 1, 2}. Therefore, the required sum = 0 + 1 + 1 + 2 = 4.

Input: N = 4Output: 7

Naive Approach: For the simplest approach to solve the problem, refer to the previous post of this article.Time Complexity: O(N)Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by the following observations and calculations:Let S(N) represent the sum of the first N terms of Fibonacci Series. Now, in order to simply find S(N), calculate the (N + 2)th Fibonacci number and subtract 1 from the result. The Nth term of this series can be calculated by the formula:

Now the value of S(N) can be calculated by (FN + 2 – 1).

Therefore, the idea is to calculate the value of SN using the above formula:

Below is the implementation of the above approach:

Java

import java.io.*;

class GFG {

public static void sumFib(int N)

{

long num = (long)Math.round(

Math.pow((Math.sqrt(5) + 1)

/ 2.0,

N + 2)

/ Math.sqrt(5));

System.out.println(num – 1);

}

public static void main(String[] args)

{

int N = 3;

sumFib(N);

}

}

Time Complexity: O(1)Auxiliary Space: O(1)

Alternate Approach: Follow the steps below to solve the problem:

The Nth Fibonacci number can also be calculated using the generating function.

The generating function for the Nth Fibonacci number is given by:

Therefore, the generating function of the sum of Fibonacci numbers is given by:

After partial fraction decomposition of G'(X), the value of G'(X) is given by:

where,

Therefore, the formula for the sum of the Fibonacci numbers is given by:

Below is the implementation of the above approach:

Java

import java.io.*;

class GFG {

public static void sumFib(int N)

{

double num = (1 – Math.sqrt(5)) / 2;

long val = Math.round(

Math.abs(1

/ (Math.pow(num, N + 2)

+ Math.pow(num, N + 1)

+ Math.pow(num, N)

+ Math.pow(num, N – 1)))

– 1);

System.out.println(val);

}

public static void main(String[] args)

{

int N = 3;

sumFib(N);

}

}

Time Complexity: O(1)Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.