Sum of first N numbers ( Σ n )

Reading time: 30 minutes | Coding time: 2 minutes

In this problem, we will find the sum of the first N integers that is 1 to N. In the brute force approach, we need to add each number which will take linear time O(N) but we can solve this in constant time O(1) by using an insightful formula.

For example, if N = 5, then

Answer = 1 + 2 + 3 + 4 + 5 = 15

The key formula is:

F(N) = 1 + 2 + ... + (N-1) + N = N * (N+1) / 2

Derivation of the formula

There are two simple approaches to arrive at the formula:

• Induction method
• Binomial method

Induction method requires us to define the structure of the equation we expect and use known results to find the exact coefficients for the equation. It can work on any pattern provided the equation you are starting with is valid.

Binomial method is a mathematical method which arrives at the resulting equation directly by using equations for all lower degree sums. We have clarified this in the section we have explained it.

Induction method

By experience, we can say that the equation for sum of first N numbers will be of degree 2.

F(x) = A * (x^2) + B * (x) + C 

where x will be the value of N. We need to find the exact value of the coefficients A, B and C.

Note that if the structure of our equation is wrong, it will fail in the method and the validation and on this, we shall change the degree of the equation to 3 or 1.

As this is a 2 degree equation with 3 coefficients, we need 3 base cases to calculate the coefficients. Following are the basic base cases:

F(0) = 0 // as sum of first o numbers is 0
F(1) = 1 // as sum of first 1 number (1) is 1
F(2) = 3 // as sum of first 2 numbers (1+2) is 3

Now, as we have taken 3 values for x (0, 1 and 2), we shall place these in our original equation and get three equations using the 3 coefficients (a, b and c).

F(0) = C = 0
F(1) = A + B + C = 1
F(2) = 4A + 2B + C = 3

Hence, the 3 equations are:

C = 0             EQ(1.1)
A + B + C = 1     EQ(1.2)
4A + 2B + C = 3   EQ(1.3)

Fron EQ(1.1), we get that C = 0. So, with this, the other two equations EQ(1.2) and EQ(1.3) are modified as:

A + B = 1    EQ(1.21)
4A + 2B = 3  EQ(1.31)

We need to solve the above two equations to get the value of A and B. To do so, we can do the following:

EQ(1.31) - 2 * EQ(1.21)

With this, we get:

     4A + 2B = 3   ... EQ(1.31)
(-1) 2A + 2B = 2   ... 2 * EQ(1.21)
 =   2A + 0  = 1
 
 A = 1/2

Hence, we got the value of A as 1/2.

We can place this value in any of the two equations (say EQ(1.21)) to get the value of B.

A + B = 1
1/2 + B = 1
B = 1/2

Hence, we get B as 1/2.

With this, we get the value for all three coefficients.

A = 1/2
B = 1/2
C = 0

Hence, our equation becomes:

F(x) = (1/2) * (x^2) + (1/2) * x
F(x) = (1/2) * (x) * (x+1)
F(x) = x * (x+1) / 2

You can verify the value of x = 4 as:

F(4) = 4 * 5 / 2 = 10 = 1 + 2 + 3 + 4

Hence, we have arrived at the equation by using the technique of Induction.

Binomial method

In this method, we need to find the equation by using the expansion of (x-1)^2. Our focus is to find F_1(x) (Let us denote this as EQ1):

$$ F_1(x) = 1 + 2 + ... + x $$

We know that (EQ2):

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

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

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

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

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

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

(x-1)^2 = x^2 + 1 -2x
x^2 - (x-1)^2 = 2x - 1

If we place summation in the above equation, we get:

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

Using equations EQ1 and EQ2 (which we derived previously), we get:

$$ N^2 = 2 * F_1(N) - N $$

This results in:

$$ F_1(N) = ( N^2 + N ) / 2 $$

$$ F_1(N) = N * (N+1) / 2 $$

Hence, we have arrived at the equation.

Pseudocode of this technique:

int sum(N)
{
    return N * (N+1) / 2;
}

Implementation:

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

Output:

55

With this, you have the complete knowledge of getting the sum of numbers from 1 to N in constant time O(1). Enjoy.