0
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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) $$

$\endgroup$
  • $\begingroup$ Why did you put one of the K's to the power of two? $\endgroup$ – Rafa_Asp1 Apr 16 '16 at 22:22
  • $\begingroup$ @Rafa_Asp1 I'm computing $S_2(n+1)=\sum_{k=0}^{n+1}k^2$. $\endgroup$ – egreg Apr 16 '16 at 22:24
  • $\begingroup$ It's not clear to me why you changed the exponent. $\endgroup$ – Rafa_Asp1 Apr 16 '16 at 22:31
  • $\begingroup$ @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. $\endgroup$ – egreg Apr 16 '16 at 22:33
  • $\begingroup$ 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²? $\endgroup$ – Rafa_Asp1 Apr 17 '16 at 12:37

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.