# Proof $\lim\limits_{n \rightarrow \infty} {\sqrt{2+\sqrt{2+\cdots+\sqrt{2}}}}=2$ using Banach's Fixed Point

I'd like to prove $\lim\limits_{n \rightarrow \infty} \underbrace{\sqrt{2+\sqrt{2+\cdots+\sqrt{2}}}}_{n\textrm{ square roots}}=2$ using Banach's Fixed Point theorem.

I think I should use the function $f(x)=\sqrt{2+x}$. This way, if I start the iterations for example with $x_0=0$, I will have $x_1=\sqrt2$. When I calculate $x_2$ I will get $\sqrt{2+\sqrt{2}}$. And $x_3 = \sqrt{2+\sqrt{2+\sqrt{2}}}$ and so on. I can see that these iterations are monotone increasing, but how can I show that this converges to 2?

Pseudo-related formula I found: http://en.wikipedia.org/wiki/Vieta_formula

Following clark's advice, here's my proof this is a contraction. I'm using the interval $D=[0, 2]$.

$f'(x)=\frac{1}{2\sqrt{x+2}}$, which is monotone decreasing. This means its highest value in $D$ is $0$. $f'(0)=\frac{1}{2\sqrt{2}} < 1$. The rate $M$ of the contraction is then $\frac{1}{2\sqrt{2}}$.

-
Where's $n$ in the first equation? I see $n \to \infty$, but I don't see what $n$ does. – Argon Jun 30 '12 at 19:54
@Argon: The meaning is presumably that $n$ is the number of iterated square roots in the expression for which Clash is taking the limit. – KCd Jun 30 '12 at 19:56
Yes, exactly, it's the ammount of square roots. Sorry, will edit the question right now! – Clash Jun 30 '12 at 19:57
I think Banach's fixed point theorem is overkill. If you show the sequence is bounded from above (you say you already showed it is monotone increasing) then the limit exists in the real numbers. Call the limit $L$. Then from the limit defining $L$, we have $\sqrt{2 + L} = L$. Thus $2 + L = L^2$. The only solutions to that in the real numbers are $L=2$ and $L=-1$. The sequence can't have a negative limit, so $L=2$. – KCd Jun 30 '12 at 19:59
@KCd, well, the whole point of the exercise is to use Banach's Theorem, so sorry that I can't use your solution... – Clash Jun 30 '12 at 20:33

In order to use Banach's fixed pointed theorem you have to show $|f(x)-f(y)| < M(|x-y|)$ in some interval, say $[a,b]$. Then your work would to prove that starting with $x_0=c\,\,$ then$x_{n+1}=f(x_n)$ stays in that interval, i.e.: $a \leq x_n \leq b$,(so your function is well defined $f:[a,b] \rightarrow \mathbb{R}$. That $M$ can be found $f'(y_0) = M$ and bound the derivative. Then you will know the limit is the solution $f(k)=k$

EDIT: Since you took the interval [0,2] you need to prove that for $y \in [0,2]$ $0 \leq f(y) \leq 2$ the first holds trivially. For the second you have $\sqrt{2+ \sqrt {2}} \leq 2 \Leftrightarrow \sqrt {2} \leq 2$ which holds. Now you are done because you have that every $x_n$ stays in the interval you choosed. So Banach's fixed point theorem can be applied. (Note that you defined $f$ on $D$ so the previous step is to make sure that the $f$ you took is well defined, because every $x_n$ is used by $f$ to define $x_{n+1}$).

-
thanks for the reply clark! could you please take a look at my edited question? I don't understand how I should proceed now – Clash Jun 30 '12 at 21:00
Now that I have shown that it's a contraction, I can directly apply banach's theorem, which says if I do an unlimited ammount of iterations, I will find the fixed point. So this limit is exactly the one above, which means that that limit is the fixed point, but why is it 2? – Clash Jun 30 '12 at 21:16
you solve the equation $f(y)=y$ that is the fixed point(the limit) for $f$ so $\sqrt{y+2} =y$ and you solve it. – clark Jun 30 '12 at 21:21
thanks! [8 chars] – Clash Jun 30 '12 at 21:42
glad I could help :) – clark Jun 30 '12 at 21:47

Define que sequence $\{x_n\}$ by

$$\begin{cases} x_0=0 \cr x_n = \sqrt{k+x_{n-1}}\end{cases}$$

with $k>0$

I claim that $$\lim_{n \to \infty}x_n=r$$

where $r$ is the positive root of the equation

$$\tag A x^2-x-k=0$$

PROOF

$(1)$ The sequenece is increasing. By induction:

It is true for $x_0=0,x_1=\sqrt k$. Assume true for $k=1,2,\dots,n$, then

$$x_n > x_{n-1} \Rightarrow x_n+k > x_{n-1}+k \Rightarrow$$

$$\Rightarrow \sqrt{x_n+k} > \sqrt{x_{n-1}+k} \Rightarrow x_{n+1} > x_n$$

$(2)$ The sequence is bounded above by $r$. By induction:

It is true for $n=0,1$. Assume true for $k=1,2,\dots,n$, then

$$x_{n} < r$$

$$x_{n}+k < r+k$$

$$\sqrt{x_{n}+k} < \sqrt{r+k}=r$$

since $r$ satisfies $(A)$.

Then by the Monotone Convergence Theorem, the sequence has a limit. In particular, this means that $\ell = \lim x_n = \lim x_{n-1}$, so that

$$\lim_{n \to \infty} x_n = \lim_{n \to \infty}\sqrt{x_{n-1}+k}$$

$$\lim_{n \to \infty} x_n = \sqrt{ \lim_{n \to \infty} x_{n-1}+k}$$

$$\ell = \sqrt{\ell+k}$$

$$\ell^2-\ell -k = 0$$

Then either

$$\ell_1 = \frac{1+\sqrt{1+4k}}{2}$$

or

$$\ell_2 = \frac{1-\sqrt{1+4k}}{2}$$

But the latter is impossible since $\ell_2 <0$. It follows that

$$\ell_1 = r$$ the positive root of the equation $x^2-x-k=0$. $\blacktriangle$

Your problem is the special case $k=2$, which yields

$$\ell = \frac{1+\sqrt{1+4\cdot 8 }}{2}=2$$

-