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. 

 A: It seems the cause of your trouble is simply that you made a mistake while computing $(n/3)^{\log_34}$, which is $n^{\log_34}/4$ and not $n^{\log_34}/3$.
(Note that $(n/3)^{\log_34}=n^{\log_34}/3^{\log_34}$ and that $3^{\log_34}=\exp(\ln3\cdot\log_34)$ with $\ln3\cdot\log_34=\ln3\cdot\ln4/\ln3=\ln4$ hence $3^{\log_34}=4$.)
Anyway, the hint you were given is to assume that $T(n)\leqslant An^{\log_34}+Bn$ $(*)$ and to check if $(*)$ is hereditary for some suitable $B$. Hence, assume $(*)$ holds for $n/3$, then 
$$
T(n)=4T(n/3)+n\leqslant 4A(n/3)^{\log_34}+4B(n/3)+n=An^{\log_34}+(4B/3+1)n,
$$ 
and one sees that $(*)$ holds for $n$ as soon as $4B/3+1\leqslant B$, for example for $B=-3$.
Now, choosing $A$ large enough such that $T(n)\leqslant An^{\log_34}-3n$ holds for $n$ small, one sees that $T(n)\leqslant An^{\log_34}-3n$ holds for every $n$.
Likewise, there exists $A'$ such that $T(n)\geqslant A'n^{\log_34}-3n$ holds for $n$ small, and this is enough to guarantee that $T(n)\geqslant A'n^{\log_34}-3n$ holds for every $n$. Thus, $T(n)=\Theta(n^{\log_34})$.
In hindsight, all this can be made easier using the change of variable $\bar T(n)=T(n)+3n$ since $\bar T(n)=4T(n/3)+n+3n=4\bar T(n/3)$, a recursion whose solution can be computed directly.
A: 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$$
A: 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).$$
