Mathematical Induction for Recurrence Relation

Question

I have solved the following recurrence relationship:

$T(1) = 1$

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

so

$T(n) = \frac{1}{2}n^2+\frac{5}{2}n -2$

I am now trying to perform mathematical induction to prove this.

$Basis:$

$T(1)=1=3-2=\frac{1}{2} + \frac{5}{2} - 2 $

$Induction:$

$T(k+1) = T(k) + k+1 + 2$

$= \frac{1}{2}k^2 + \frac{5}{2}k -2 + k+1 +2$

$= \frac{1}{2}k^2 + \frac{7}{2}k +1$

What can I do next?

Answer 1

What can I do next?

Hint. Prove that, for $k=1,2,\cdots,$ $$ \frac{1}{2}k^2 + \frac{7}{2}k +1=\frac{1}{2}(k+1)^2+\frac{5}{2}(k+1)-2. $$

Answer 2

HINT: Try to express the last formula in terms of $(k+1) $, rather than a function of $k $.

Answer 3

If induction is not a prerequisite, the following is an alternative that simply telescopes the sequence.

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

$$\sum_{k=2}^{n} \big(T(k) - T(k-1)\big) = \sum_{k=2}^{n}(k + 2)$$

$$T(n) - T(1) = \frac{(n-1)(n+6)}{2}$$

$$T(n) \;=\; 1 + \frac{n^2 + 5 n - 6}{2} \;=\; \frac{1}{2}n^2 + \frac{5}{2}n - 2$$