# How to come up with Gauss arithmetic progression solution in this sum

I need to solve this: $\sum\limits_{k=0}^n k\\$

Using this specific method: $n + \sum\limits_{k=0}^{n-1} k\ = 0 + \sum\limits_{k=1}^n k\\$

Now this has to evaluate to: $\ n+\frac{n(n-1)}{2} = \frac{n(n+1)}{2} \\$

I don't know how to reach that result using that method, my results don't look like this.

• Are you saying you do not understand proof by induction? – almagest Apr 16 '16 at 20:59
• No, I saying I don't know how to evaluate this sum starting with that "method". – Rafa_Asp1 Apr 16 '16 at 22:23

## 2 Answers

You say:

Now this has to evaluate to: $\ n+\frac{n(n-1)}{2} = \frac{n(n+1)}{2} \\$

I don't know how to reach that result using that method, my results don't look like this.

Well, if you expand the left hand side you get:

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

Which is equal to the right hand side above.

References: Young Gauss and the sum of the first n positive integers further details some history about how to perform the sum.

Writing $n + \sum\limits_{k=0}^{n-1} k = 0 + \sum\limits_{k=1}^n k$ does not take you much far, but the method is good if you consider the sums of squares instead. Set $$S_1(n)=\sum_{k=0}^n k, \quad S_2(n)=\sum_{k=0}^n k^2,$$ and write \begin{align} S_2(n)+(n+1)^2 &=S_2(n+1)\\ &=0+\sum_{k=1}^{n+1}k^2\\ &=\sum_{k=0}^{n}(k+1)^2\\ &=\sum_{k=0}^{n}(k^2+2k+1)\\ &=\sum_{k=0}^{n}k^2+2\sum_{k=0}^{n}k+\sum_{k=0}^{n}1\\ &=S_2(n)+2S_1(n)+(n+1) \end{align} Comparing the starting point to the final one, we get $$2S_1(n)=(n+1)^2-(n+1)=n(n+1)$$

• Why did you put one of the K's to the power of two? – Rafa_Asp1 Apr 16 '16 at 22:22
• @Rafa_Asp1 I'm computing $S_2(n+1)=\sum_{k=0}^{n+1}k^2$. – egreg Apr 16 '16 at 22:24
• It's not clear to me why you changed the exponent. – Rafa_Asp1 Apr 16 '16 at 22:31
• @Rafa_Asp1 I added a step, perhaps it's clearer. It's a nice trick I learnt from “Discrete Mathematics” by Graham, Knuth and Patashnik. – egreg Apr 16 '16 at 22:33
• Using K² I will ended up with the closed form for K, and using K³ I will ended up with the closed form for K²? – Rafa_Asp1 Apr 17 '16 at 12:37