The Difference Between Sum of Squares and Square of the Sum

The sum of the squares of the first ten natural numbers is,
1^2+2^2+3^2+…10^2=385

The square of the sum of the first ten natural numbers is,
(1+2+…+10)^2=55^2=3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Bruteforce Algorithm

Given the input is 100, we can bruteforce.

1
2
3
4
5
6
7

let sum = 0;
let square_sum = 0;
for (let i = 1; i <= 100; ++ i) {
   sum += i;
   square_sum += i * i;
}
console.log(square_sum - sum * sum);

let sum = 0;
let square_sum = 0;
for (let i = 1; i <= 100; ++ i) {
   sum += i;
   square_sum += i * i;
}
console.log(square_sum - sum * sum);

The answer is 25164150

Math Formula to compute the Difference Between Sum of Squares and Square of the Sum

We know the Sum of first N Natural numbers is: . It would be great if we can find out the formula for the sum of squares.

Let’s assume is it (the sum of squares) . The first few values:

With these four equations, we can obtain the following values by solving the system of equations:

Thus, the f() function can be guessed as:

We just have to prove this by induction:

Both sides are equals, thus the correct formula has been obtained.

Therefore, it can be computed pretty quickly in O(1) constant time by any input value:

1
2
3
4

const limit = 100;
const sum = limit * (limit + 1) / 2;
const sum_eq = (2*limit + 1) * (limit + 1) * limit / 6;
console.log(sum*sum-sum_eq);

const limit = 100;
const sum = limit * (limit + 1) / 2;
const sum_eq = (2*limit + 1) * (limit + 1) * limit / 6;
console.log(sum*sum-sum_eq);

–EOF (The Ultimate Computing & Technology Blog) —