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?

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