Solve the recurrence relation: $T_n=\sqrt nT_{\sqrt n} +1$

Question

Try to solve it over similar methods , but I can not give the answer

$T_n=\sqrt nT_{\sqrt n} +1$

Can anyone arrive at the solution？

Answer 1

For $n = 1$ you have $T_1 = \sqrt{1} T_1 + 1 = T_1 + 1$, which is impossible.

Answer 2

There will be about $\log\log n$ iterations of the square-root until you reach numbers near $1$. The sequence becomes approximately $n^{1/2}+n^{3/4}+n^{7/8}+...+n^{1-\epsilon}T(n^{\epsilon})$, or $T(n)\approx n\log\log n$.
As Paul says, you have to keep away from $n=1$.