# Solving $T(n) = 4T(n/2) + n^3$ with substituton method

I am trying to solve the following recurrence $$T(n) = 4T(n/2) + n^3$$ with substitution method. My guess is $$T(n) = \Theta (n^3)$$ (I used master theorem) and I tried to show that $$T(n) \leq cn^3$$. But, when I substitute I got $$T(n) \leq c \frac{n^3}{2} + n^3$$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?

Your guess works: if $$T(n) \le c n^3$$ and $$c \ge 2$$ then $$T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3.$$