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\).