Recurrence relation by substitution I have an exercise where I need to prove by using the substitution method the following
$$T(n) = 4T(n/3)+n = \Theta(n^{\log_3 4})$$
using as guess like the one below will fail, I cannot see why, though, even if I developed the substitution
$$T(n) ≤ cn^{\log_3 4}$$
finally, they ask me to show how to substract off a lower-order term to make a substitution proof work. I was thiking about using something like
$$T(n) ≤ cn^{\log_3 4}-dn$$
but again, I cannot see  how to verify this recurrence.
What I did:
$$T(n) = 4T(n/3)+n$$ 
$$\qquad ≤ \frac{4c}{3}n^{\log_3 4} + n$$
and then from here, how to proceed and conclude that the first guess fails?
The complete exercise says:

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


This recurrence has the nice property that we can give an explicit value for all $n$, not just powers of three. Let $$ n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k$$ be the representation of $n$ in base three. With $T(0) = 0$, we have by inspection
$$ T(n) = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 
\sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j} =
\sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 
\sum_{k=0}^{\lfloor \log_3 n \rfloor - j } d_{k+j} 3^k
.$$
For a lower bound, consider those $n$ that consist of a leading one digit followed by zeroes. This gives
$$ T(n) \ge \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 3^{\lfloor \log_3 n \rfloor - j} =
3^{\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} 
\left(\frac{4}{3}\right)^j $$ which is $$ 3^{\lfloor \log_3 n \rfloor}
\frac{(4/3)^{1+ \lfloor \log_3 n \rfloor}-1}{4/3-1} = 
4^{1+ \lfloor \log_3 n \rfloor} - 3^{1+ \lfloor \log_3 n \rfloor}.$$
For an upper bound, consider those $n$ that consist entirely of digits with value two.
$$ T(n) \le 2 \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 
\sum_{k=0}^{\lfloor \log_3 n \rfloor - j } 3^k =
2 \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 
\frac{3^{1+\lfloor \log_3 n \rfloor - j}-1}{3-1} < 
\sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 3^{1+\lfloor \log_3 n \rfloor - j}
$$ which is
$$3^{1+ \lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} 
\left(\frac{4}{3}\right)^j =
3^{1+\lfloor \log_3 n \rfloor}
\frac{(4/3)^{1+ \lfloor \log_3 n \rfloor}-1}{4/3-1} = 
3 \times 4^{1+ \lfloor \log_3 n \rfloor} - 3 \times 3^{1+ \lfloor \log_3 n \rfloor}$$
What we have shown here is that for all $n$,
$$ T(n) \in 
\Theta\left(4^{1+ \lfloor \log_3 n \rfloor} - 3^{1+ \lfloor \log_3 n \rfloor}\right) =
\Theta\left(4^{1+ \lfloor \log_3 n \rfloor}\right) =
\Theta\left(4^{\lfloor \log_3 n \rfloor}\right).$$
But $$4^{\lfloor \log_3 n \rfloor} \le
4^{\log_3 n} = 4^{\frac{\log_4 n}{\log_4 3}} =
n^{\frac{1}{\log_4 3}} = n^{\log_3 4}$$
and similarly
$$4^{\lfloor \log_3 n \rfloor} >
4^{\log_3 n -1} = \frac{1}{4} 4^{\frac{\log_4 n}{\log_4 3}} =
\frac{1}{4}n^{\frac{1}{\log_4 3}} = \frac{1}{4}n^{\log_3 4}$$
so that finally
$$ T(n) \in \Theta\left(n^{\log_3 4}\right).$$
