Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

Question

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$)?

Answer 1

Assume that $n \ge 4$ (the induction step is only handling $n \ge 10$ anyway), then $n-n^\frac{2}{5} > 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.

Answer 2

In addition, if you are fine not using induction, you could do the following to get to a recurrence where the Master theorem can be applied.

First of all lets pretend there is no floor in the original recurrence (there are formal ways to get rid of that while obtaining the same asymptotic result), and define $S(n) = T(2^n)$. Then:

$$ S(n) = T(2^n) = 5^{2^n} + 3 T(2^{\frac{2}{5}n}) = 5^{2^n} +3 S\left(\frac{2}{5} n\right). $$

This recurrence has solution $S(n) = O(5^{2^n})$, hence: $$ T(n) = S(\log n) = O(5^{2^{\log n}}) = O(5^n). $$