Question: [![image](https://i.stack.imgur.com/7vpac.png)](https://i.stack.imgur.com/7vpac.png)

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.

Answer: 
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$.
\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$.