Sum of Fibonacci Numbers

Given a number positive number n, find value of f₀ + f₁ + f₂ + …. + f_n where f_i indicates i’th Fibonacci number. Remember that f₀ = 0, f₁ = 1, f₂ = 1, f₃ = 2, f₄ = 3, f₅ = 5, …
Examples :

Input  : n = 3
Output : 4
Explanation : 0 + 1 + 1 + 2  = 4

Input  :  n = 4
Output :  7
Explanation : 0 + 1 + 1 + 2 + 3  = 7

Method 1 (O(n))
Brute Force approach is pretty straight forward, find all the Fibonacci numbers till f(n) and then add them up.

C++

// C++ Program to find sum of Fibonacci numbers 
#include<bits/stdc++.h> 
using namespace std; 
  
// Computes value of first fibonacci numbers 
int calculateSum(int n) 
{ 
    if (n <= 0) 
       return 0; 
  
    int fibo[n+1]; 
    fibo[0] = 0, fibo[1] = 1; 
  
    // Initialize result 
    int sum = fibo[0] + fibo[1]; 
  
    // Add remaining terms 
    for (int i=2; i<=n; i++) 
    { 
        fibo[i] = fibo[i-1]+fibo[i-2]; 
        sum += fibo[i]; 
    } 
  
    return sum; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int n = 4; 
    cout << "Sum of Fibonacci numbers is : "
         << calculateSum(n) << endl; 
    return 0; 
} 

Java

// Java Program to find 
// sum of Fibonacci numbers 
  
import java.io.*; 
  
class GFG { 
      
    // Computes value of first 
    // fibonacci numbers 
    static int calculateSum(int n) 
    { 
        if (n <= 0) 
           return 0; 
       
        int fibo[]=new int[n+1]; 
        fibo[0] = 0; fibo[1] = 1; 
       
        // Initialize result 
        int sum = fibo[0] + fibo[1]; 
       
        // Add remaining terms 
        for (int i=2; i<=n; i++) 
        { 
            fibo[i] = fibo[i-1]+fibo[i-2]; 
            sum += fibo[i]; 
        } 
       
        return sum; 
    } 
       
    // Driver program to test above function 
    public static void main(String args[]) 
    { 
        int n = 4; 
        System.out.println("Sum of Fibonacci" +  
        " numbers is : "+ calculateSum(n)); 
    } 
} 
  
// This code is contributed by Nikita tiwari. 

Python3

# Python 3 Program to find 
# sum of Fibonacci numbers 
  
  
# Computes value of first 
# fibonacci numbers 
def calculateSum(n) : 
    if (n <= 0) : 
        return 0
   
    fibo =[0] * (n+1) 
    fibo[1] = 1
   
    # Initialize result 
    sm = fibo[0] + fibo[1] 
   
    # Add remaining terms 
    for i in range(2,n+1) : 
        fibo[i] = fibo[i-1] + fibo[i-2] 
        sm = sm + fibo[i] 
          
    return sm 
  
  
# Driver program to test 
# above function 
n = 4
print("Sum of Fibonacci numbers is : " , 
      calculateSum(n)) 
  
# This code is contributed 
# by Nikita tiwari. 

C#

// C# Program to find 
// sum of Fibonacci numbers 
using System; 
  
class GFG  
{ 
      
    // Computes value of first 
    // fibonacci numbers 
    static int calculateSum(int n) 
    { 
        if (n <= 0) 
        return 0; 
      
        int []fibo = new int[n + 1]; 
        fibo[0] = 0; fibo[1] = 1; 
      
        // Initialize result 
        int sum = fibo[0] + fibo[1]; 
      
        // Add remaining terms 
        for (int i = 2; i <= n; i++) 
        { 
            fibo[i] = fibo[i - 1] + fibo[i - 2]; 
            sum += fibo[i]; 
        } 
      
        return sum; 
    } 
      
    // Driver Code 
    static void Main() 
    { 
        int n = 4; 
        Console.WriteLine( "Sum of Fibonacci" +  
                              " numbers is : "+  
                              calculateSum(n)); 
    } 
} 
  
// This code is contributed by Anuj_67 

PHP

<?php 
// PHP Program to find sum  
// of Fibonacci numbers 
  
// Computes value of first  
// fibonacci numbers 
function calculateSum($n) 
{ 
    if ($n <= 0) 
    return 0; 
  
    $fibo[0] = 0; 
    $fibo[1] = 1; 
  
    // Initialize result 
    $sum = $fibo[0] + $fibo[1]; 
  
    // Add remaining terms 
    for($i = 2; $i <= $n; $i++) 
    { 
        $fibo[$i] = $fibo[$i - 1] +  
                    $fibo[$i - 2]; 
        $sum += $fibo[$i]; 
    } 
  
    return $sum; 
} 
  
    // Driver Code 
    $n = 4; 
    echo "Sum of Fibonacci numbers is : ", 
          calculateSum($n),"
"; 
  
// This code is contributed by aj_36 
?> 

Output :

Sum of Fibonacci numbers is : 7

Method 2 (O(Log n))
The idea is to find relationship between the sum of Fibonacci numbers and n’th Fibonacci number.

F(i) refers to the i’th Fibonacci number.
S(i) refers to sum of Fibonacci numbers till F(i),

We can rewrite the relation F(n+1) = F(n) + F(n-1) as below
F(n-1)    = F(n+1)  -  F(n)

Similarly,
F(n-2)    = F(n)    -  F(n-1)
.          .           .
.          .             .
.          .             .
F(0)      = F(2)    -  F(1)
-------------------------------

Adding all the equations, on left side, we have
F(0) + F(1) + … F(n-1) which is S(n-1).

Therefore,
S(n-1) = F(n+1) – F(1)
S(n-1) = F(n+1) – 1
S(n) = F(n+2) – 1 —-(1)

In order to find S(n), simply calculate the (n+2)’th Fibonacci number and subtract 1 from the result.

F(n) can be evaluated in O(log n) time using either method 5 or method 6 in this article (Refer to methods 5 and 6).

Below is the implementation based on method 6 of this

C++

// C++ Program to find sum of Fibonacci numbers in  
// O(Log n) time. 
#include <bits/stdc++.h> 
using namespace std; 
const int MAX = 1000; 
  
// Create an array for memoization 
int f[MAX] = {0}; 
  
// Returns n'th Fibonacci number using table f[] 
int fib(int n) 
{ 
    // Base cases 
    if (n == 0) 
        return 0; 
    if (n == 1 || n == 2) 
        return (f[n] = 1); 
  
    // If fib(n) is already computed 
    if (f[n]) 
        return f[n]; 
  
    int k = (n & 1)? (n+1)/2 : n/2; 
  
    // Applying above formula [Note value n&1 is 1 
    // if n is odd, else 0]. 
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) 
           : (2*fib(k-1) + fib(k))*fib(k); 
  
    return f[n]; 
} 
  
// Computes value of first Fibonacci numbers 
int calculateSum(int n) 
{ 
    return fib(n+2) - 1; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int n = 4; 
    cout << "Sum of Fibonacci numbers is : "
         << calculateSum(n) << endl; 
    return 0; 
} 

Java

// Java Program to find sum 
// of Fibonacci numbers in  
// O(Log n) time. 
import java.io.*; 
import java.util.*; 
  
class GFG { 
    static int MAX = 1000; 
  
    // Create an array for memoization 
    static int f[] = new int[MAX]; 
      
    // Returns n'th Fibonacci  
    // number using table f[] 
    static int fib(int n) 
    { 
        Arrays.fill(f, 0); 
        // Base cases 
        if (n == 0) 
            return 0; 
        if (n == 1 || n == 2) 
            return (f[n] = 1); 
      
        // If fib(n) is already computed 
        if (f[n] == 1) 
            return f[n]; 
            int k; 
        if((n & 1) == 1)  
            k = (n + 1) / 2 ; 
        else
            k = n / 2; 
      
        // Applying above formula  
        // [Note value n&1 is 1  
        // if n is odd, else 0]. 
        if((n & 1) == 1)  
            f[n] = (fib(k) * fib(k) + 
            fib(k - 1) * fib(k - 1)); 
        else
            f[n] = (2 * fib(k - 1) + fib(k)) * fib(k); 
      
        return f[n]; 
    } 
      
    // Computes value of first  
    // Fibonacci numbers 
    static int calculateSum(int n) 
    { 
        return fib(n + 2) - 1; 
    } 
      
    // Driver program 
    public static void main(String args[]) 
    { 
        int n = 4; 
        System.out.println( "Sum of Fibonacci numbers is : "
                          + calculateSum(n)); 
          
    } 
} 
  
  
/*This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 Program to find sum of  
# Fibonacci numbers in O(Log n) time. 
  
MAX = 1000
  
# Create an array for memoization 
f = [0] * MAX
  
# Returns n'th Fibonacci number 
# using table f[] 
def fib(n): 
      
    n = int(n) 
  
    # Base cases 
    if (n == 0): 
        return 0
    if (n == 1 or n == 2): 
        return (1)  
  
    # If fib(n) is already computed 
    if (f[n] == True): 
        return f[n]  
  
    k = (n+1)/2 if (n & 1) else n/2
  
    # Applying above formula [Note value n&1  
    # is 1 if n is odd, else 0]. 
    f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1)) if (n & 1) else (2 * fib(k-1) + fib(k)) * fib(k) 
    return f[n]  
  
# Computes value of first Fibonacci numbers 
def calculateSum(n): 
  
    return fib(n+2) - 1
  
# Driver program to test above function 
n = 4
print("Sum of Fibonacci numbers is :", calculateSum(n))  
  
# This code is contributed by 
# Smitha Dinesh Semwal 

C#

// C# Program to find sum 
// of Fibonacci numbers in  
// O(Log n) time. 
using System; 
  
class GFG { 
    static int MAX = 1000; 
  
    // Create an array for memoization 
    static int []f = new int[MAX]; 
      
    // Returns n'th Fibonacci  
    // number using table f[] 
    static int fib(int n) 
    { 
        for(int i = 0;i < MAX;i++) 
        f[i] = 0; 
          
        //Arrays.fill(f, 0); 
        // Base cases 
        if (n == 0) 
            return 0; 
        if (n == 1 || n == 2) 
            return (f[n] = 1); 
      
        // If fib(n) is  
        // already computed 
        if (f[n] == 1) 
            return f[n]; 
            int k; 
        if((n & 1) == 1)  
            k = (n + 1) / 2 ; 
        else
            k = n / 2; 
      
        // Applying above formula  
        // [Note value n&1 is 1  
        // if n is odd, else 0]. 
        if((n & 1) == 1)  
            f[n] = (fib(k) * fib(k) + fib(k - 1) 
                                   * fib(k - 1)); 
        else
            f[n] = (2 * fib(k - 1) + fib(k)) * 
                                       fib(k); 
      
        return f[n]; 
    } 
      
    // Computes value of first  
    // Fibonacci numbers 
    static int calculateSum(int n) 
    { 
        return fib(n + 2) - 1; 
    } 
      
    // Driver Code 
    public static void Main() 
    { 
        int n = 4; 
        Console.Write( "Sum of Fibonacci numbers is : "
                                    + calculateSum(n)); 
          
    } 
} 
  
// This code is contributed by nitin mittal. 

PHP

<?php 
// PHP Program to find sum of Fibonacci  
// numbers in O(Log n) time. 
$MAX = 1000; 
  
// Create an array for memoization 
$f = array_fill(0, $MAX, 0); 
  
// Returns n'th Fibonacci number  
// using table f[] 
function fib($n) 
{ 
    global $f; 
      
    // Base cases 
    if ($n == 0) 
        return 0; 
    if ($n == 1 || $n == 2) 
        return ($f[$n] = 1); 
  
    // If fib(n) is already computed 
    if ($f[$n]) 
        return $f[$n]; 
  
    $k = ($n & 1) ? ($n + 1) / 2 : $n / 2; 
  
    // Applying above formula [Note value n&1  
    // is 1 if n is odd, else 0]. 
    $f[$n] = ($n & 1) ?  
             (fib($k) * fib($k) + fib($k - 1) * fib($k - 1)) :  
                  (2 * fib($k - 1) + fib($k)) * fib($k); 
  
    return $f[$n]; 
} 
  
// Computes value of first Fibonacci numbers 
function calculateSum($n) 
{ 
    return fib($n + 2) - 1; 
} 
  
// Driver Code 
$n = 4; 
print("Sum of Fibonacci numbers is : " .  
                      calculateSum($n)); 
  
// This code is contributed by mits 
?> 

Output :

Sum of Fibonacci numbers is : 7

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

C++

Java

Python3

C#

PHP

C++

Java

Python3

C#

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books