Difference of squares - Part 2

In the first part, we introduced the problem, and proposed a solution, but found it inefficient at high numbers. Now we will try for a more efficient solution.

Solution #2

After digging around online a bit, it becomes obvious pretty quick that we can reduce our solution to a simple equation.

sumOfSquares n = n * (n+1) * (2*n+1) `div` 6
squareOfSum n = (n * (n+1) `div` 2) ^ 2

This simplifies it immensely, and we run out of ways to represent n before the calculation lags now.

But, what did we do here?

Proof

So we have found the formula of (n * (n+1) * (2n+1)) / 6 is equal to our sumOfSquares formula. Our testing has worked out, but we want to be sure that they are the same. So of course, let's prove it, and how else, but by induction.

Base case:

N = 1

(N * (N+1) * (2N + 1)) / 6 ==>
(1 * (1+1) * (2*1 +1)) / 6 ==>
6 / 6 = 1

That checks out. Now on to the next step.

Let's assume that for N = K the following statement is true:

1^2 + 2^2 + 3^2 ... K^2 = (K * (K+1) * (2K+1)) / 6

If that is true, then N = K+1 becomes:

1^2 + 2^2 + 3^2 ... (K+1)^2 = ((K+1) * ((K+1)+1) * (2(K+1)+1)) / 6 = ((K+1)*(K+2)*(2K+3))/6

This can be rewritten as:

1^2 + 2^2 + 3^2 ... K^2 + (K+1)^2 = (K * (K+1) * (2K+1)) / 6 + (K+1)^2

The right-hand side reduces down to:

((K+1)(2K^2 + 7K + 6)) / 6 ==> ((K+1)(K+2)(2K+3)) / 6

Since the left-hand side is equal to the right-hand side, we are done!

Background

It turns out that the above is a specific case of the more general idea of Bernoulli's Numbers, which is used in numerous other places including Fermat's Theorem and Euler-Maclaurin summation.

Wrapping Up

This post has already gone on for far too long (like anyone got this far). The analysis of the other formula used will have to wait for a future post. As will further exploration of Bernoulli and his numbers.