Saturday, 16 Oct 2021

# 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.