Method for solution to a recurrence

Question

Is there a closed form solution or tight bound to recurrence $T[n]=k\cdot T[n^{1/c}] + (\log n)^{r}$ with $k,c,r\geq1$ and $T[n]=O(1)$ if $n\leq2$?

Answer 1

Hint:

Let $n=e^{c^m}$ so that $n^{1/c}=e^{c^{m-1}}$.

The recurrence turns to

$$U_m=k\,U_{m-1}+(c^r)^m.$$

And with

$$U_m=k^mV_m,$$

$$V_m=V_{m-1}+\left(\frac{c^r}k\right)^m.$$

Finally, $$T_n=\frac{(c^r)^{\log_c(\log n)+1}-k^{\log_c(\log n)+1}}{c^r-k}=\frac{c^r\log^rn-k\log^{\log_ck}n}{c^r-k}.$$

Boundedness requires $k,c<1$.