Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?
You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases}
  8 &amp; n = 2\\
  8T\left(\tfrac{n}{2}\right) + n^3 &amp; n &gt; 2\\
\end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n &gt; 2$):

$$\begin{align*}
T(n) &amp; = 8T\left(\tfrac{n}{2}\right) + n^3\\
     &amp; = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\
     &amp; = n^3 \log_2 \tfrac{n}{2} + n^3\\
     &amp; = n^3 \log_2 n - n^3 \log_2 2 + n^3\\
     &amp; = n^3 \log_2 n - n^3 + n^3\\
     &amp; = n^3 \log_2 n &amp; \square
\end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds. 



However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases}
f(b) &amp; n = b\\
aT(n/b) + f(n) &amp; n &gt; b
\end{cases}$$ 

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*}
T(n) &amp; = aT(n/b) + f(n)\\
     &amp; = a(aT(n/b^2) + f(n/b)) + f(n)\\
     &amp; = a^2T(n/b^2) + af(n/b) + f(n)\\
     &amp; \vdots\\
     &amp; = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right)
\end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*}
T(n) &amp; = 8T\left(\tfrac{n}{2}\right) + n^3\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} n^3\\
     &amp; = n^3 \log_2 n\\
\end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.



Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases}
  12 &amp; n = 3\\
  5T\left(\tfrac{n}{3}\right) + n^2 + n &amp; n &gt; 3\\
\end{cases}$$