# How does sum of first $k$ integers equal $k(k+1)/2$ [closed]

According to this video, he explains $$p = k(k+1) / 2$$ Where $$p$$ is the sum of the first $$k$$ natural numbers. I understand $$k$$ means times of repetition and $$k+1$$ is how it increments, but why does he divide by $$2$$? I can't justify it.

Here is what the video describes:

for (i = 1; i <= n; i++)
p += i

$$\begin{array}{|c|c|} \hline i & p \\ \hline 1 & 1 \\ \hline 2 & 3 \\ \hline 3 & 6 \\ \hline 4 & 10 \\ \hline \vdots & \vdots \\ \hline i & i(i+1)/2 \\ \hline \end{array}$$

• Add the numbers 1 to 5. Compare with 5*6 and with 5*6/2. Commented Apr 25, 2019 at 14:14
• ok... but still, I know it get the right number, but how, did the person just know, to divide by two? I just feel there is some concept I missed .... @ghasher729 Commented Apr 25, 2019 at 14:38
• I'm closing this question, because 1: it is not clear what your question is without watching the video, please include all relevant information inside the question body. (I suppose you could partially deduce it from the figure, but please transcribe it, as it is still too ambiguous to me) 2, it seems your question is only about an elementary mathematical identity, which is off-topic here. Commented Apr 25, 2019 at 16:05
• @Discrete lizard uhm.... If the whole screenshot involved the whole formula you can't understand I don't know what to say... Clearly somehow many people do understand this question Commented Apr 25, 2019 at 16:24
• Yeah seems pretty off-topic, probably a better fit on math.stackexchange.com, but it's already been answered there. This is not about algorithm analysis or time complexity at all. This is just evaluating a sum. Also just a simple google search would answer this for you.
– ryan
Commented Apr 25, 2019 at 18:08

Let me tell you the story of young Carl Friedrich Gauss.

He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he asked the kids to add up the numbers 1 to 1000.

How did he do it?

He changed the order and added 1+1000, 2+999, 3+998 up to 500+501. Each sum is 1001, and there are 500 sums, so the result is 1001 * 500. Obviously k=1000, so this is (k+1) * k / 2.

You can use this for adding numbers in any arithmetic progression: sum = (first + last) * count / 2.

• silly me, totally forgot this story lol heard it like couple times in my life time.... Commented Apr 25, 2019 at 15:57
• While it is a nice story, it is currently generally believed to be entirely apocryphal. Commented Apr 25, 2019 at 16:01
• I personally like pairing up 1+999, 2+998, ..., 499+501, 500+500 (this covers the fact we didn't include 1000) as the example. Then you just add 500 to get (1000*1000 / 2) + (1000/2). Although this is just a matter of preference I gauss.
– ryan
Commented Apr 25, 2019 at 16:34
• @ryan. Your last sentence: groan. Commented Apr 26, 2019 at 12:49

It is not an algorithm time complexity. The time complexity of the specified loop in the picture is $$\Theta(n)$$ (as it does $$n$$ add operation).

What you can see in the sum of $$1 + 2 + ... + k$$ can be proved easily by mathematical induction. You can verify that for $$n = 1$$ obviously. Now suppose it is true for $$n$$ $$f(n) = 1 + 2 + ... + n = \frac{n(n+1)}{2}$$. And try to prove for $$n+1$$. By the definition we know that $$f(n+1) = 1 + 2 + 3 + ... + n + (n+1) = f(n) + n + 1$$. From the induction assumption we will have $$f(n+1) = \frac{n(n+1)}{2} + n+1 = (n+1)(\frac{n}{2} + 1) = \frac{(n+1)(n+2)}{2}$$. The proof is completed.

And a completely different answer that can handle more cases:

Let’s say you are summing $$3x^2 + 7x - 4$$. You guess that the solution is something like $$ax^3$$. When you go from k-1 to k, the sum increases by $$3k^2 + 7k - 4$$. The formula increases by $$a(k^3 - (k-1)^3)$$ = $$a(3k^2-3k+1)$$. So you guess a=1.

So your formula starts with $$k^3$$. You subtract $$a(3k^2-3k+1)$$ from $$3k^2 + 7k - 4$$, leaving 10k - 5, and calculate the sum for this. Works for any polynomial.

Now all this was guessing, so you use complete induction to prove it.

• is this... the answer for this question? lol feel like its meant for another totally different question lol Commented Apr 25, 2019 at 15:54
• It's it maybe just I am a bit silly in understanding the concept here Commented Apr 25, 2019 at 18:15