Sum of squares of first N numbers ( Σ n² )

Reading time: 30 minutes | Coding time: 2 minutes

Our focus is to find the sum of the quares of the first N numbers that is from 1 to N. The simplest approach is to square each number and add it which will take linear time (N) if we assume multiplication takes constant time. With an insightful equation, we can solve this in constant time O(1).

Example:

If N = 5, then the sum F_2(5) is:

Sum = 1^2 + 2^2 + 3^2 + 4^2 + 5^2
Sum =  1  +  4  +  9  +  16 +  25
Sum = 55 

Let F_2(N) be the function denoting the sum of squares of the first N numbers.

The insightful equation is:

$$ F_2(N) = \sum_{x=1}^N x^2 = N * (N+1) * (2*N + 1) / 6 $$

If we apply if for N = 5, we get:

F_2(5) = 5 * 6 * 11 / 6 = 5 * 11 = 55

There are two approaches to arrive at the solution:

• Induction method
• Binomial method

In Induction method, we will assume a equation of a degree as a solution and used known results to find the actual parameters of the equation. Provided you started with the right degree polynomial, this method will give you the right answer.

In Binomial method, we will start with an expansion of an equation and use it and solution of sum of first N integers to arrive at our current solution. This depends to previous results but is an elegant result.

Induction method

Let us assume that the polynomial of degree 3 captures the sum. So, our equation will look like:

F_2(X) = A * X^3 + B * X^2 + C * X + D

As there are 4 parameters (A, B, C and D), we will need 4 pre-known solutions to solve this. Following are the four solutions:

F_2(0) = 0
F_2(1) = 1 = 1^2
F_2(2) = 5 = 1^2 + 2^2
F_2(3) = 14 = 1^2 + 2^2 + 3^2

We have choosen 4 values of X = 0, 1, 2 and 3.

When we place this in our initial equation, we get the following:

F_2(0) = D = 0                   ... EQ(1.1)
F_2(1) = A + B + C + D = 1       ... EQ(1.2)
F_2(2) = 8A + 4B + 2C + D = 5    ... EQ(1.3)
F_2(3) = 27A + 9B + 3C + D = 14  ... EQ(1.4)

With EQ(1.1), we get the value of D as 0. With this the rest of the three equations are modified as:

F_2(1) = A + B + C = 1       ... EQ(1.21)
F_2(2) = 8A + 4B + 2C = 5    ... EQ(1.31)
F_2(3) = 27A + 9B + 3C = 14  ... EQ(1.41)

To solve for A, B and C, we need to solve the above equations.

EQ(2.1) = EQ(1.31) - 4 * EQ(1.21) 
EQ(2.2) = EQ(1.41) - 9 * EQ(1.21)

We get EQ(2.1) and EQ(2.2) as follows:

EQ(2.1) = 4A - 2C = 1
EQ(2.2) = 18A - 6C = 5

Now, if we do the following, we will get the value of A.

EQ(2.2) - 3 * EQ(2.1)
6A - 0 = 2
A = 1/3

With A = 1/3 in EQ(2.1), we will get the value of C as follows:

4*(1/3) - 2C = 1
2C = 1/3
C = 1/6

Now, with A = 1/3 and C = 1/6 in EQ(1.21), we get the following:

A + B + C = 1       ... EQ(1.21)
1/3 + B + 1/6 = 1
B = 1 - 1/2
B = 1/2

Hence, the value of coefficients are:

A = 1/3
B = 1/2
C = 1/6
D = 0

With this, our final equation is:

F_2(X) = (1/3) * X^3 + (1/2) * X^2 + (1/6) * X
F_2(X) = (2 * X^3 + 3 * X^2 + X) / 6
F_2(X) = X * (2 * X^2 + 3 * X + 1) / 6
F_2(X) = X * (X+1) * (2X-1) / 6

Hence, we have arrive at the equation. Use it and enjoy its power.

Binomial method

To arrive at the solution, we will expand this expression (X-1)^3. Our focus is to find F_2(x) (Let us denote this as EQ1):

$$ F_2(x) = 1^2 + 2^2 + ... + x^2 $$

We know that (EQ2):

$$ F_0(x) = \sum_{i=1}^N i^0 = 1^0 + 2^0 + ... + x^0 = x $$

$$ F_1(x) = \sum_{i=1}^N i^1 = 1^1 + 2^1 + ... + x^1 = x * (x+1) / 2 $$

Another relation, we will need is the following (EQ3):

$$ \sum_{x=1}^N x^3 - \sum_{x=1}^N (x-1)^3 = N^3 $$

This is because all terms are cancelled except the last one. Follow this to get the idea:

Σ x^3 - Σ (x-1)^3
= Σ (x^3 - (x-1)^3)
= (1^3 - 0^3 ) + (2^3 - 1^3) + ... + (N^3 - (N-1)^3)
// move negative terms to the end
= 1^3 + 2^3 + ... + N^3 - 0^3 - 1^3 - 2^3 - ... - (N-1)^3
// terms are cancelled except N^3
= N^3

Now, as we have prepared everything, we shall move to the final step. Let us expand (x-1)^3.

(X-1)^3 = (X-1)(X^2 +1-2X) = X^3 - 3*X^2 + 3X - 1

If we place summation in this above expansion, we will get the following (EQ4):

   Σ (x-1)^3 = Σ x^3 - 3 * Σ x^2 + 3 * Σ x - Σ 1
=> Σ x^3 - Σ (x-1)^3 = 3 * Σ x^2 - 3 * Σ x + Σ 1

Now, if we use EQ1, EQ2 and EQ3 on EQ4, we get the following:

$$ \sum_{x=1}^N x^3 - \sum_{x=1}^N (x-1)^3 = 3 * \sum_{x=1}^N x^2 - 3 * \sum_{x=1}^N x + \sum_{x=1}^N 1 $$

$$ N^3 = 3 * F_2(N) - 3 * F_1(N) + N $$

$$ N^3 = 3 * F_2(N) - 3 * N * (N+1) / 2 + N $$

$$ F_2(N) = ( N^3 + 3 * N * (N+1) / 2 - N ) / 3 $$

$$ F_2(N) = (2 * N^3 + 3 * N^2 + N ) / 6 $$

$$ F_2(N) = N * (2 * N^2 + 3 * N + 1 ) / 6 $$

$$ F_2(N) = N * (N+1) * (2N+1) / 6 $$

Hence, we have arrived at our solution.

With this, we can find the sum of squares of first N numbers in constant time.

Implementation

Following is the implementation of the above technique:

class opengenus 
{
    static int sum(int N)
    {
        return N * (N+1) * (2*N+1) / 6;
    }
	public static void main (String[] args) 
	{
		int N = 10;
		int answer = sum(N);
		System.out.println(answer);
	}
}

Output:

385

With this, you have the complete knowledge of this domain. Enjoy.