Waste less time on Facebook — follow Brilliant.

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
9 months, 3 weeks ago

No vote yet
1 vote


Sort by:

Top Newest

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\). Prasun Biswas · 9 months, 1 week ago

Log in to reply

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. Efren Medallo · 9 months, 2 weeks ago

Log in to reply

@Efren Medallo 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. Oli Hohman · 9 months, 2 weeks ago

Log in to reply

@Oli Hohman 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. Efren Medallo · 9 months, 2 weeks ago

Log in to reply

@Efren Medallo 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. Prasun Biswas · 9 months, 2 weeks ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...