running time of an algorithm I am trying to prove an algorithm with input size $n$ satisties the recurence relation (for $n>=1$) 
$T(n) = T(n-1)+n$ and an initial condition of $T(1)=1$ has running time in  $Θ(n^2$).
By using telescope, I've got up to the point where I got 
$T(n) = n+(n-1)+(n-2)+......+ 1$
But I can not go any further from this point.
I've been googling and searching for a while and I saw that
$n+(n-1)+(n-2)+......+ 1$ can be written as $\frac{n(n+1)}{2}$ 
Can someone explain how would I get $\frac{n(n+1)}{2}$  from $n+(n-1)+(n-2)+......+ 1$?
 A: This is a well-known identity. It can be proved by induction as follows.
Notice that $1=\frac{1(1+1)}{2}$. Suppose then that we have proven that
$$1+2+\cdots +(n-2)+(n-1)=\frac{n(n-1)}{2}$$
Then
$$1+2+\cdots+(n-1)+n=\frac{n(n-1)}{2}+n=\frac{n^2-n+2n}{2}=\frac{n(n+1)}{2}$$
so the result follows by induction.
A: Let $S = 1 + 2 + 3 + 4 + ... + n$
$S = 1 + 2 + 3 + 4 + .... + n$
$S = (n) + (n-1) + (n-2) + (n-3) + .... + 1)$
If you add them together you'll notice a they all simplify to a series like this:
$2S = (n+1) + (n+1) + ..... + (n+1)$
$2S = n(n+1)$ (because we add $(n+1)$ $n$ times)
So,
$S = n(n+1)/2$
A: First note that
$$ n+(n-1)+(n-2)+\cdots +1$$ 
Can be rewritten as
$$ 1+2+\dots +n$$
Now let's use mathematical induction 
Hypothesis
$$ \forall n\in\mathbb{N}:n\ge 1$$
$$ 1+2+\dots +n=\frac{n(n+1)}{2} $$
Basis Step
Let $n=1$,
$$ 1=\frac{1\cdot (1+1)}{2} $$
$$ 1=\frac{1\cdot 2}{2} $$
$$ 1=1 $$
Inductive Step
Let $n=k+1$,
$$ 1+2+\dots +k+(k+1)=\frac{(k+1)(k+1+1)}{2} $$
$$ 1+2+\dots +k+(k+1)=\frac{(k+1)(k+2)}{2} $$
$$ 1+2+\dots +k+(k+1)=\frac{k^2+2k+k+2}{2} $$
$$ 1+2+\dots +k+(k+1)=\frac{k^2+k}{2}+\frac{2k+2}{2} $$
$$ 1+2+\dots +k+(k+1)=\frac{k^2+k}{2}+(k+1)$$
$$ 1+2+\dots +k=\frac{k^2+k}{2} $$
$$ 1+2+\dots +k=\frac{k(k+1)}{2} $$
Therefore 
$$ 1+2+\dots +n=\frac{n(n+1)}{2} $$
