Use the substitution method to prove that the recurrence \(T(n) = T(n-1) + \Theta(n)\) has the solution \(T(n) = \Theta(n^2)\), as claimed at the beginning of Section 7.2.

We guess \(T(n) \leq cn^2\) for some constant \(c > 0\). Furthermore, we will represent \(\Theta(n)\) as \(dn\). Substituting these into the recurrence yields

\[\begin{split} T(n) &\leq T(n-1) + dn \\ &= c(n-1)^2 + dn \\ &= cn^2 -2cn + c + dn \\ &\leq cn^2 \\ \end{split}\]

where the last step holds for when \(2c > d\) and \(c \geq \frac{dn}{2n-1}\).