Step in proof of derivation of $1+2+\cdots+n=\tfrac{n(n+1)}{2}$.

Question

I have been solving a few computer science problems lately and it is important for me to understand how the time complexity of an algorithm is calculated by coming up with the derivation and arriving at the result. One problem is frustrating me a lot.

In order to find the sum of the first $n$ natural numbers I can use the equation $\tfrac{n(n+1)}{2}$. I looked into this article and understand how this equation makes sense.

And then I looked into this article to understand how to arrive at this equation via algebraic method.

I feel like there is a giant leap between the third and second lines from the last in the above image. This is the same derivation I could find in all the articles i have visited. I don't understand how the equation suddenly got multiplied with $n$ on the right hind side, where $2T(n)= n(n+1)$.

Kindly let me know what I'm missing here.

Answer 1

Alternative. $\color{white}{You shall never see me.}$

See this sum?

$S=1+\color{red}{2}+\color{blue}{3}+\color{green}{4} \ldots \color{orange}{n}$

Write it backwards.

$S=n+\color{red}{(n-1)}+\color{blue}{(n-2)}+\color{green}{(n-3)} \ldots \color{orange}{1}$

Add up corresponding terms:

$2S=(n+1)+(n-1+2)+(n-2+3) \ldots (1+n)$

$=n(n+1)$

That's what the article is saying.

Answer 2

On the right hand side you have a sum of $n$ terms, and each terms equals $n+1$, so this sum equals $n(n+1)$.

Answer 3

Does this layout help?:

$T(n) + T(n) = \underbrace{1 + 2 + 3 + ...... + n}_{\text{There are }n\text{ of these terms}} + $

$\underbrace{n + (n-1)+ (n-2) + ...... + 1}_{\text{These are }n\text{ of these terms}}=$

$\underbrace{(1+n) + (2+n-1)+ (3+ n-2) + ...... + (n+1)}_{\text{These are }n\text{ of these terms}}=$

$\underbrace{(n+1) + (n+1)+ (n+1) + ...... + (n+1)}_{n\text{ times}}=$

$n\times (n+1)$

.....

Remember $m \times k= \underbrace{k + k + k + ..... + k}_{m \text{ times}}$.

That's why we call it "times". Because $m$ "times" $k$ means we add $k$ to itself $m$ times.