running time of an algorithm

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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$