Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \le cn^2$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Let us assume $T(n) \le cn^2$ for all $n \ge n_0$, where $c$ and $n_0$ are positive constants.

With this we cannot prove our assumption in itâ€™s exact form.

Now, let us assume $T(n) \le cn^2 - n$ for all $n \ge n_0$, where $c$ and $n_0$ are positive constants.

Uh oh! From this we cannot say the last step will be less than or equal to $cn^2 - n$ when $n$ is sufficiently large.

So, what does that mean? This means we are trying to prove a wrong assumption. And if you use Master Theorem, you will see the asymptotic bound of the given recurrence is $\Theta(n^2 \lg n)$, not $\Theta(n^2)$ as given in the problem statement.

So, let us assume $T(n) \le cn^2 \lg n - n$ for all $n \ge n_0$, where $c$ and $n_0$ are positive constants.

The last step holds as long as $c \ge 1$. Hence, our assumption is correct.

PS: As usual we have just proved $O$-bound. But to show $\Theta$-bound, we also need to show $\Omega$-bound, which can be done by adding the lower order term instead of subtracting.