1
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by Discrete lizard Apr 25 at 16:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Add the numbers 1 to 5. Compare with 5*6 and with 5*6/2. $\endgroup$ – gnasher729 Apr 25 at 14:14
  • $\begingroup$ 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 $\endgroup$ – Ezeewei Apr 25 at 14:38
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 25 at 16:05
  • $\begingroup$ @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 $\endgroup$ – Ezeewei Apr 25 at 16:24
  • $\begingroup$ 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. $\endgroup$ – ryan Apr 25 at 18:08
6
$\begingroup$

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.

30 seconds later young Carl Friedrich had the answer: 500,500.

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.

$\endgroup$
  • $\begingroup$ silly me, totally forgot this story lol heard it like couple times in my life time.... $\endgroup$ – Ezeewei Apr 25 at 15:57
  • $\begingroup$ While it is a nice story, it is currently generally believed to be entirely apocryphal. $\endgroup$ – Discrete lizard Apr 25 at 16:01
  • $\begingroup$ 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. $\endgroup$ – ryan Apr 25 at 16:34
  • 1
    $\begingroup$ @ryan. Your last sentence: groan. $\endgroup$ – Rick Decker Apr 26 at 12:49
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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