Convergence Proof

Say that you have a recurring sequence such that: $a_{0} = 1/2$
$a_{n+1} = \sqrt{1-a_n}$

How do you prove that this sequence converges, given that it does. If it doesn't, how do you prove it diverges?

Note by Oli Hohman
1 year, 11 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

One possible way to show the convergence is to consider the two subsequences $$\{a_{2n}\}_{n\geq 0}$$ and $$\{a_{2n+1}\}_{n\geq 0}$$ and show that they are monotone and bounded. The first subsequence is monotonically increasing and strictly bounded above by $$1$$ and below by $$1/2$$ and the second subsequence is monotonically decreasing and strictly bounded below by $$0$$ and above by $$\sqrt{1/2}$$. Since monotone bounded sequences have a finite limit, denote the limits of the two subsequences by $$l_1$$ and $$l_2$$ respectively. Then, both $$l_1$$ and $$l_2$$ are solutions of the equation below:

$k=\sqrt{1-\sqrt{1-k}}\implies k^2=1-\sqrt{1-k}\implies (k^2-1)^2=1-k\implies (k-1)(k^2+k-1)=0$

Now, to show that the sequence $$\{a_n\}_{n\geq 0}$$ is convergent, we need to show that $$l_1=l_2$$, i.e., we need to show that there exists a unique real root $$k_0$$ of the above equation such that $$1/2\leq k_0\leq\sqrt{1/2}$$. Solving the equation shows that there does exist a unique real root $$k_0$$ which is equal to $$1/\phi$$ and hence the sequence $$\{a_n\}_{n\geq 0}$$ is convergent with the limit being $$1/\phi$$.

Another way to show the convergence would be to show that the map $$x\mapsto\sqrt{1-x}$$ is a contraction mapping in the metric space $$[0,1]$$ with the usual absolute value metric and then invoke the Banach fixed point theorem to show that the sequence $$\{a_n\}_{n\geq 0}$$ is convergent with the limit being the fixed point of the mentioned contraction mapping, which is $$1/\phi$$.

- 1 year, 11 months ago

Let's see.

Supposing we start off with a number $$a_0$$.

$$a_1 = \sqrt{ 1 - a_0}$$

$$a_2 = \sqrt {1 - a_1 }$$

$$a_2 = \sqrt { 1 - \sqrt{1 - a_0} }$$

$$a_3 = \sqrt { 1 - a_2}$$

$$a_3 = \sqrt { 1 - \sqrt{1 - a_1 }}$$

$$a_3 = \sqrt { 1 - \sqrt{1 - \sqrt{1- a_0}}}$$

As you can notice, $$a_n$$ seemingly becomes a nested radical starting from $$a_0$$..

If we extend this toward infinity, we will know if $$a_n$$ approaches a specific value.

$$a_n = \sqrt{1 - \sqrt{ 1 - \sqrt { 1 - \sqrt { 1 - \sqrt{...}}}}}$$

We can condense this into

$$a_n = \sqrt { 1 - a_n }$$

$$a_n^2 + a_n - 1 = 0$$

We are now left with an equation in terms of $$a_n$$, which surprisingly means that no matter what $$a_0$$ we begin with, it reaches this value of $$a_n$$.

Coincidentally, this $$a_n$$, when solved, gives the reciprocal of the golden ratio $$\frac {-1 + \sqrt{5}}{2}$$. Well the other value is discarded as it is extraneous.

- 1 year, 11 months ago

Very elegant solution. That's the exact process I used to get the solution, given that it does converge. I just wonder if this is enough to prove that the sequence certainly does converge.

- 1 year, 11 months ago

I think since it was assumed that $$lim_{n \to \infty} a_n = y$$, so we reached for a particular value of $$y$$, which verifies that indeed the limit exists.

- 1 year, 11 months ago

No, that's not a sufficient condition. Consider the following counter-example of a sequence $$\{a_n\}_{n\geq 0}$$ defined by $$a_{n+1}=2a_n~\forall~n\geq 0$$ and the base case $$a_0=1$$

If we assume that the sequence converges, i.e., assume that $$\lim\limits_{n\to\infty} a_n=y$$ exists and is finite, then we get using the recurrence relation that $$y=2y\implies y=0$$ which is finite. But the sequence is actually $$a_n=2^n~\forall~n\geq 0$$ which is divergent.

- 1 year, 11 months ago