Sum sequence (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

In this article we will look at different ways to calculate the sum of a sequence - (n^2 - 1^2) 2(n^2 - 2^2) …. n(n ^2 - n^2). In the first method, we will calculate the sequence sum for each i in the range 1 to n one by one and add it to the final sum.

In the second approach, we will derive a mathematical formula to calculate the sum of a given series, which will reduce the time complexity of the program from O(n) to O(1).

Problem Statement − We are given a number "n" and our task is to calculate the sum of the given sequence (n^2 - 1^2) 2(n^2 - 2^2) …. n (n^2 - n^2).

Example

Input − Number = 5

Output - When n = 5, the series (n^2 - 1^2) 2(n^2 - 2^2) …. n(n^2 - n^2) The sum is 150.

Input − Number = 3

Output - For n = 3, the series (n^2 - 1^2) 2 (n^2 - 2^2) ....n (n^2 - n^2) The sum is 18.

method one

This is the simplest brute force method to solve the sequence summation problem.

After careful analysis of this sequence, we can conclude: for any number n, we have

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

So, for the brute force method, we can use the above formula in a loop, i from 1 to n, to generate the required summation.

Example

The code for this method is as follows:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 3;
   long long sum=0;
   for (int i=1  ; i<num ; i++ ) {
      sum = sum+i*( num*num - i*i );
   }
   cout<< " The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = " << num << " is " <<sum;
   return 0;
}

Output

The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = 3 is 18

Complexity

Time complexity - O(n) since we iterate through the loop through the numbers from 1 to n.

Space Complexity - Since we are not using any external space, the space complexity of this method is O(1).

Method Two

In this approach we will derive a formula that will directly get the required sequence sum, so no iterations are needed and this approach will solve the given problem with constant time complexity.

As mentioned before, we get the general version of the series, given as

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

The same series can be written as:

Sum =  n^2∑ i - ∑ i^3

We already know the formulas for calculating the sum of all numbers from 1 to n and the formula for calculating the sum of cubes of all numbers from 1 to n, respectively:

The sum of all numbers from 1 to n

n* ( n+1 )/2 

Where n is the given number.

Now, find the cube sum of all numbers from 1 to n

(n*( n+1 )/2)^2

So the given series can be written as -

Sum = n^2 * ( n*( n+1 )/2 ) – ( n*( n+1 )/2 )^2

Sum can be further simplified to -

Sum = ( n * (n+1)/2 )*( n^2 - ( n * (n+1)/2 ))
Sum = n^2 * ( n+1 )/2 * ( n^2 – (n * ( n+1))/2)
Sum = n^2 * ( n+1 ) * ( n-1 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

Thus, we only need to calculate Sum = (n^4)/4 - (n^2)/4, for any n, to get the sum of the desired sequences.

Example

The code for this method is as follows:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 5;
   long long sum = 0;
   sum = num*num*(num*num-1)/4;
   cout<< " The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = " << num << " is " <<sum;
   return 0;
}

Output

The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = 5 is 150

Complexity

Time complexity - O(1), since we just calculate the required sum using the formula we derived.

Space Complexity - Since we are not using any external space, the space complexity of this method is O(1).

Conclusion - In this article, we discussed two methods to calculate the sum of the required series and in the second method we reduced the time complexity to a constant.

The above is the detailed content of Sum sequence (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2). For more information, please follow other related articles on the PHP Chinese website!