How I can solve $s(n)=n+s(n-1)$ by iteration method?

Question

$$ s(n)= \begin{cases} 0, \text{if $n=0$}\\ n+s(n-1), \text{if $n>0$}\\ \end{cases} $$

Using the relation \begin{align} s(n) &= n+s(n-1) \\ &= n+n-1+s(n-2) \\ &= n+n-1+n-2+s(n-3) \\ &= \dots \\ &= n+n-1+n-2+\dots+1 \\ &= \dfrac{n^2+n}2 \\ &= \theta(n^2) \end{align}

Is it right?

Answer 1

$s(n)=n+s(n-1)$

$s(n-1)=n-1 + s(n-2)$

$s(n-2)=n-2 + s(n-3)$

$s(n-3)=n-3 + s(n-4)$

.

.

.

$s[n-(n-1)]=n-(n-1) + s(0)$

⇒ $s(n)=n\times n -\frac{(n-1)(n-1+1)}{2}=n^2-\frac{(n)(n-1)}{2}=\frac{n^2+n}{2}$

Answer 2

I like to turn recurrences to telescoping sums whenever possible.

From $s(n) = n+s(n-1) $ I get $s(n)-s(n-1) = n$.

Summing both sides from $1$ to $m$, $\sum_{n=1}^m s(n)-s(n-1) = \sum_{n=1}^m n $.

The left side telescopes into $s(m)-s(0)$ and the right side is just $\dfrac{m(m+1)}{2} $.

Note that if the first value is $s(1)$, just make the sum from $2$ instead of $1$.