Posted on by Kalkicode
Code Mathematics

# Sum of n Fibonacci number in constant time

The problem involves finding the sum of the first n Fibonacci numbers in constant time, meaning the time complexity should not increase with n. Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The challenge here is to find a formula or approach that can calculate the sum without iterating through all n numbers.

## Problem Statement

Given an integer n, the task is to find the sum of the first n Fibonacci numbers in constant time.

## Example

Let's consider n = 7 as an example. The Fibonacci sequence starts with 0 and 1, and the next numbers are obtained by adding the previous two numbers:

Fibonacci sequence: [0, 1, 1, 2, 3, 5, 8, ...]

The sum of the first 7 Fibonacci numbers is 0 + 1 + 1 + 2 + 3 + 5 + 8 = 20.

## Idea to Solve

The idea to solve this problem involves using the mathematical properties of the Fibonacci sequence. A formula known as Binet's formula provides a way to directly calculate the n-th Fibonacci number using the golden ratio and its conjugate. By using this formula, we can derive a formula for the sum of the first n Fibonacci numbers.

## Pseudocode

``````function sumFibonacciNo(n)
if n > 0
golden_ratio = (1 + sqrt(5)) / 2
sum = round((pow(golden_ratio, n + 1) - (-1 / golden_ratio^n + 1)) / sqrt(5))
print "Sum of", n, "Fibonacci numbers is", sum
else
print "Invalid value", n``````

## Algorithm Explanation

1. Check if n is greater than 0.
2. Calculate the golden ratio using the formula `(1 + sqrt(5)) / 2`.
3. Use Binet's formula to calculate the sum of the first n Fibonacci numbers:
• `sum = round((pow(golden_ratio, n + 1) - (-1 / golden_ratio^n + 1)) / sqrt(5))`
4. Print the result.

## Solution

``````/*
C program for
Sum of n Fibonacci number in constant time
*/
#include <stdio.h>
#include <math.h>

void sumFibonacciNo(int n)
{
if (n > 0)
{
long long int sum = round(pow((sqrt(5) + 1) / 2.0, n + 1) / sqrt(5));
// Display calculated result
printf("\n Sum of %d fibonacci number is %lld", n, sum - 1);
}
else
{
printf("\n Invalid %d value", n);
}
}
int main(int argc, char const *argv[])
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
sumFibonacciNo(7);
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
sumFibonacciNo(10);
return 0;
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````/*
Java program for
Sum of n Fibonacci number in constant time
*/
public class FibonacciSeries
{
public void sumFibonacciNo(int n)
{
if (n > 0)
{
long sum = Math.round(
Math.pow((Math.sqrt(5) + 1) / 2.0, n + 1) /
Math.sqrt(5));
// Display calculated result
System.out.print("\n Sum of " +
n + " fibonacci number is " + (sum - 1));
}
else
{
System.out.print("\n Invalid " + n + " value");
}
}
public static void main(String[] args)
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````// Include header file
#include <iostream>

#include <math.h>

using namespace std;
/*
C++ program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
public: void sumFibonacciNo(int n)
{
if (n > 0)
{
long sum = round(
pow((sqrt(5) + 1) / 2.0, n + 1) / sqrt(5)
);
// Display calculated result
cout << "\n Sum of " << n
<< " fibonacci number is " << (sum - 1);
}
else
{
cout << "\n Invalid " << n << " value";
}
}
};
int main()
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
return 0;
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````// Include namespace system
using System;
/*
Csharp program for
Sum of n Fibonacci number in constant time
*/
public class FibonacciSeries
{
public void sumFibonacciNo(int n)
{
if (n > 0)
{
double sum = Math.Round(
Math.Pow((Math.Sqrt(5) + 1) / 2.0, n + 1) / Math.Sqrt(5)
);
// Display calculated result
Console.Write("\n Sum of " +
n + " fibonacci number is " + (sum - 1));
}
else
{
Console.Write("\n Invalid " + n + " value");
}
}
public static void Main(String[] args)
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````package main
import "math"
import "fmt"
/*
Go program for
Sum of n Fibonacci number in constant time
*/

func sumFibonacciNo(n int) {
if n > 0 {
var sum  = math.Round(math.Pow((math.Sqrt(5.0) + 1) / 2.0,
float64(n + 1)) / math.Sqrt(5.0))
// Display calculated result
fmt.Print("\n Sum of ", n, " fibonacci number is ", (sum - 1))
} else {
fmt.Print("\n Invalid ", n, " value")
}
}
func main() {
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
sumFibonacciNo(7)
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
sumFibonacciNo(10)
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````<?php
/*
Php program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
public	function sumFibonacciNo(\$n)
{
if (\$n > 0)
{
\$sum = round(pow((sqrt(5) + 1) / 2.0, \$n + 1) / sqrt(5));
// Display calculated result
echo("\n Sum of ".\$n.
" fibonacci number is ".(\$sum - 1));
}
else
{
echo("\n Invalid ".\$n." value");
}
}
}

function main()
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
main();``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````/*
Node JS program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
sumFibonacciNo(n)
{
if (n > 0)
{
var sum = Math.round(
Math.pow((Math.sqrt(5) + 1) / 2.0, n + 1) / Math.sqrt(5)
);
// Display calculated result
process.stdout.write("\n Sum of " +
n + " fibonacci number is " + (sum - 1));
}
else
{
process.stdout.write("\n Invalid " + n + " value");
}
}
}

function main()
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
main();``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````import math
#    Python 3 program for
#    Sum of n Fibonacci number in constant time
class FibonacciSeries :
def sumFibonacciNo(self, n) :
if (n > 0) :
sum = round(
(((math.sqrt(5) + 1) / 2.0) ** (n + 1)) / math.sqrt(5)
)
#  Display calculated result
print("\n Sum of", n ,"fibonacci number is ", (sum - 1), end = "")
else :
print("\n Invalid ", n ," value", end = "")

def main() :
#  Fibonacci sequence
#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
#   Test A
#   n = 7
#   0 + 1 + 1 + 2 + 3 + 5 + 8
#   ----------------------------------------
#   20
#   Test B
#   n = 10
#   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
#   -----------------------------------------
#   88

if __name__ == "__main__": main()``````

#### Output

`````` Sum of 7 fibonacci number is  20
Sum of 10 fibonacci number is  88``````
``````#    Ruby program for
#    Sum of n Fibonacci number in constant time
class FibonacciSeries
def sumFibonacciNo(n)
if (n > 0)
sum = (
(((Math.sqrt(5) + 1) / 2.0) ** (n + 1)) / Math.sqrt(5)
).round
#  Display calculated result
print("\n Sum of ", n ," fibonacci number is ", (sum - 1))
else

print("\n Invalid ", n ," value")
end

end

end

def main()
#  Fibonacci sequence
#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
#   Test A
#   n = 7
#   0 + 1 + 1 + 2 + 3 + 5 + 8
#   ----------------------------------------
#   20
#   Test B
#   n = 10
#   0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
#   -----------------------------------------
#   88
end

main()``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````/*
Scala program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries()
{
def sumFibonacciNo(n: Int): Unit = {
if (n > 0)
{
var sum: Long = Math.round(
Math.pow((scala.math.sqrt(5) + 1) / 2.0, n + 1) /
scala.math.sqrt(5)
);
// Display calculated result
print("\n Sum of " + n + " fibonacci number is " + (sum - 1));
}
else
{
print("\n Invalid " + n + " value");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: FibonacciSeries = new FibonacciSeries();
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````
``````import Foundation;
/*
Swift 4 program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
func sumFibonacciNo(_ n: Int)
{
if (n > 0)
{
let sum =
round(
pow(((5).squareRoot() + 1) / 2.0, Double(n + 1)) /
(5).squareRoot()
);
// Display calculated result
print("\n Sum of",
n ,"fibonacci number is",
(sum - 1), terminator: "");
}
else
{
print("\n Invalid ", n ," value", terminator: "");
}
}
}
func main()
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}
main();``````

#### Output

`````` Sum of 7 fibonacci number is 20.0
Sum of 10 fibonacci number is 88.0``````
``````/*
Kotlin program for
Sum of n Fibonacci number in constant time
*/
class FibonacciSeries
{
fun sumFibonacciNo(n: Int): Unit
{
if (n > 0)
{
val sum = Math.round(
Math.pow(
(Math.sqrt(5.0) + 1) / 2.0, (n + 1).toDouble()) /
Math.sqrt(5.0)
);
// Display calculated result
print("\n Sum of " + n + " fibonacci number is " + (sum - 1));
}
else
{
print("\n Invalid " + n + " value");
}
}
}
fun main(args: Array < String > ): Unit
{
// Fibonacci sequence
// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377...]
/*
Test A
n = 7
0 + 1 + 1 + 2 + 3 + 5 + 8
----------------------------------------
20
*/
/*
Test B
n = 10
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34
-----------------------------------------
88
*/
}``````

#### Output

`````` Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88``````

## Time Complexity

The time complexity of this algorithm is constant, O(1), as it involves only a few mathematical calculations that do not depend on the input size. The space complexity is also constant, as it uses a fixed number of variables.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post