Need to show $f_k=o(f_{k-1})$ for $k > 1$ Based off the description of an algorithm, I came up with the following worst-case run time
$$f_k(n)=n^{\frac 1 k}+f_{k-1}(n^{\frac{k-1}{k}})$$
$$f_2(n)=2 \sqrt n$$
I need to show that each $f$ becomes asymptotically slower than the previous, i.e.
$$\lim_{n \to \infty} \frac{f_k(n)}{f_{k-1}(n)}=0 \text{ for }k=2, 3, ...$$
I noticed after expanding the definition of $f_k$ for a few terms it is $O(n^\frac{1}{k})$ but from this previous question I asked, this was not enough to show the limit exists. At the moment I am stuck trying to prove this.
 A: As promised in comment I solve recurrent relation (but ask you double check it):
$$\begin{array}{l}f_k(n)=n^{\frac 1 k}+f_{k-1}(n^{\frac{k-1}{k}})=\\
=n^{\frac 1 k}+ n^{\frac{k-1}{k}\cdot \frac{1}{k-1}}+f_{k-2}(n^{\frac{k-1}{k}\cdot \frac{k-2}{k-1}}) = 2n^{\frac 1 k}+ f_{k-2}(n^{\frac{k-2}{k}}) =\\
= 2n^{\frac 1 k} +  n^{\frac{k-2}{k}\cdot \frac{1}{k-2}}+f_{k-3}(n^{\frac{k-2}{k}\cdot \frac{k-3}{k-2}}) = 3n^{\frac 1 k}+ f_{k-3}(n^{\frac{k-3}{k}}) =\\
=\cdots = mn^{\frac 1 k}+ f_{k-m}(n^{\frac{k-m}{k}}) = \cdots = \lvert \text{ taking }k-m=2\rvert=\\
=(k-2)n^{\frac 1 k}+ f_{2}(n^{\frac{2}{k}}) =kn^{\frac 1 k}\end{array}$$
Now it's obvious to say that
$$\lim_{n \to \infty} \frac{f_k(n)}{f_{k-1}(n)}=\lim_{n \to \infty}\frac{k}{k-1}n^{\frac{1}{k}-\frac{1}{k-1}}=0 $$
And, at end,  $f_k(n)=kn^{\frac 1 k}\in \Theta(n^{\frac 1 k})$.
A: $f_k(n)
=n^{\frac 1 k}+f_{k-1}(n^{\frac{k-1}{k}})
$
so
$f_k(n^k)
=n+f_{k-1}(n^{k-1})
$.
Letting
$g_k(n)
=f_k(n^k)
$,
$g_k(n)
=n+g_{k-1}(n)
$.
Therefore
$n
=g_k(n)-g_{k-1}(n)
$
so
$\begin{array}\\
(m-2)n
&=\sum_{k=3}^mn\\
&=\sum_{k=3}^m(g_k(n)-g_{k-1}(n))\\
&=g_m(n)-g_{2}(n)\\
&=g_m(n)-f_{2}(n^2)\\
&=f_m(n^m)-2n\\
\end{array}
$
so
$f_m(n^m)
=mn
$
or
$f_m(n)
=mn^{1/m}
$.
Therefore
$\begin{array}\\
\dfrac{f_m(n)}{f_{m-1}(n)}
&=\dfrac{mn^{1/m}}{(m-1)n^{1/(m-1)}}\\
&=\dfrac{m}{m-1}n^{1/m-1/(m-1)}\\
&=\dfrac{m}{m-1}n^{-1/(m(m-1))}\\
&\to 0
\qquad\text{as } n \to \infty\\
\end{array}
$
for fixed $m$.
