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 nth term in the sum be called u_n:

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


Suppose u_n can be written in the form


where f is some function. Then



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


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








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




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


\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:


\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)

So there’s our answer:

\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


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


and you can check your answer easily.

Return to top


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s