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)
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
}``````

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()
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
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)
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
}``````

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()
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
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()
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
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() :
#  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
#   Test B
#   n = 10
#   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
#   (8)² + (13)² + (21)² + (34)² = 1870

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()
#  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
#   Test B
#   n = 10
#   (0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
#   (8)² + (13)² + (21)² + (34)² = 1870
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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
}``````

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()
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}
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
{
// 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
*/
/*
Test B
n = 10
(0)² + (1)² + (1)² + (2)² + (3)² + (5)² +
(8)² + (13)² + (21)² + (34)² = 1870
*/
}``````

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.

Categories
Relative Post