19
$\begingroup$

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$
6
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 20, 2012 at 16:12
  • $\begingroup$ @RossMillikan thanks very much! $\endgroup$ Mar 20, 2012 at 16:14
  • 3
    $\begingroup$ 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 $\endgroup$ Mar 20, 2012 at 16:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – aelguindy
    Mar 20, 2012 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 20, 2012 at 20:26

7 Answers 7

41
$\begingroup$

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

Gauss style proof

I leave the details to you.

$\endgroup$
5
  • 8
    $\begingroup$ 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) $\endgroup$
    – robjohn
    Feb 5, 2014 at 4:03
  • $\begingroup$ And the number of 2n+1's in the right is exactly 1 + 2 + ... + n, which we know in closed form. $\endgroup$
    – JeremyKun
    Feb 5, 2014 at 14:18
  • 1
    $\begingroup$ Spectacular! Thanks for posting it. $\endgroup$
    – kjo
    Sep 12, 2014 at 11:57
  • $\begingroup$ What source was this from? $\endgroup$
    – user17753
    Jan 29, 2016 at 12:36
  • 1
    $\begingroup$ This was told to me by a professor in the Budapest Semesters program. I do not know if it appears in any book. $\endgroup$
    – JeremyKun
    Jan 29, 2016 at 16:13
10
$\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$ 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. $\endgroup$ Mar 20, 2012 at 16:31
  • 6
    $\begingroup$ @Pureferret: Telescopy generalizes nicely; the allegedly-Gaussian trick does not. $\endgroup$ Mar 20, 2012 at 16:55
  • $\begingroup$ 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. $\endgroup$ Mar 20, 2012 at 17:59
8
$\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$ 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. $\endgroup$ Mar 21, 2012 at 8:10
  • $\begingroup$ 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. $\endgroup$ Mar 21, 2012 at 8:13
  • $\begingroup$ @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. $\endgroup$
    – Pedro
    Mar 21, 2012 at 23:37
7
$\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
  • 1
    $\begingroup$ Looking back, I still really like this. Thanks again! $\endgroup$ Sep 22, 2012 at 0:06
3
$\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$
1
$\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
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.