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