Sum of n fibonacci numbers

The Fibonacci sequence is a famous sequence of numbers in mathematics, where each number is the sum of the two preceding ones, starting from 0 and 1. The sum of the first n Fibonacci numbers is a common problem that has applications in various fields, including mathematics, computer science, and nature. This article aims to explain how to calculate the sum of the first n Fibonacci numbers using a C program.

Problem Statement

Given a positive integer n, the task is to calculate the sum of the first n Fibonacci numbers. The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the previous two.

Example

For instance, if n is 7, then the first 7 Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8. Their sum is 20. If n is 10, the first 10 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34. Their sum is 88.

Idea to Solve

The solution involves generating the Fibonacci sequence up to the nth number and simultaneously calculating the sum of the generated numbers. This can be done using an auxiliary array to store the Fibonacci sequence.

Pseudocode

function sum_fibonacci_number(n):
    if n <= 0:
        return
    else:
        Create an auxiliary array
        Initialize sum = 0
        Set first two numbers of the sequence
        Iterate from 0 to n-1:
            Calculate current Fibonacci number
            Add current Fibonacci number to sum
        Print "Sum of", n, "fibonacci numbers is", sum

function main():
    sum_fibonacci_number(7)
    sum_fibonacci_number(10)

Algorithm Explanation

1. The sum_fibonacci_number function takes a single parameter n.
2. It first checks if n is less than or equal to 0. If it is, the function returns without performing any calculations.
3. It creates an auxiliary array to store the Fibonacci sequence and initializes the sum as 0.
4. It sets the first two numbers of the Fibonacci sequence (0 and 1).
5. It iterates from 0 to n-1, calculating the current Fibonacci number by adding the last two numbers in the auxiliary array.
6. It adds the current Fibonacci number to the sum.
7. Finally, it prints the calculated sum along with the provided value of n.
8. The main function tests the sum_fibonacci_number function with different values of n.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// C Program
// Sum of n fibonacci numbers
#include <stdio.h>

//Calculating the sum of n fibonacci numbers
void sum_fibonacci_number(int n)
{
	if (n <= 0)
	{
		return;
	}
	else
	{
		//create auxiliary space
		int auxiliary[n];
		long long int sum = 0;
		//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377
		//Set initial sequence
		auxiliary[0] = 0;
		auxiliary[1] = 1;
		//Calculate the sum of n fibonacci numbers
		for (int i = 0; i < n; ++i)
		{
			if (i > 1)
			{
				auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
			}
			// Add fibonacci number
			sum += auxiliary[i];
		}
		printf("\n Sum of %d fibonacci number is %lld", n, sum);
	}
}
int main()
{
	//Test case
	sum_fibonacci_number(7);
	sum_fibonacci_number(10);
	return 0;
}

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

// Java Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	public void sum_fibonacci_number(int n)
	{
		if (n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			int[] auxiliary = new int[n];
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377
			//Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			//resultant variable
			long sum = 0;
			//Calculate the sum of n fibonacci numbers
			for (int i = 0; i < n; ++i)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// Add fibonacci number
				sum += auxiliary[i];
			}
			System.out.print("\n Sum of " + n + " fibonacci number is " + sum);
		}
	}
	public static void main(String[] args)
	{
		MyMaths obj = new MyMaths();
		//Test case
		obj.sum_fibonacci_number(7);
		obj.sum_fibonacci_number(10);
	
	}
}

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

//Include header file
#include <iostream>

using namespace std;
// C++ Program 
// Sum of n fibonacci numbers
class MyMaths
{
	public:
		//Calculating the sum of n fibonacci numbers
		void sum_fibonacci_number(int n)
		{
			if (n <= 0)
			{
				return;
			}
			else
			{
				//create auxiliary space
				int auxiliary[n];
				//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
				//Set initial sequence
				auxiliary[0] = 0;
				auxiliary[1] = 1;
				//resultant variable
				long sum = 0;
				//Calculate the sum of n fibonacci numbers
				for (int i = 0; i < n; ++i)
				{
					if (i > 1)
					{
						auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
					}
					// Add fibonacci number
					sum += auxiliary[i];
				}
				cout << "\n Sum of " << n << " fibonacci number is " << sum;
			}
		}
};
int main()
{
	MyMaths obj = MyMaths();
	//Test case
	obj.sum_fibonacci_number(7);
	obj.sum_fibonacci_number(10);
	return 0;
}

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

//Include namespace system
using System;
// C# Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	public void sum_fibonacci_number(int n)
	{
		if (n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			int[] auxiliary = new int[n];
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			//Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			//resultant variable
			long sum = 0;
			//Calculate the sum of n fibonacci numbers
			for (int i = 0; i < n; ++i)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// Add fibonacci number
				sum += auxiliary[i];
			}
			Console.Write("\n Sum of " + n + " fibonacci number is " + sum);
		}
	}
	public static void Main(String[] args)
	{
		MyMaths obj = new MyMaths();
		//Test case
		obj.sum_fibonacci_number(7);
		obj.sum_fibonacci_number(10);
	}
}

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

<?php
// Php Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	public	function sum_fibonacci_number($n)
	{
		if ($n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			$auxiliary = array_fill(0, $n, 0);
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			//Set initial sequence
			$auxiliary[0] = 0;
			$auxiliary[1] = 1;
			//resultant variable
			$sum = 0;
			//Calculate the sum of n fibonacci numbers
			for ($i = 0; $i < $n; ++$i)
			{
				if ($i > 1)
				{
					$auxiliary[$i] = $auxiliary[$i - 2] + $auxiliary[$i - 1];
				}
				// Add fibonacci number
				$sum += $auxiliary[$i];
			}
			echo "\n Sum of ". $n ." fibonacci number is ". $sum;
		}
	}
}

function main()
{
	$obj = new MyMaths();
	//Test case
	$obj->sum_fibonacci_number(7);
	$obj->sum_fibonacci_number(10);
}
main();

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

// Node Js Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	sum_fibonacci_number(n)
	{
		if (n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			var auxiliary = Array(n).fill(0);
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			//Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			//resultant variable
			var sum = 0;
			//Calculate the sum of n fibonacci numbers
			for (var i = 0; i < n; ++i)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// Add fibonacci number
				sum += auxiliary[i];
			}
			process.stdout.write("\n Sum of " + n + " fibonacci number is " + sum);
		}
	}
}

function main()
{
	var obj = new MyMaths();
	//Test case
	obj.sum_fibonacci_number(7);
	obj.sum_fibonacci_number(10);
}
main();

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

#  Python 3 Program 
#  Sum of n fibonacci numbers

class MyMaths :
	# Calculating the sum of n fibonacci numbers
	def sum_fibonacci_number(self, n) :
		if (n <= 0) :
			return
		else :
			# create auxiliary space
			auxiliary = [0] * n
			# Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			# Set initial sequence
			auxiliary[0] = 0
			auxiliary[1] = 1
			# loop controlling variable
			i = 0
			# resultant variable
			sum = 0
			# Calculate the sum of n fibonacci numbers
			while (i < n) :
				if (i > 1) :
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
				
				#  Add fibonacci number
				sum += auxiliary[i]
				i += 1
			
			print("\n Sum of ", n ," fibonacci number is ", sum, end = "")
		
	

def main() :
	obj = MyMaths()
	# Test case
	obj.sum_fibonacci_number(7)
	obj.sum_fibonacci_number(10)

if __name__ == "__main__": main()

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

#  Ruby Program 
#  Sum of n fibonacci numbers
class MyMaths

	# Calculating the sum of n fibonacci numbers
	def sum_fibonacci_number(n)
	
		if (n <= 0)
		
			return
		else
		
			# create auxiliary space
			auxiliary = Array.new(n) {0}
			# Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			# Set initial sequence
			auxiliary[0] = 0
			auxiliary[1] = 1
			# loop controlling variable
			i = 0
			# resultant variable
			sum = 0
			# Calculate the sum of n fibonacci numbers
			while (i < n)
			
				if (i > 1)
				
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
				end
				#  Add fibonacci number
				sum += auxiliary[i]
				i += 1
			end
			print("\n Sum of ", n ," fibonacci number is ", sum)
		end
	end
end
def main()

	obj = MyMaths.new()
	# Test case
	obj.sum_fibonacci_number(7)
	obj.sum_fibonacci_number(10)
end
main()

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

// Scala Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	def sum_fibonacci_number(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			var auxiliary: Array[Int] = Array.fill[Int](n)(0);
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			//Set initial sequence
			auxiliary(0) = 0;
			auxiliary(1) = 1;
			//loop controlling variable
			var i: Int = 0;
			//resultant variable
			var sum: Long = 0;
			//Calculate the sum of n fibonacci numbers
			while (i < n)
			{
				if (i > 1)
				{
					auxiliary(i) = auxiliary(i - 2) + auxiliary(i - 1);
				}
				// Add fibonacci number
				sum += auxiliary(i);
				i += 1;
			}
			print("\n Sum of " + n + " fibonacci number is " + sum);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyMaths = new MyMaths();
		//Test case
		obj.sum_fibonacci_number(7);
		obj.sum_fibonacci_number(10);
	}
}

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

// Swift Program 
// Sum of n fibonacci numbers
class MyMaths
{
	//Calculating the sum of n fibonacci numbers
	func sum_fibonacci_number(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		else
		{
			//create auxiliary space
			var auxiliary: [Int] = Array(repeating: 0, count: n);
			//Sequence = 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377 ...
			//Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			//loop controlling variable
			var i: Int = 0;
			//resultant variable
			var sum: Int = 0;
			//Calculate the sum of n fibonacci numbers
			while (i < n)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// Add fibonacci number
				sum += auxiliary[i];
				i += 1;
			}
			print("\n Sum of ", n ," fibonacci number is ", sum, terminator: "");
		}
	}
}
func main()
{
	let obj: MyMaths = MyMaths();
	//Test case
	obj.sum_fibonacci_number(7);
	obj.sum_fibonacci_number(10);
}
main();

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

Time Complexity

The time complexity of this code is linear, O(n), where n is the input value. This is because the code iterates through the auxiliary array once to generate the Fibonacci sequence and calculate the sum. The execution time grows linearly with the input value.