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) \le cn^{\log_3 4}$$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.

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

\begin {aligned} T(n) & = 4T(n/3) + n \\ & \le 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 {aligned}

We cannot proceed further with this to show our hypothesis is correct.

Now, let us assume $$T(n) \le cn^{\log_3 4} - dn$$ for all $$n \ge n_0$$, where $$c$$, $$d$$, and $$n_0$$ are positive constants.

\begin {aligned} T(n) & = 4T(n/3) + n \\ & \le 4\left(c\left(\frac n 3\right)^{\log_3 4} - \left(\frac {dn} 3\right)\right) + n \\ & = 4c\left(\frac {n^{\log_3 4}} {3^{\log_3 4}}\right) - 4\left(\frac {dn} 3\right) + n \\ & = 4c\left( \frac {n^{\log_3 4}} {4}\right) - 4\left(\frac {dn} 3\right) + n \\ & = cn^{\log_3 4} - dn - dn/3 + n \\ & = cn^{\log_3 4} - dn - (d/3 - 1) n \\ & \le cn^{\log_3 4} - dn \end {aligned}

The last step holds as long as $$(d/3 - 1) n \ge 0$$.

If we pick $$n_0 = 1$$, then we need $$d \ge 3$$.