Solving Recurrence Relation T(n) = T(n-1) + n + 2

Question

I am getting stuck solving this recurrence relation.

T(1) = 1

T(n) = T(n-1) + n + 2

I continued to expand it:

$T(n) = T(n-1) + n + 2 = [T(n-2) + (n-1) + n + 2] + 2$

$= T(n-2) + (n-1) + n +4 = [T(n-3) + (n-2) + (n-1) + n + 2] + 4$

$= T(n-3) + (n-2) + (n-1) + n + 6$

$= T(n-(n-1)) + (\sum_{i=0}^{n-2} n-i) + 2(n-1)$

$= 1 + (\sum_{i=0}^{n-2} n-i) + 2n-2$

This is where I get stuck. Did I do a step wrong?

Answer 1

That's a rough way to solve it. You could arrange it: $$T(n) - T(n - 1) = n + 2$$ Which is the definition of the summation: $$T(n) = \sum (n + 2)$$ $$T(n) = \frac{n(n + 1)}2 + 2n + C$$ $$T(n) = \frac12n^2 + \frac52n + C$$ Noting that $T(1) = 1$: $$C = -2$$ So: $$T(n) = \frac12n^2 + \frac52n - 2$$

Answer 2

HINT:

$$T(n) - T(n-1) = n +2 = T(n-1) - T(n-2) + 1 \implies T(n) - 2T(n-1) + T(n-2) = 1$$

Now in the same manner:

$$T(n) - 2T(n-1) + T(n-2) = 1 = T(n-1) - 2T(n-2) + T(n-3) \implies $$ $$T(n) - 3T(n-2) + 3T(n-2) - T(n-3) = 0$$

Now this is a homogenous recursive relation, which can be easily solved.