# Prove a recursive sequence converges

Let $$\{a_n\}_{n=0}^∞$$ be a sequence defined recursively as follows:

$$\left\{\begin{array}{l}a_0=\sqrt2\\a_n=\sqrt{2a_{n-1}},n\geq1\end{array}\right.$$

Show that $$\{a_n\}_{n=0}^∞$$ converges and that its limit is $$2$$.

Hint: It may be helpful to first prove that for all $$x ∈ (0, 2)$$, we have $$x < \sqrt{2x} < 2$$.

What I tried so far:

I proved the hint first

WTS $$\forall x\in(0,2), x<\sqrt{2x}<2$$

$$\Leftrightarrow \forall x,0

Assume the negation:

$$\not\Leftrightarrow \exists x,0

$$\Leftrightarrow \exists x,(0

Case1: $$\exists x,0

Let $$x$$ be such $$x$$

Since $$0

Have $$0<\sqrt{2x}$$

That $$0<\sqrt{2x}\leq x$$

$$\Rightarrow 0<2x

$$\Rightarrow 0<2\leq x$$ Contradiction

Case2: $$\exists x,0

Let x be such x

Have $$0

$$\Rightarrow 0

$$\Rightarrow 0

But $$0

Implies $$4x<8$$

$$\Rightarrow 4<\frac{8}{x}$$

$$\Rightarrow \frac{4}{2}<\frac{4}{x}$$

$$\Rightarrow 2<\frac{4}{x}$$ Contradiction

Therefore $$\forall x\in(0,2), x<\sqrt{2x}<2$$ hold by contradiction.

Then prove $$\forall n \in \mathbb{N},0 by induction:

Base case: $$n=0$$ $$0<\sqrt2<2 \text{ hold}$$

Inductive steps:

Assumse $$0

Show $$0

By assumption $$0

Have $$\sqrt{2(0)}<\sqrt{2(a_k)}=\sqrt{2(\sqrt{2a_{k-1}})}<\sqrt{2(2)}$$

That $$0

Therefore $$\forall n \in \mathbb{N},0

Since $$0, that $$x<\sqrt{2x}<2$$ hold for $$a_{n - 1}$$ implies: $$0 < a_{n - 1} < \sqrt{2a_{n-1}} = a_n < 2,$$ Therefore $$a_n$$ is increasing and bounded above, implies: $$\exists L\in \mathbb{R},\{a_n\}_{n=0}^∞=L$$

By given also have $$a_n = \sqrt{2a_{n-1}}$$ Take the limit on both sides we have: $$L = \sqrt{2L} \rightarrow L = 2.$$ Therefore $$\{a_n\}_{n=0}^∞=2$$

• show $a_n \le a_{n+1}$ and $a_n \le 2$ by induction. Then there must be a limit of $(a_n)_n$, call it $L$. $L$ must satisfy $L = \sqrt{2L}$, so $L=2$. Jul 28, 2019 at 1:30

First, I just want to say, your proof of the hint is indeed correct, but it's... it's so inelegant. What you have here is the fact that the geometric mean of $$x$$ and $$2$$ lies between $$x$$ and $$2$$. This can be proven, more directly.

Since $$0 < x < 2$$, we have $$0 < \sqrt{x} < \sqrt{2}$$ since the square root function is strictly increasing. Then, multiplying through by $$\sqrt{x} > 0$$, $$0 < x < \sqrt{2x}.$$ Now, multiplying through by $$\sqrt{2} > 0$$, $$0 < \sqrt{2x} < 2.$$ In total, $$0 < x < \sqrt{2x} < 2.$$

How does this help? Well, taking $$x = a_{n - 1}$$ implies $$0 < a_{n - 1} < \sqrt{2a_{n-1}} = a_n < 2,$$ implying both that $$a_n$$ is increasing, and bounded above. Thus, a limit $$L$$ exists. If we take the recurrence relation $$a_n = \sqrt{2a_{n-1}}$$ and take the limit of both sides, then $$L = \sqrt{2L} \implies L = 2.$$ The limit must therefore be $$2$$.

First we show that the sequence is increasing and bounded above, so it does converge.

Then we show that the limit is in fact $$2$$.

We know that $$a_0 = \sqrt 2 <2$$ and if $$a_{n-1}<2$$ then $$a_n= \sqrt {2a_{n-1}}<\sqrt {2\times 2} =2$$

In order to show that the sequence is increasing , we have $$\sqrt {2a_{n-1}}>a_{n-1} \iff$$

$$2a_{n-1}>a_{n-1}^2 \iff a_{n-1} (2-a_{n-1})>0$$

Since $$0 the above inequality holds therefore the sequence is increasing .

Now that we know the sequence converges to a real number $$l$$ we take limit of $$a_n=\sqrt {2a_{n-1}}$$ to get $$l=\sqrt {2l}$$ or $$l^2=2l$$ which gives us $$l=0$$ or $$l=2$$

The acceptable limit is $$l=2$$ since the sequence is increasing and starts at $$\sqrt 2$$

• why did you switch from "can show" to "show" in the first sentence? Jul 28, 2019 at 3:12
• See if you like the edit. Jul 28, 2019 at 3:16

For the hint, suppose that $$0, then to the inequality $$x<2$$ we multiply it by $$x$$ (which is positive) and we get $$x^2<2x$$, that is, $$x<\sqrt{2x}$$. And similarly we obtain $$\sqrt{2x}<2$$ (multiply the inequality $$x<2$$ by two). Thus $$x<\sqrt{2x}<2$$ Now, if we know that a sequence is convergent if and only if it is bounded and non-decreasing, it follows from the hint (set $$x=a_{n-1}$$) that $$a_{n-1} (it is non-decreasing) and that $$a_n<2$$ for all $$n\in \mathbb N$$ (the sequence is bounded by $$2$$).

Finally, to prove that the limit is in fact $$2$$ just note that, since the sequence is convergent, let's say it converges to $$\ell$$. And observe this (after "take the limit" in the recursive formula) : $$\ell =\sqrt{2 \ell}$$ $$\ell (\ell -2)=0$$ and clearly, $$\ell$$ cannot be equal to $$0$$ (why?). Therefore $$\lim_{n\to \infty} a_n =2$$

$$a_0 = \sqrt 2=2 ^ {1/2}$$ $$a_1=\sqrt {2\sqrt2} =2 ^{(1/2)+(1/2)^2}$$ $$...$$ $$a_n = 2 ^{(1/2)+(1/2)^2+...+(1/2)^{n+1}} = 2^{\frac{(1/2)^{n+2}-(1/2)}{(1/2)-1}}=2^{1-(1/2)^{n+1}}$$ $$lim_{n\rightarrow\infty}a_n=lim_{n\rightarrow\infty}2^{1-(1/2)^{n+1}}=2$$