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$.
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}.$$