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