recurrence algorithms, algebra issues? 
So we're given a problem to solve... no other instructions..
the answer is given as well. 
I am having trouble understanding how this problem is unrolled. 
I understand that $\sqrt{2^{2^k}}$ can also be represented as $2^{2^{k-1}}$.
I don't understand how $2^{2^{k-2}}$ then becomes $2^{2^{-1}}$.
Does this mean that $k$ eventually becomes $0$ in this series?
Can someone explain this a little bit better to me because I am lost.
Why does $n = 2^{2^k}$?
Any help is much appreciated, thanks.
 A: There is a first issue in the definition as it is given, $T(1) = 1$ and $T(n) = T(\sqrt{n}) +n$. The notation $n$ suggests that we are working with natural numbers. But then, what is the value of $T(2)$? In reality, the induction rule only gives you the value of $T(n)$ when $n$ is of the form $2^{2^k}$. This is the reason of the suggested change of variable $n = 2^{2^k}$.
Now, if I understood correctly your question, you arrived safely to the second line, $T(n) = T(2^{2^{k-1}}) + 2^{2^k}$. The trick is that it should actually be written as
$$
(1) \quad T(2^{2^k}) = T(2^{2^{k-1}}) + 2^{2^k}
$$ 
and this holds for every $k$. In particular, it also holds for $k-1$, which gives you
$$
(2) \quad T(2^{2^{k-1}}) = T(2^{2^{k-2}}) + 2^{2^{k-1}}. 
$$
Reporting in (1) yields 
$$
T(2^{2^k}) = T(2^{2^{k-1}}) + 2^{2^k} = T(2^{2^{k-2}}) + 2^{2^k} + 2^{2^{k-1}}
$$
that is, the third line. You can now iterate this process until $k = 0$.
A: Try thinking of it as repeatedly applying the function $T$. Start out with letting $n = 2^{2^k}$. Then
$$T(n) = T(\sqrt{n}) + n = T\left(\sqrt{2^{2^k}}\right) + 2^{2^k} = T\left(2^{2^{k - 1}}\right) + 2^{2^k}.$$
Now the question is, what is $T\left(2^{2^{k - 1}}\right)$? Well, we use the definition of $T$ again:
$$T\left(2^{2^{k - 1}}\right) = T\left(\sqrt{2^{2^{k - 1}}}\right) + 2^{2^{k - 1}} = T\left(2^{2^{k - 2}}\right) + 2^{2^{k - 1}}.$$
If we plug this back into the previous equation, we get
$$T(n) = T\left(2^{2^{k - 2}}\right) + 2^{2^{k - 1}} + 2^{2^k},$$
so now we need to figure out what $T\left(2^{2^{k - 2}}\right)$ is.
If we continue to do this, we eventually reach the point where we have to figure out what $T(1)$ is, and this is simply $1$, so we get
$$T(n) = 1 + 2^{2^0} + 2^{2^{1}} + \dots + 2^{2^k}.$$
A: \begin{align}
   T(n) &= n + T(n^{1/2}) \\
   &= n + n^{1/2} + T(n^{1/4}) \\
   &\phantom{n} \vdots \\
   &= n + n^{1/2} + n^{1/4} + n^{1/8} \cdots
\end{align}
The fact that $\displaystyle \lim_{x \to \infty} n^{2^{-x}} = 1$ justifies the $``\cdots"$ and also implies that $T(n)$ does not exists except for $n=0$.
