<s>[INST] Mathematical Induction for Recurrence Relation 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?
 [/INST] 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$$
</s>