# Sum of Squares

Consider the sum

$\displaystyle S(N)=\sum_{n=1}^N n^2=1^2+2^2+...+(N-1)^2+N^2$

This is the sum of the natural numbers’ sterner sibling. Here’s a simple way of evaluating $S$ using a trick called the method of differences.

Let the $n$th term in the sum be called $u_n$:

$\displaystyle S(N)=\sum_{n=1}^N u_n$

$S(N)=u_1+u_2+...+u_{N+1}+u_N$

Suppose $u_n$ can be written in the form

$u_n=f(n)-f(n-1)$

where $f$ is some function. Then

$S(N)=[f(1)-f(0)]+[f(2)-f(1)]+...+[f(N)-f(N-1)]$

$S(N)=f(N)-f(0)$

The positive part of $u_n$ cancels with the negative part of $u_{n+1}$. This kills nearly everything in the sum except the positive part of $u_N$ and the negative part of $u_1$, since they have nothing with which to cancel.

So to evaluate $S$, we just need to find a function $f$ that satisfies

$n^2=f(n)-f(n-1)$

It’s reasonable to expect that $f$ will be a polynomial, and we’ll guess it’s of third order:

$f(n)=an^3+bn^2+cn+d$

so

$f(n-1)=a(n-1)^3+b(n-1)^2+c(n-1)+d$

$f(n-1)=a(n^3-3n^2+3n-1)+b(n^2-2n+1)+c(n-1)+d$

hence

$f(n)-f(n-1)=[a-a]n^3+[b+3a-b]n^2+[c-3a+2b-c]n^1+[d+a-b+c-d]n^0$

$f(n)-f(n-1)=3an^2+[-3a+2b]n^1+[a-b+c]n^0$

If this entire expression is to be equal to $n$ squared, we must demand that

$3a=1$

$-3a+2b=0$

$a-b+c=0$

Pleasingly, these simultaneous equations come out such that they are naturally solved in order. The first equation gives

$\displaystyle a=\frac{1}{3}$

The second equation gives

$\displaystyle b=\frac{3}{2}a$

$\displaystyle b=\frac{3}{2}\cdot\frac{1}{3}$

$\displaystyle b=\frac{1}{2}$

The third equation gives

$c=b-a$

$\displaystyle c=\frac{1}{2}-\frac{1}{3}$

$\displaystyle c=\frac{1}{6}$

Hence our required function $f$ is

$\displaystyle f(n)=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n+d$

The constant $d$ was never determined, but we’ll see in a second that it won’t matter.

We can now use the expression we derived earlier:

$S(N)=f(N)-f(0)$

$\displaystyle S(N)=\frac{1}{3}N^3+\frac{1}{2}N^2+\frac{1}{6}N+d-d$

$\displaystyle S(N)=\frac{1}{3}N^3+\frac{1}{2}N^2+\frac{1}{6}N$

Let’s tidy this up and put it in its traditional form:

$\displaystyle S(N)=\frac{1}{6}N(2N^2+3N+1)$

$\displaystyle S(N)=\frac{1}{6}N(N+1)(2N+1)$

$\displaystyle \sum_{n=1}^N n^2=\frac{1}{6}N(N+1)(2N+1)$

One point you may be unhappy with: how did I know $f$ would be of third order? Why didn’t I instead guess

$f(n)=an^4+bn^3+cn^2+dn+e$

or an even higher power? The honest answer is that I knew the value of the sum already. But that’s not to say you can’t guess what the order of the leading term will be. Here’s a dodgy bit of reasoning: the most significant terms in the sum are the biggest, those on the order of $N^2$, since they contribute the most. So we expect the sum to be proportional to $N^2$ as it becomes very large. But the sum also increases with the number of terms in the sum, which goes like $N$. The conclusion is that the sum increases with $N^2\times N=N^3$.

If you don’t like that (and I wouldn’t blame you), you are welcome to try a trial function $f$ on an order greater than three, and you will get exactly the same answer in the end; you’ll just have to do more work to get there.

It’s fun trying to think of applications for this sum. The one that sprung to my mind was working out how many blocks you would need to build a step pyramid with $N$ layers, something like El Castillo at Chichen Itza. Say no to Minecraft, kids, it will consume your life.

You might like to try finding the value of the sum

$\displaystyle S(N)=\sum_{i=1}^N n^3$

using the difference method; a sensible guess for $f$ would be one of the form

$f(n)=an^4+bn^3+cn^2+dn+e$