# Thread: Proof of Convergence for Recursive Sequence

1. ## Proof of Convergence for Recursive Sequence

I am trying to figure out how to prove that the following sequence converges:

$\displaystyle a_{n+1}=\sqrt{2+\sqrt{a_{n}}}$

with $\displaystyle a_{1}=\sqrt{2}$

Thoughts anyone?

2. Originally Posted by General
Since the sequence converges, then $\displaystyle \lim_{n\to\infty} a_n = L$ , where L is a finite number ..

Recall that, for the convergent sequence $\displaystyle a_n$:
$\displaystyle \lim_{n\to\infty} a_n=\lim_{n\to\infty} a_{n+1}$ ..

Since : $\displaystyle a_{n+1}=\sqrt{2+\sqrt{a_{n}}}$

By taking the limit of both sides, we will conclude the following equation :

$\displaystyle L=\sqrt{2+\sqrt{L}}$ , solve it for L ..

Thanks for the quick replies. I believe that in a formal proof

$\displaystyle L=\sqrt{2+\sqrt{L}}$

can be used to solve for the limit L if we know that the series converges. However, I need to first prove that the series converges given

$\displaystyle a_{1}=\sqrt{2}$

3. I think we should say this :

$\displaystyle |a_{n+1} - L|<\epsilon$

and $\displaystyle -\epsilon < a_{n+1} - L < \epsilon$

it means :

$\displaystyle 0 < a_{n+1} - L < 2\epsilon$

and $\displaystyle a_{n+1} < 2\epsilon+L$

also if $\displaystyle 2\epsilon<<L$ we can unspot $\displaystyle 2\epsilon$ .
and $\displaystyle a_{n+1} < L$

this is the proof. but to complete it

we should proof that $\displaystyle 2\epsilon<<L$ . or

$\displaystyle \epsilon<<\frac{L}{2}$

We Know L is 1 as here :

$\displaystyle \lim_{n\rightarrow\infty}\sqrt{\frac{2}{a_{n}} +1} = 1$

so the $\displaystyle \epsilon<<0.5$

4. Originally Posted by moemoe
However, I need to first prove that the series converges given
Show that the sequence is increasing and bounded.
Use induction to do that.

5. Originally Posted by parkhid
I think we should say this :

$\displaystyle |a_{n+1} - L|<\epsilon$
...
You can't assume convergence if you're trying to prove it...

@moemoe: The usual way to prove that this type of recursive sequences converge is to prove by induction that the sequence is monotone and bounded.

In your case, plug in the values for the first few terms to see whether the sequence is increasing or decreasing, and then prove it by induction. After you do that, prove that it is bounded (this can be done by induction as well).

EDIT: Plato ahead of me :<

6. So assuming

$\displaystyle a_{n} \geq a_{n-1} \geq 0$

we have

$\displaystyle a_{n+1} = \sqrt{2+\sqrt{a_{n}}} \geq \sqrt{2+\sqrt{a_{n-1}}}= a_{n}$

Does anyone have a slick way of showing the sequence is bounded?

7. Maybe define a new sequence

$\displaystyle b_{n+1}=\sqrt{2+\sqrt{b_{n}}}$ with $\displaystyle b_{1}=2$

where $\displaystyle a_{n} \leq b_{n}$ for each $\displaystyle n$ and $\displaystyle b_{n}$ is decreasing by the same induction argument above?

Is there another simpler way?

8. There is a simpler way.

First, validate that $\displaystyle a_1, a_2 < 2$.

Now, assume $\displaystyle a_n < 2$ and use the induction hypothesis to prove that $\displaystyle a_{n+1} < 2$.
This will prove that the sequence is bounded by 2 (it doesn't mean that 2 is the limit, though..)

9. Perhaps we can try this.

By the induction step it can be shown that $\displaystyle a_{n}<2$

$\displaystyle a_{n+1}=\sqrt{2+\sqrt{a_{n}}}$

$\displaystyle (a_{n+1})^{2}=2+\sqrt{a_{n}}$

$\displaystyle (a_{n+1})^{2}-1=1+\sqrt{a_{n}}$

$\displaystyle (a_{n+1}+1)(a_{n+1}-1)=1+\sqrt{a_{n}}$

Since for all n, $\displaystyle a_{n}<2$

$\displaystyle a_{n+1}-1<1$

$\displaystyle a_{n+1}+1>a_{n}+1$

$\displaystyle a_{n+1}>a_{n}$

and it is monotone increasing.

10. The sequence is defined recursively as...

$\displaystyle \Delta_{n} = a_{n+1} - a_{n} = \sqrt{2 + \sqrt{a_{n}}} - a_{n} = f(a_{n})$ (1)

The function $\displaystyle f(x)= \sqrt{2 + \sqrt{x}} - x$ is represented here...

It has a single zero at $\displaystyle x_{0} = 1.83117720721...$ and because $\displaystyle |f(x)|$ is less that the line crossing the x axis in $\displaystyle x=x_{0}$ with unity negative slope, any $\displaystyle a_{0} \ge 0$ will produce a sequence converging at $\displaystyle x_{0}$ without oscillations...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

,

,

### how to use induction to find that a recursive sequence is bounded

Click on a term to search for related topics.