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

We start by substituting our doomed guess of \(T(n) \leq cn^2\) into the recurrence

\[\begin{split} T(n) & \leq 4c \left(\frac{n}{2}\right)^2 + n \\ & = 4c \frac{n^2}{4} + n \\ & = cn^2 + n \\ & \leq cn^2 \\ \end{split}\]

Where the last step (\(cn^2 + n \leq cn^2\)) does not hold for any valid value of \(c\). Next, let us modify our guess to subtract a lower order term: \(T(n) \leq cn^2 - bn\). Substituting this new guess into the recurrence yields

\[\begin{split} T(n) & \leq 4 \left( c \left(\frac{n}{2}\right)^2 -b \frac{n}{2} \right) + n \\ & = cn^2 - 2bn + n \\ & \leq cn^2 - bn \\ \end{split}\]

Where the last step holds for \(b \geq 1\).