How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

Question

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method?

I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $

I need a help with finding the final solution here.

Answer 1

I suggest working as follows, set : $$m=log_2(log_2(n)) $$

so that: $n=2^{2^m}$ and you will get : $$ T(n)=T(2^{2^{m-1}})+2^{2^m}$$

hence : $$ T(n)=T(2)+2^{2^1}+\cdots+2^{2^{m-1}}+2^{2^m} $$

but $2^{2^1}+\cdots+2^{2^{m-1}}+2^{2^m}$ is equivalent to $2^{2^m}$ so $T(n)$ is equivalent to $n$