Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$ I need to prove that the following recurrence relation is $O(5^n)$:
$$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$
And $T(n)=\Theta(1)$ for $n\le 9$.
I am trying induction, and proving that there exists $c$ such that $T(n)\le c\cdot5^n$, but I am stuck at the induction step:
$T(n)=5^n+3T(\big\lfloor n^\frac{2}{5}\big\rfloor)\le5^n+3c\cdot 5^{\lfloor n^\frac{2}{5}\rfloor}\le5^n+3c \cdot 5^{n^{\frac{2}{5}}}=\bigg(1+\frac{3c}{5^{n- n^\frac{2}{5}}}\bigg)\cdot 5^n$.
How can I continue in the induction (turn the parenthesis into the constant $c$)?
Assume that $n \ge 4$ (the induction step is only handling $n \ge 10$ anyway), then $n-n^\frac{2}{5} &gt; n - \sqrt{n} \ge 2$ and you have:
$$
\left( 1 + \frac{3c}{5^{n-n^\frac{2}{5}}} \right) \cdot 5^n \ge
\left( 1 + \frac{3c}{5^2} \right) \cdot 5^n =
\left( 1 + \frac{3}{25} c\right) \cdot 5^n.
$$
The latter term is not larger than $c \cdot 5^n$ whenever $1 + \frac{3}{25} c \le c$, i.e., when $c \ge \frac{25}{22}$.
Pick $c$ large enough to satisfy $c \ge \frac{25}{22}$ and the base cases, and you're done.