<s>[INST] Solving Geometric Progression. Question
$\text{While solving recurrence relation ,}$

$$T(n)=T(\sqrt{n})+n$$

I got stuck in following Geometric series.
$$T(n)=n^{\frac{1}{2^{0}}}+n^{\frac{1}{2^{1}}}+n^{\frac{1}{2^{2}}}+...n^{\frac{1}{2^{k-1}}}$$
where $k=\log \log n$
Please help me out.
 [/INST] We must specify the numbers $n$ for which the recurrence holds (it cannot hold for $n=1$).  
Suppose there is a real number $B$ and a function $T:[\sqrt{2},\infty)\rightarrow\mathbb{R}$ such that the following two properties hold:  
1) $|T(x)|\leq B$ for all $x \in [\sqrt{2},2)$. 
2) $T(x) = T(\sqrt{x}) + x$ for all $x \geq 2$. 
Lemma
a) All real numbers $x \geq 2$ can be written $x=z^{2^k}$ for some real number $z \in [\sqrt{2},2)$ and some integer $k \in \{1, 2, 3, \ldots\}$. 
b) If  $z \in [\sqrt{2},2)$ and $n \in \{1, 2, 3, ...\}$, we have the equality:
$$ \boxed{T(z^{2^n}) = T(z) + z^{2^1} + z^{2^2} + ... + z^{2^n}} $$
c) The function $T$ satisfies 
$$ \boxed{-B + x \leq T(x) \leq B + x + \left[\frac{\sqrt{2}}{\sqrt{2}-1}\right]\sqrt{x}  \quad, \forall x \geq 4}$$
and so 
$$ \lim_{x\rightarrow\infty} \frac{T(x)}{x} = 1 $$
Proof
Proof of (a):  Fix $x \geq 2$.  Take repeated square roots until the result first decreases below 2, that is, until we find a positive integer $k$ such that $x^{(1/2)^k}<2$ but $x^{(1/2)^{k-1}}\geq 2$.  Define $z=x^{(1/2)^k}$ and note that $\sqrt{2}\leq z < 2$.  $\Box$
Proof of (b): Fix $z \in [\sqrt{2},2)$.  Then $z^2\geq 2$ and from the recurrence relation we get
\begin{align}
T(z^{2^1}) &= T(z) + z^{2^1} \\
T(z^{2^2}) &= T(z^{2^1}) + z^{2^2} = T(z) + z^{2^1} + z^{2^2} \\
T(z^{2^3}) &= T(z^{2^2}) + z^{2^3} = T(z) + z^{2^1} + z^{2^2}+ z^{2^3}
\end{align}
And so on.  So for any $z \in [\sqrt{2},2]$ and any positive integer $n$ we have: 
$$T(z^{2^n}) = T(z) + z^{2^1} + z^{2^2} + ... + z^{2^n} $$
This proves part (b). $\Box$
Proof of (c): Fix $x \geq 4$.  Then $\sqrt{x}\geq 2$ and from part (a) we know $\sqrt{x}=z^{2^k}$ for some real number $z \in [\sqrt{2},2)$ and some integer $k \in \{1, 2, 3, ...\}$. Hence, $x =z^{2^{k+1}}$. Define $n=k+1$, so that $x=z^{2^n}$, and note that $n\geq 2$.  We know from part (b) that 
$$T(z^{2^n}) = T(z) + z^{2^1} + z^{2^2} + ... + z^{2^n} \quad (Eq. 1)$$
Thus: 
\begin{align}
T(z) + z^{2^n} &\leq T(z^{2^n}) \quad \mbox{[from (Eq. 1)]} \\
&= T(z)  + z^{2^n} + (z^{2^1} + ... + z^{2^{n-1}}) \quad \mbox{[from (Eq. 1)]}\\
&\leq T(z) + z^{2^n} + \sum_{i=2}^{2^{n-1}} z^i  \quad \mbox{[since this fills  in the missing $z^i$ terms]}\\
&= T(z) + z^{2^n} +  z^2\frac{(z^{2^{n-1}-1}-1)}{z-1} \\
&\leq T(z) + z^{2^n} + \left[\frac{z}{z-1} \right]z^{2^{n-1}}\\
&\leq T(z) + z^{2^n} +\left[\sup_{y\in [\sqrt{2},2]}\frac{y}{y-1}\right] z^{2^{n-1}} \\
&= T(z) + z^{2^n} +\left[\frac{\sqrt{2}}{\sqrt{2}-1}\right]\sqrt{z^{2^n}}
\end{align}
Since $-B\leq T(z) \leq B$ we obtain 
$$ -B + z^{2^n} \leq T(z^{2^n}) \leq B + z^{2^n} + \left[\frac{\sqrt{2}}{\sqrt{2}-1}\right]\sqrt{z^{2^n}} $$
Substituting $x=z^{2^n}$ gives the result. $\Box$
</s>