<s>[INST] 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. 

 [/INST] Let $n = 3^{m+1}$. Then we have
$$T \left(3^{m+1} \right) = 4T \left(3^{m} \right) + 3^{m+1}$$
Let $T\left(3^m\right) = g(m)$. We then get that
$$g(m+1) = 4g(m) + 3^{m+1} = 4(4g(m-1) + 3^m) + 3^{m+1} = 4^2 g(m-1) + 4\cdot 3^m + 3^{m+1}\\
= 4^2 (4g(m-2) + 3^{m-1}) + 4\cdot 3^m + 3^{m+1} = 4^3 g(m-3) + 4^2 \cdot 3^{m-1} + 4 \cdot 3^m + 3^{m+1}$$
Let $\lfloor m \rfloor = M$
Hence, by induction we get that
$$g(m+1) = 4^M g(m-M) + \sum_{k=0}^{M-1} 4^k \cdot 3^{m+1-k} = 4^M g(m-M) + 3^{m+1} \sum_{k=0}^{M-1} (4/3)^k\\
= 4^M g(m-M) + 3^{m+1} \dfrac{(4/3)^M-1}{4/3-1}= 4^M g(m-M) + 3^{m+2} ((4/3)^M-1)$$
Hence, we get that
$$g(m+1) = 4^M g(m-M) + 3^{m+2-M} \cdot 4^M - 3^{m+2}$$
To get the order, we can take $m$ to be an integer.
Hence, $m=M = \log_3(n)-1$ and we get that
$$g(m+1) = 4^{\log_3(n)-1} g(0) + 3^{2} \cdot 4^{\log_3(n)-1} - 3^{\log_3(n)+1}$$
Note that $4^{\log_3(n)} = n^{\log_3(4)}$. Hence, we get that
$$T(n) = \dfrac{g(0)}4 n^{\log_3(4)} + \dfrac94 \cdot n^{\log_3(4)} - 3n$$
</s>