-1
$\begingroup$

Okay so I am supposed to find the recurrence equation of $T(n) = T(n-1)+n+2$, where $T(1) = 1$. I know the answer should come out to be $\dfrac12(n(n+5)-4)$ but I don't understand how to get that answer.

$\endgroup$
4
$\begingroup$

You have $$T(k)-T(k-1)=k+2$$ Summation of both sides from $2$ to $n$ gives you $$T(n)-T(1)=\sum_{k=2}^n(k+2)=\sum_{k=4}^{n+2}k=\frac{(n+6)(n-1)}{2}$$ $$T(n)=1+\frac{n^2+5n-6}{2}$$ $$=\frac{n^2+5n-4}{2}$$ $$=\frac{n(n+5)-4}{2}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What is k? why is it equal to 2? I am having real trouble understanding it, but that's mainly because I suck at math, thanks for the quick response though! $\endgroup$ – Adam Angel Nov 2 '16 at 4:53
0
$\begingroup$

Hint: Consider $a_n=T(n)-T(n-1)$ for $n\geqslant 2$. How can you express $T(n)$ in terms of $a_n$, $a_{n-1}$, $\dots$, $a_2$?

An alternative, since you know the solution, is to prove the formula by mathematical induction. That's less satisfying since you may not know the solution next time you'll face a similar problem.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.