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

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)

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

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.

steps

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

and you can check your answer easily.

Return to top

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s