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?
$\endgroup$ 67 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ 1 $\begingroup$This answer uses the formula for the sum of odd numbers, which is$$i^2=\sum_{k=1}^i 2k-1$$First insert this into the considered formula$$s_n\overset{\mathrm{def}}{=}\sum_{i=1}^ni^2=\sum_{i=1}^{n}\sum_{k=1}^i (2k-1)$$
Definitely in the style of Gauss is writing out the sum for each $i$ and using one row for each $i$: \begin{align} s_n&=\color{red}{1}\\ &+\,\color{red}{1}+\color{blue}{3}\\ &+\,\color{red}{1}+\color{blue}{3}+\color{green}{5}\\ &+\,\color{red}{1}+\color{blue}{3}+\color{green}{5}+7\\ &\;\vdots\\ &+\,\color{red}{1}+\color{blue}{3}+\color{green}{5}+7+\ldots+2n-1 \end{align}Now take the sum column by column beginning with the last to obtain$$s_n=1\cdot (2n-1)+2\cdot (2n-3)+3\cdot (2n-5)+\ldots+\cdot \color{green}{(n-2)\cdot 5}+\color{blue}{(n-1)\cdot 3}+\color{red}{n\cdot 1}$$which is exactly the sum$$s_n=\sum_{i=1}^n i\cdot(2n-(2i-1))=\sum_{i=1}^n i((2n+1)-2i)$$To get the final result, you only have to do simple calculations, you see here:$$s_n=(2n+1)\sum_{i=1}^n i-2\sum_{i=1}^n i^2=(2n+1)\frac{n(n+1)}{2}-2s_n$$Thus$$3s_n=\frac{n(n+1)(2n+1)}{2}\qquad \Rightarrow\qquad s_n=\frac{n(n+1)(2n+1)}{6}$$
$\endgroup$ $\begingroup$We use that $n^2=\sum_{k=1}^{n} (2k-1).$ Then:
Not quite Gaussian, but similar:
$$\begin{align}S&=\sum_{n=1}^{m} n^2 \\&= \sum_{n=1}\sum_{k=1}^n (2k-1)\\ &=\sum_{k=1}^{m}\sum_{n=k}^{m}(2k-1)\\ &=\sum_{k=1}^m(2k-1)\sum_{n=k}^{m}1\\ &=\sum_{k=1}^m(2k-1)(m+1-k)\\ &=-2S -m(m+1)+ (2m+3)\sum_{k=1}^m k \end{align}$$
So we get;
$$3S = m(m+1)\left(\frac{2m+3}{2}-1\right)=\frac{m(m+1)(2m+1)}{2}$$
$\endgroup$ 0 $\begingroup$This has a few parts, but should bridge the gap between what you were looking for (hopefully?) and the answers from Tyler and Pedro.
If I remember right, that method of Gauss' has a geometric interpretation that Gauss provided along with it. Namely that the sum 1+2+...+n can be visualized as a "staircase" of rectangles. Flipping the sum and adding it to the first one is putting a new rectangle on each of the original ones, but this time in descending order, so 1 will have n above it, 2 will have n-1, etc. Since the bottom portion of increasing by 1 each time the top part decreases by 1, every rectangle now has height n+1. There are n of them, so together they cover an area equal to n*(n+1). That uses two "staircases" though, so one "staircase" amounts to n*(n+1)/2, which is also (n^2+n)/2. (Note that in this last form the rectangle is a square with a single extra row of units at the top.)
So Gauss' method was to realize that you could put two staircases together to make a rectangle with an easy to calculate area and then divide by 2 to get back what you really wanted. Taking that thinking up to the sum of squares question then would potentially involve some 3D versions of staircases. You definitely can make some 3D staircase analogues. Put a 4x4x1 slab under a 3x3x1 slab under a 2x2x1 slab under a 1x1x1 cube and align them so they all would fit neatly in the corner of a box. There's your 3D version of a staircase made of sums of squares.
Now that we're up a dimension though, 2 sets of these stairs aren't going to fit together the way we want to make a nice convenient rectangular prism for us to easily find the volume of and then divide to get what we want. Turns out we need 3 of them.
That's where Tyler and Pedro's answers come in. They show how you can build a cube using 3 "3D-staircases", 3 "2D-staircases", n singles and an extra single. Their formula shows that in going from a cube of size n^3 to a cube of size (n+1)^3, the larger cube is made by adding 3 face-extensions of size nxnx1, 3 new outside edges of size 1x1xn, and a new corner of size 1x1x1. This means you can "peel" any cube down into a sum of these added layers. The three sets of faces make three 3D staircases, the three sets of edges make three 2D staircases, the new corners sum to n, and the last 1x1x1 cube is the "seed" all the layers were wrapped around.
So, that's how Gauss' method connects to this problem and also how Tyler and Pedro's answers are relevant to that discussion. In terms of why the algebra isn't working out, I think this breakdown should provide some ideas, first and foremost that you'll need 3 sums rather than 2 and that you'll probably need the 2D staircases as well.
I hope it goes well (or went well, if you resolved this long ago). Your question generated a lot of cool responses! Thanks!
$\endgroup$
