Using the master method in Section 4.5, you can show that the solution to the recurrence \(T(n) = 4T(n/3) + n\) is \(T(n) = \Theta(n^{\log_3 4})\). Show that a substitution proof with the assumption \(T(n) \leq cn^{\log_3 4}\) 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^{\log_{3}4}\) into the recurrence

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

Which we cannot proceed further from. Next, let us modify our guess to subtract a lower-order term: \(T(n) \leq cn^{\log_{3}4} - bn\). Substituting this new guess into the recurrence yields

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

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