We have recurrence $T(n)=10T(\dfrac{n}{3})+n\sqrt{n}$ and assume $T(1)$ is a constant. With Master Theorem applied, we get $T(n)=\Theta(n^{\log_3{10}})$ as this recurrence is the first case of Master Theorem. Now I want to prove my answer using induction. I'm familiar with induction generally in mathematics, but for this kind of problem I've got a little confused. I don't know what base cases should be in this problem, and how to make an induction hypothesis and prove the next step. This is what I tried:
To prove $T(n)=\Theta(n^{\log_3{10}})$, we should prove $T(n)=\mathcal{O}(n^{\log_3{10}})$ and $T(n)=\Omega(n^{\log_3{10}})$. To show that $T(n)=\mathcal{O}(n^{\log_3{10}})$, we claim it's correct, so because of definition of $\mathcal{O}(f(n))$ we'll have:
$\begin{align} T(n) = & 10T(\frac{n}{3})+n\sqrt{n}\\ \leq & 10(c(\frac{n}{3})^{\log_3{10}})+n\sqrt{n}\\ = & 10c(10)^{\log_3{\frac{n}{3}}}+n\sqrt{n}\\ = & 10c(10)^{(\log_3{n})-1}+n\sqrt{n}\\ = & c(10)^{\log_3{n}}+n\sqrt{n}\\ = & cn^{\log_3{10}}+n\sqrt{n} \end{align}$
But at this point, we know $n\sqrt{n}>0$ as $n$ is a positive (and I think large) value. So we can't reach $T(n)\leq cn^{\log_3{10}}$. I searched for some similar example but it was somehow confusing to me, specially about what is base case, what is hypothesis and what is the next step in proof. I would be really thankful if you exaplain these to me. And also help to prove this using induction. Any help is much much appreciated.
Here's a sketch for part of the proof. Assume:
$$ T(n) \leq c \cdot n^k - d \cdot n \sqrt{n} $$
with $k = \log_3 10$ and $c,d > 0$. Then:
$$ T(n) = 10 T\left( \frac{n}{3} \right) + n \sqrt{n} $$ $$ \leq 10 \left( c \cdot \left(\frac{n}{3}\right)^k - d \cdot \frac{n}{3} \sqrt{\frac{n}{3}}\right) + n \sqrt{n} $$ $$ = c \cdot n^k - 10 \cdot d \cdot \frac{n}{3} \sqrt{\frac{n}{3}} + n \sqrt{n} $$ $$ = c \cdot n^k - \left(\frac{10}{3 \sqrt{3}} \cdot d - 1\right) n \sqrt{n} $$ $$ \leq c \cdot n^k - d \cdot n \sqrt{n} $$
which holds when $ \left(\frac{10}{3 \sqrt{3}} - 1\right)d \geq 1 $. And so:
$$T(n) \leq c \cdot n^k - d \cdot n \sqrt{n}$$
which means:
$$ T(n) = O(n^k) = O\left(n^{\log_3 10}\right) $$