How to solve this recurrence using back substitution: $T(n)=T(n^{1/2})+n$ where T(2)=1

Question

I am trying to solve this recurrence using back substitution.

$$T(n)=T(n^{1/2})+n$$ where T(2)=1

I solved it and got the kth term as follows:

$$T(n)=T(n^{1/2^k})+(n)^{1/2}+(n)^{1/2^2}+(n)^{1/2^3}+....(n)1/{2^{{k-1}}}+n$$

But i don't have any idea how to deal with this series.Please give me some idea to solve this series.

Answer 1

Since your sequence is defined only for $n=2^{2^k}$, $k\ge 0$, it seems useful to rewrite it as

$$S(k):=T(2^{2^k}),\quad k\ge 0.$$ Then you are able to write it as $$S(k+1) = S(k) + 2^{2^{k+1}}, \quad S(0) = 1.$$ It would give $$S(k) = -1+\sum_{s=0}^k 2^{2^s}.$$