Substitution Method to Prove Inequalities for Recurrence

Question

Use the substitution method to show that recurrence

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

implies that

T(n) ≤ C * n^2

as long as

C ≥ 1 and C ≥ T(1)

I am trying to figure out what C represents in this question. My professor left it ambiguous. I believe that C is the number of expansions made on the recurrence.

Also, assuming that C is the number of expansions, I am not sure how to solve for it without a provided base case.

The farthest I got was partially guessing the generalized equation. I have:

T(n) = T(n-C) + (C*n) + [SOME SUMMATION INVOLVING C]

I have not figured out what the summation should be- or even if one is required.

Any direction on what C might be and how to solve for it would be greatly appreciated. Thanks!

Answer 1

Let us prove it by induction on $n$. Clearly, $T(1) \leq C$ (it is one of the given assumptions).

Let us suppose that $T(n) \leq Cn^{2}$. Then we have to prove that $T(n+1)\leq C(n+1)^{2}$.

Indeed, one has that \begin{align*} T(n+1) = T(n) + n + 1 & \leq Cn^{2} + n + 1\\\\ & \leq Cn^{2} + 2n + 1\\\\ & \leq C(n^{2}+2n+1) = C(n+1)^{2} \end{align*} because $C\geq 1$ by assumption. Therefore we are done.