Posted on by Kalkicode
Code Number

Sum of squares of Fibonacci Numbers

The given problem is to find the sum of the squares of the first 'n' Fibonacci numbers. Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The Fibonacci sequence begins with 0 and 1, and each subsequent number is the sum of the two previous numbers.

Problem Statement

We are given an integer 'n' representing the number of Fibonacci numbers to consider. The task is to calculate the sum of the squares of the first 'n' Fibonacci numbers.

Explanation with an Example

Let's take a simple example to understand the problem. Consider 'n' is 5.

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

The first five Fibonacci numbers are: 0, 1, 1, 2, and 3.

Now, we need to find the sum of the squares of these five Fibonacci numbers.

Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² = 0 + 1 + 1 + 4 + 9 = 15

So, the sum of the squares of the first 5 Fibonacci numbers is 15.

Standard Pseudocode

Before diving into the algorithm, let's write the standard pseudocode for the problem:

function sumFibonacciSquares(n)
    sum = 0
    if n > 1
        create auxiliary array with size n
        auxiliary[0] = 0
        auxiliary[1] = 1
        for i from 0 to n-1
            if i > 1
                auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
            sum += (auxiliary[i] * auxiliary[i])
    print "Sum of", n, "fibonacci square number is", sum

Algorithm Explanation

  1. Initialize a variable sum to keep track of the sum of squares of Fibonacci numbers. Set it to 0 initially.
  2. Check if 'n' is greater than 1. If it is not, then there's no need to calculate anything, so we can return.
  3. Create an auxiliary array of integers with a size of 'n' to store the Fibonacci sequence.
  4. Set the first two elements of the auxiliary array to 0 and 1, respectively, as these are the first two Fibonacci numbers.
  5. Use a loop to calculate the next Fibonacci numbers up to the 'n'th number and store them in the auxiliary array.
  6. During each iteration, calculate the square of the current Fibonacci number and add it to the sum.
  7. Once the loop is completed, the sum will contain the sum of the squares of the first 'n' Fibonacci numbers.
  8. Print the value of sum as the final output.

Code Solution

Here given code implementation process.

/*
    C program for
    Sum of squares of Fibonacci Numbers 
*/
#include <stdio.h>

void sumFibonacciSquares(int n)
{
	long long int sum = 0;
	if (n > 1)
	{
		// Create auxiliary space
		int auxiliary[n];
		// 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];
			}
			// sum squares of fibonacci number
			sum += (auxiliary[i] *auxiliary[i]);
		}
	}
	printf("\n Sum of %d fibonacci square number is %lld", n, sum);
}
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 = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	sumFibonacciSquares(10);
	return 0;
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
/*
    Java program for
    Sum of squares of Fibonacci Numbers 
*/
public class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	public void sumFibonacciSquares(int n)
	{
		long sum = 0;
		if (n > 1)
		{
			// Create auxiliary space
			int[] auxiliary = new int[n];
			// 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];
				}
				// sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i]);
			}
		}
		System.out.print("\n Sum of " + 
                         n + " fibonacci square number is " + sum);
	}
	public static void main(String[] args)
	{
		FibonacciSeries task = new FibonacciSeries();
		// Fibonacci sequence
		// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
		/*
		   Test A
		   n = 5
		   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
		*/
		task.sumFibonacciSquares(5);
		/*
		   Test B
		   n = 10
		   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
		   (8)² + (13)² + (21)² + (34)² = 1870
		*/
		task.sumFibonacciSquares(10);
	}
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries
{
	public:
		// Here n indicates number of initial Fibonacci series elements
		void sumFibonacciSquares(int n)
		{
			long sum = 0;
			if (n > 1)
			{
				// Create auxiliary space
				int auxiliary[n];
				// 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];
					}
					// sum squares of fibonacci number
					sum += (auxiliary[i] *auxiliary[i]);
				}
			}
			cout << "\n Sum of " << n 
          		 << " fibonacci square number is " << sum;
		}
};
int main()
{
	FibonacciSeries *task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	task->sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	task->sumFibonacciSquares(10);
	return 0;
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
// Include namespace system
using System;
/*
    Csharp program for
    Sum of squares of Fibonacci Numbers 
*/
public class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	public void sumFibonacciSquares(int n)
	{
		long sum = 0;
		if (n > 1)
		{
			// Create auxiliary space
			int[] auxiliary = new int[n];
			// 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];
				}
				// sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i]);
			}
		}
		Console.Write("\n Sum of " + n + 
                      " fibonacci square number is " + sum);
	}
	public static void Main(String[] args)
	{
		FibonacciSeries task = new FibonacciSeries();
		// Fibonacci sequence
		// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
		/*
		   Test A
		   n = 5
		   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
		*/
		task.sumFibonacciSquares(5);
		/*
		   Test B
		   n = 10
		   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
		   (8)² + (13)² + (21)² + (34)² = 1870
		*/
		task.sumFibonacciSquares(10);
	}
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
package main
import "fmt"
/*
    Go program for
    Sum of squares of Fibonacci Numbers 
*/

// Here n indicates number of initial Fibonacci series elements
func sumFibonacciSquares(n int) {
	var sum int64 = 0
	if n > 1 {
		// Create auxiliary space
		var auxiliary = make([] int, n)
		// Set initial sequence
		auxiliary[0] = 0
		auxiliary[1] = 1
		// Calculate the sum of n fibonacci numbers
		for i := 0 ; i < n ; i++ {
			if i > 1 {
				auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
			}
			// sum squares of fibonacci number
			sum += int64(auxiliary[i] * auxiliary[i])
		}
	}
	fmt.Print("\n Sum of ", 
		n, " fibonacci square number is ", sum)
}
func main() {
	
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	sumFibonacciSquares(5)
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	sumFibonacciSquares(10)
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
<?php
/*
    Php program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	public	function sumFibonacciSquares($n)
	{
		$sum = 0;
		if ($n > 1)
		{
			// Create auxiliary space
			$auxiliary = array_fill(0, $n, 0);
			// Set initial sequence
			$auxiliary[0] = 0;
			$auxiliary[1] = 1;
			// Calculate the sum of n fibonacci numbers
			for ($i = 0; $i < $n; ++$i)
			{
				if ($i > 1)
				{
					$auxiliary[$i] = $auxiliary[$i - 2] + $auxiliary[$i - 1];
				}
				// sum squares of fibonacci number
				$sum += ($auxiliary[$i] * $auxiliary[$i]);
			}
		}
		echo("\n Sum of ".$n.
			" fibonacci square number is ".$sum);
	}
}

function main()
{
	$task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	$task->sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	$task->sumFibonacciSquares(10);
}
main();

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
/*
    Node JS program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	sumFibonacciSquares(n)
	{
		var sum = 0;
		if (n > 1)
		{
			// Create auxiliary space
			var auxiliary = Array(n).fill(0);
			// Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			// 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];
				}
				// sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i]);
			}
		}
		process.stdout.write("\n Sum of " + 
                             n + " fibonacci square number is " + sum);
	}
}

function main()
{
	var task = new FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	task.sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	task.sumFibonacciSquares(10);
}
main();

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
#    Python 3 program for
#    Sum of squares of Fibonacci Numbers 
class FibonacciSeries :
	#  Here n indicates number of initial Fibonacci series elements
	def sumFibonacciSquares(self, n) :
		sum = 0
		if (n > 1) :
			#  Create auxiliary space
			auxiliary = [0] * (n)
			#  Set initial sequence
			auxiliary[0] = 0
			auxiliary[1] = 1
			i = 0
			#  Calculate the sum of n fibonacci numbers
			while (i < n) :
				if (i > 1) :
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
				
				#  sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i])
				i += 1
			
		
		print("\n Sum of", n ,"fibonacci square number is ", 
              sum, end = "")
	

def main() :
	task = FibonacciSeries()
	#  Fibonacci sequence
	#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	#   Test A
	#   n = 5
	#   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	task.sumFibonacciSquares(5)
	#   Test B
	#   n = 10
	#   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	#   (8)² + (13)² + (21)² + (34)² = 1870
	task.sumFibonacciSquares(10)

if __name__ == "__main__": main()

Output

 Sum of 5 fibonacci square number is  15
 Sum of 10 fibonacci square number is  1870
#    Ruby program for
#    Sum of squares of Fibonacci Numbers 
class FibonacciSeries 
	#  Here n indicates number of initial Fibonacci series elements
	def sumFibonacciSquares(n) 
		sum = 0
		if (n > 1) 
			#  Create auxiliary space
			auxiliary = Array.new(n) {0}
			#  Set initial sequence
			auxiliary[0] = 0
			auxiliary[1] = 1
			i = 0
			#  Calculate the sum of n fibonacci numbers
			while (i < n) 
				if (i > 1) 
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
				end

				#  sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i])
				i += 1
			end

		end

		print("\n Sum of ", n ," fibonacci square number is ", sum)
	end

end

def main() 
	task = FibonacciSeries.new()
	#  Fibonacci sequence
	#  [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	#   Test A
	#   n = 5
	#   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	task.sumFibonacciSquares(5)
	#   Test B
	#   n = 10
	#   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	#   (8)² + (13)² + (21)² + (34)² = 1870
	task.sumFibonacciSquares(10)
end

main()

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
/*
    Scala program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries()
{
	// Here n indicates number of initial Fibonacci series elements
	def sumFibonacciSquares(n: Int): Unit = {
		var sum: Long = 0;
		if (n > 1)
		{
			// Create auxiliary space
			var auxiliary: Array[Int] = Array.fill[Int](n)(0);
			// Set initial sequence
			auxiliary(0) = 0;
			auxiliary(1) = 1;
			var i: Int = 0;
			// Calculate the sum of n fibonacci numbers
			while (i < n)
			{
				if (i > 1)
				{
					auxiliary(i) = auxiliary(i - 2) + auxiliary(i - 1);
				}
				// sum squares of fibonacci number
				sum += (auxiliary(i) * auxiliary(i));
				i += 1;
			}
		}
		print("\n Sum of " + n + " fibonacci square number is " + sum);
	}
}
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 = 5
		   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
		*/
		task.sumFibonacciSquares(5);
		/*
		   Test B
		   n = 10
		   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
		   (8)² + (13)² + (21)² + (34)² = 1870
		*/
		task.sumFibonacciSquares(10);
	}
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870
/*
    Swift 4 program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	func sumFibonacciSquares(_ n: Int)
	{
		var sum: Int = 0;
		if (n > 1)
		{
			// Create auxiliary space
			var auxiliary: [Int] = Array(repeating: 0, count: n);
			// Set initial sequence
			auxiliary[0] = 0;
			auxiliary[1] = 1;
			var i: Int = 0;
			// Calculate the sum of n fibonacci numbers
			while (i < n)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i]);
				i += 1;
			}
		}
		print("\n Sum of ", n ,
              " fibonacci square number is ", sum, terminator: "");
	}
}
func main()
{
	let task: FibonacciSeries = FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	task.sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	task.sumFibonacciSquares(10);
}
main();

Output

 Sum of  5  fibonacci square number is  15
 Sum of  10  fibonacci square number is  1870
/*
    Kotlin program for
    Sum of squares of Fibonacci Numbers 
*/
class FibonacciSeries
{
	// Here n indicates number of initial Fibonacci series elements
	fun sumFibonacciSquares(n: Int): Unit
	{
		var sum: Long = 0;
		if (n > 1)
		{
			// Create auxiliary space
			var auxiliary: Array < Int > = Array(n)
			{
				0
			};
			// Set initial sequence
			auxiliary[1] = 1;
			var i: Int = 0;
			// Calculate the sum of n fibonacci numbers
			while (i < n)
			{
				if (i > 1)
				{
					auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
				}
				// sum squares of fibonacci number
				sum += (auxiliary[i] * auxiliary[i]);
				i += 1;
			}
		}
		print("\n Sum of " + n + " fibonacci square number is " + sum);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: FibonacciSeries = FibonacciSeries();
	// Fibonacci sequence
	// [0  1  1  2  3  5  8  13  21  34  55  89  144  233  377..]
	/*
	   Test A
	   n = 5
	   (0)² + (1)² + (1)² + (2)² + (3)²  = 15
	*/
	task.sumFibonacciSquares(5);
	/*
	   Test B
	   n = 10
	   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + 
	   (8)² + (13)² + (21)² + (34)² = 1870
	*/
	task.sumFibonacciSquares(10);
}

Output

 Sum of 5 fibonacci square number is 15
 Sum of 10 fibonacci square number is 1870

Resultant Output Explanation

Now, let's consider the two test cases mentioned in the code and understand their outputs.

  1. Test A: n = 5

    The first 5 Fibonacci numbers are [0, 1, 1, 2, 3]. The sum of their squares is:

    Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² = 0 + 1 + 1 + 4 + 9 = 15

    So, the output will be: "Sum of 5 fibonacci square number is 15"

  2. Test B: n = 10

    The first 10 Fibonacci numbers are [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]. The sum of their squares is:

    Sum of squares: (0)² + (1)² + (1)² + (2)² + (3)² + (5)² + (8)² + (13)² + (21)² + (34)² = 0 + 1 + 1 + 4 + 9 + 25 + 64 + 169 + 441 + 1156 = 1870

    So, the output will be: "Sum of 10 fibonacci square number is 1870"

Time Complexity

Let's analyze the time complexity of the provided code:

  1. The loop iterates 'n' times to calculate the first 'n' Fibonacci numbers.
  2. Each Fibonacci number requires O(1) time to calculate since it is the sum of the previous two numbers.
  3. Therefore, the time complexity of the loop is O(n).

Overall, the time complexity of the code is O(n), which is linear in the input 'n'. This is an efficient solution for calculating the sum of the squares of 'n' Fibonacci numbers.

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.

New Comment