Solving the recurrence $T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$ A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation:
$$T(n) = \sqrt n T(\sqrt{n}) + n$$
There are several ways to solve this recurrence relation and this question has already been asked here.
I was talking to my student about this problem and mentioned that it's quite hard to solve and is pretty dependent on the particular choices being made. As an example, I suggested this variant of a recurrence relation that was less simple to solve:
$$T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$$
The TA and I tried solving this recurrence for about an hour and a half without making any progress. Here are a few things we tried:


*

*My approach to solving the initial recurrence relation was to draw out a recursion tree and notice that each level of the tree contributes $n$ to the total and that there are $O(\log \log n)$ layers, so the recurrence solves to $O(n \log \log n)$. When I tried doing this here, I noticed that the work per layer was no longer constant; instead, the top layer sums to $\sqrt{n}$, the second layer to $n^{3/4}$, the third to $n^{7/8}$, etc. We got stuck working with the summation $n^{1/2} + n^{3/4} + n^{7/8} + ...$.

*We tried using the iteration method to unroll the recurrence. With the original recurrence relation, this works out nicely; here, we got stuck at the same summation given above.
I'm completely stuck trying to figure out how to solve this recurrence relation. There's nothing riding on it per se - I don't need to solve it for any particular reason - but the fact that we arrived at it by a straightforward modification of a common algorithms problem set question makes it all the more enticing.
Any idea how to solve this recurrence?
Thanks!
 A: As you mention, the explicit solution (assuming appropriate initial conditions) is
$$
\begin{align*}
T(n) &= n^{1/2} + n^{3/4} + \cdots + n^{1-1/\log n} \\ &=
n \left(\frac{1}{n^{1/2}} + \frac{1}{n^{1/4}} + \cdots + \frac{1}{n^{1/\log n}} \right).
\end{align*}
$$
Note that $1/n^{1/\log n} = 1/2$. Another way of writing the same formula is
$$
T(n) = n\left(\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^4} + \cdots + \frac{1}{2^{2^{\log\log n-1}}} \right).
$$
The infinite series
$$
\sum_{k=0}^\infty \frac{1}{2^{2^k}}
$$
converges to some limit $L \approx 0.81642$, and so
$$
T(n) = Ln + o(n),
$$
the formula holding for $n$ of the form $2^{2^k}$.
A: For powers of powers of $2$,
$$T(2^2)=2^1T(2^1)+2^1,\\
T(2^4)=2^2T(2^2)+2^2=2^22^1T(2^1)+2^22^1+2^2,\\
T(2^8)=2^4T(2^4)+2^4=2^42^22^1T(2^1)+2^42^22^1+2^42^2+2^4,\\
T(2^{16})=2^8T(2^8)+2^8=2^82^42^22^1T(2^1)+2^82^42^22^1+2^82^42^2+2^82^4+2^8\\
\cdots\\
T(2^{2^k})=2^{2^k-1}\left(T_2+1+\frac1{2^1}+\frac1{2^12^2}+\frac1{2^12^22^4}+\frac1{2^12^22^42^8}\cdots\right),
\\
\color{green}{T(n)=\frac n2\left(T_2+S\right)+o(n)},
$$where $S\approx1.63284301804$.
