1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ from what I can tell, that is correct. $\endgroup$ Commented Mar 15, 2018 at 2:28
  • $\begingroup$ 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. $\endgroup$ Commented Mar 15, 2018 at 3:58

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @RossMillikan, you are right , I edited the answer. $\endgroup$
    – sirous
    Commented Mar 15, 2018 at 3:34
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .