# Gaussian proof for the sum of squares?

There is a famous proof of the Sum of integers, supposedly put forward by Gauss.

$$S=\sum\limits_{i=1}^{n}i=1+2+3+\cdots+(n-2)+(n-1)+n$$

$$2S=(1+n)+(2+(n-2))+\cdots+(n+1)$$

$$S=\frac{n(1+n)}{2}$$

I was looking for a similar proof for when $S=\sum\limits_{i=1}^{n}i^2$

I've tried the same approach of adding the summation to itself in reverse, and I've found this:

$$2S=(1^2+n^2)+(2^2+n^2+1^2-2n)+(3^2+n^2+2^2-4n)+\cdots+(n^2+n^2+(n-1)^2-2(n-1)n$$

From which I noted I could extract the original sum;

$$2S-S=(1^2+n^2)+(2^2+n^2-2n)+(3^2+n^2-4n)+\cdots+(n^2+n^2-2(n-1)n-n^2$$

Then if I collect all the $n$ terms;

$$2S-S=n\cdot (n-1)^2 +(1^2)+(2^2-2n)+(3^2-4n)+\cdots+(n^2-2(n-1)n$$

But then I realised I still had the original sum in there, and taking that out mean I no longer had a sum term to extract.

Have I made a mistake here? How can I arrive at the answer of $\dfrac{n (n + 1) (2 n + 1)}{6}$ using a method similar to the one I expound on above? I.e following Gauss' line of reasoning?

-
It is bad form to reuse $n$, it would be better to write $S=\sum\limits_{n=1}^{n}n$ as $S=\sum\limits_{i=1}^{n}i$ to save some possible confusion. –  Ross Millikan Mar 20 '12 at 16:12
@RossMillikan thanks very much! –  Pureferret Mar 20 '12 at 16:14
The formulas actually predate Gauss; the formulas for $1^n + 2^n + \cdots + k^n$ from $n=1$ through $n=17$ were published in 1631 by Johann Faulhaber. For some proofs, see, e.g., this paper, or this one –  Arturo Magidin Mar 20 '12 at 16:36
Mmm, probably not quite what you expect, but if you imagine that proof geometrically, it's putting together two triangles and getting an $n \times (n + 1)$ rectangle. This proof here goes along the same lines. –  aelguindy Mar 20 '12 at 17:06
The neat generalisation is the sum of numbers of the form $\frac{m(m+1) ... (m+r-1)} {r!}$ - which if you don't know it, is worth exploring on your own. –  Mark Bennet Mar 20 '12 at 20:26

You can use something similar, though it requires work at the end.

If $S_n = 1^2 +2^2 + \cdots + n^2$ then $$S_{2n}-2S_n = ((2n)^2 - 1^2) + ((2n-1)^2-2^2) +\cdots +((n+1)^2-n^2)$$

$$=(2n+1)(2n-1 + 2n-3 + \cdots +1) = (2n+1)n^2$$ using the Gaussian trick in the middle.

Similarly $$S_{2n+1}-2S_n = (2n+1)(n+1)^2$$

So for example to work out $S_9$, you start

$$S_0=0^2=0$$

$$S_1=1 + 2S_0 = 1$$

$$S_2=3+2S_1=5$$

$$S_4=25+2S_2=30$$

$$S_9 = 225+2S_4 = 285$$

but clearly there are easier ways.

-
Looking back, I still really like this. Thanks again! –  Pureferret Sep 22 '12 at 0:06

HINT: $(k + 1)^3 - k^3 = 3k^2 + 3k + 1$. Telescope the left hand side, solve for $k^2$.

If you need more of a hint I'll be glad to elaborate later. In case you'd like a reference, this is one of the first exercises in Spivak's Calculus (I don't have the latest edition, but it's in the section "Numbers of Various Sorts.")

EDIT

Since you're only interested in the "Gaussian" method of summing this series, I suggest you take a look at this Wikipedia article on Arithmetic progression. It shows how you can use this specific trick for finding the sum of arbitrary arithmetic series. Unfortunately, your sum is not of this kind, so cannot be summed by that simple method.

I have no doubt that if you fumble around with the series for long enough, you'll encounter some trick that will allow you to sum it (maybe the fact that the sum of the first $n$ odd numbers is a square?). No doubt a lot of research has been done on the so-called square pyramidal numbers (check out the list of references!) The Wikipedia entry on them has a picture of what you're actually summing (finding the number of balls in a square bottomed pyramid), so maybe you can see why they aren't as easy to sum as the triangular numbers, which can easily be arranged into squares. The MathOverflow link by aelguindy gives a "visual proof" of how the formula is derived.

Sorry I could not be of any more help.

-
Tyler, I've seen this proof before but I don't understand it. I was hoping to reduce the problem to one I'd seen before (i.e. the one by gauss). Whilst helpful in general, this is not what I'm after. –  Pureferret Mar 20 '12 at 16:31
@Pureferret: Telescopy generalizes nicely; the allegedly-Gaussian trick does not. –  Arturo Magidin Mar 20 '12 at 16:55
Telescopy may generalize well, but I'm after a specific method. If such a method does not exist, I'd rather know that, than be given alternatives which I'm not after. –  Pureferret Mar 20 '12 at 17:59

Since I think the solution Tyler proposes is very useful and accesible, I'll spell it out for you:

We know that

$$(k+1)^3-k^3=3k^2+3k+1$$

If we give the equation values from $1$ to $n$ we get the following:

$$(\color{red}{1}+1)^3-\color{red}{1}^3=3\cdot \color{red}{1}^2+3\cdot \color{red}{1}+1$$ $$(\color{red}{2}+1)^3-\color{red}{2}^3=3 \cdot \color{red}{2}^2+3 \cdot \color{red}{2}+1$$ $$(\color{red}{3}+1)^3-\color{red}{3}^3=3 \cdot \color{red}{3}^2+3 \cdot \color{red}{3}+1$$ $$\cdots=\cdots$$ $$(\color{red}{n-1}+1)^3-(\color{red}{n-1})^3=3(\color{red}{n-1})^2+3(\color{red}{n-1})+1$$ $$(\color{red}{n}+1)^3-\color{red}{n}^3=3\color{red}{n}^2+3\color{red}{n}+1$$

We sum this orderly in columns.

Note that in the LHS the numbers cancel out with each other, except for the $(n+1)^3$ and the starting $-1$ ($2^3-1^3+3^3-2^3+4^3-3^3+\cdots+n^3-(n-1)^3+(n+1)^3-n^3$). We get:

$$(n+1)^3-1 = 3(1+2^2+3^2+\cdots +(n-1)^2+n^2)+ 3(1+2+3+\cdots +(n-1)+n)+(\underbrace{1+1+\cdots+1}_{n})$$

We can write this in sigma notation as:

$$(n+1)^3-1=\sum\limits_{k=1}^n(3k^2+3k+1)$$

Naming our sum $S$ we have that:

$$(n+1)^3-1=3S+\sum\limits_{k=1}^n(3k+1)$$

We know how to compute the sum in the RHS, because

$$\sum\limits_{k=1}^n 3k =3\frac{n(n+1)}{2}$$

$$\sum\limits_{k=1}^n 1 =n$$

(We're summing $n$ ones in the last sum.)

$$(n+1)^3-1=3S+3 \frac{n(n+1)}{2}+n$$

$$n^3+3n^2+3n=3S+\frac{3}{2}n^2+\frac{3}{2}n+n$$

$$n^3+\frac{3n^2}{2}+\frac{n}{2}=3S$$

$$\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=S$$

This factors to

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

which is what you wanted.

-
I have two main issues with this, neither os which is your fault. Firslty I'm lost after the second line of algebra. I have figuratively no idea what telescoping is, or how we get to $(n+1)^3-1$ from the expression above. My motivation for learning this via Gauss' method (I know it's not 'his' but it's the best way I can describe it) is so I can start at my sum over $n^2$ and more forwards from their, in say and exam. This exam is nothing to do with series or sums but a quick simple method would be handy to know. If I have to start with the top expression I may as well memorise the bottom one. –  Pureferret Mar 21 '12 at 8:10
Largely because this would be a Physics exam, with no marks for memorising a 'complicated' method involving telescoping. Also because I suspect if the lecturer (a physicist) marking it doesn't follow the method (likely) I will be downgraded. In a similar question to this the lecturer solved it by trial and error, which wasn't rigorous enough for me to be satisfied which is why I'm exploring this route. –  Pureferret Mar 21 '12 at 8:13
@Pureferret The method is very elemental. I think you could try and find some values of the RHS for some $n$ to see why the result is such. Nevertheless, I'll add more to the answer. –  Pedro Tamaroff Mar 21 '12 at 23:37

There is a more beautiful Gauss-style proof that involves writing the numbers in triangles instead of in a line.

I leave the details to you.

-
You might want to explain this a bit more. The sum of the numbers in the left triangle is $\sum\limits_{k=1}^nk^2$. Furthermore, the other triangles are simply rotations of the first. Nice proof, and definitely in the spirit of the Gaussian approach. (+1) –  robjohn Feb 5 '14 at 4:03
And the number of 2n+1's in the right is exactly 1 + 2 + ... + n, which we know in closed form. –  JeremyKun Feb 5 '14 at 14:18
Spectacular! Thanks for posting it. –  kjo Sep 12 '14 at 11:57