Problem 6: Sum square difference

Problem:

Please find the problem here.

Solution:

Again, notice the size of the problem - it is just 100 numbers, brute force will work great. But let's be slightly advanced with computing sums. Here I introduce a method that we can compute sum of squares (in general, the method can go to sum of any powers) as follow:

When we want to compute sum of squares, let consider difference of cubes.

$
\begin{eqnarray*} (n+1)^3 - n^3 &=& n^3 + 3n^2 + 3n + 1 - n^3 \\ &=& 3n^2 + 3n + 1 \\ \sum\limits_{j=1}^{n} ((j+1)^3 - j^3) &=& \sum\limits_{j=1}^{n} (3j^2 + 3j + 1) \\ (n+1)^3 - 1 &=& 3\sum\limits_{j=1}^{n} j^2 + 3\sum\limits_{j=1}^{n} j + \sum\limits_{j=1}^{n} 1 \\ &=& 3\sum\limits_{j=1}^{n} j^2 + 3\frac{n(n+1)}{2} + n \\ 3\sum\limits_{j=1}^{n} j^2 &=& (n+1)^3 - 1 - 3\frac{n(n+1)}{2} - n \\ \sum\limits_{j=1}^{n} j^2 &=& \frac{(n+1)^3 - 1 - 3\frac{n(n+1)}{2} - n}{3} \\ &=& \frac{n(n+1)(2n+1)}{6} \end{eqnarray*}$

There are two things you should wonder in the proof. First - how on hell I know to consider the difference of cube. The truth is - I don't know - I learn it somewhere in my algebra textbook. But that useful technique can cover sum of any power by considering difference of a higher power, as you can imagine the first line will cancel out the higher power, and the fourth line will the higher power difference sum will telescope away.

The second thing is why we have the equality on the last line - that must have involve some serious expansion and factorization, which is tedious. Fortunately, we don't have to do that manually. The following Matlab command will do that for us instantly.

syms x
factor(((x+1)^3 - 1 - 3 *x*(x+1)/2 - x)/3)

It will yield 1/6*x*(x+1)*(2*x+1) right away. It is awesome to have Matlab.

With that, the code to compute is trivial, here it is:

namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem006()
        {
            int n = 100;
            int sumOfSquares = n * (n + 1) * (2 * n + 1) / 6;
            int squareOfSum = n * n * (n + 1) * (n + 1) / 4;
            Console.WriteLine(squareOfSum - sumOfSquares);
        }
    }
}

Answer: 25164150