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

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

• from what I can tell, that is correct. Commented Mar 15, 2018 at 2:28
• When you do it just using ... instead of a summation it is easy to have one term too few or one term too many. You have it right here. Commented Mar 15, 2018 at 3:58

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

• @RossMillikan, you are right , I edited the answer. Commented Mar 15, 2018 at 3:34

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