4
$\begingroup$

For $0 the limit $\lim\limits_{n\rightarrow \infty}\sqrt{1-a_n}= \frac{\sqrt{5}-1}{2}$ for the sequence $a_{n+1}=\sqrt{1-a_n}$.

But the problem is that the choice of $a_0$ does not matter.

The question is why?

  • 0
    +1: interesting question; usually convergence of such sequences is determined by Contraction Mapping Theorem, but for your case the mapping is not contractive on $(0,1)$.2011-12-09

2 Answers 2

4

Since one iterates the function $v:x\mapsto\sqrt{1-x}$ which is not contractive, an idea is to use monotonicity instead of contraction, hence to consider a power of $v$ instead of $v$.

Consider $u=v\circ v$, hence $u(x)=\sqrt{1-\sqrt{1-x}}$ for every $x$ in $[0,1]$. Then $a_{n+2}=u(a_n)$ for every $n\geqslant0$, hence the two sequences $(b_n)$ and $(c_n)$ defined by $b_n=a_{2n}$ and $c_n=a_{2n+1}$ are both such that $b_{n+1}=u(b_n)$ and $c_{n+1}=u(c_n)$.

Note that $u([0,1])=[0,1]$, $u(0)=0$, $u(1)=1$, $u(z)=z$ for $z=\frac12(\sqrt5-1)$, $u$ is increasing on $[0,1]$, $u(x)>x$ if $0 and $u(x) if $z.

Thus, any sequence $(x_n)$ defined by $x_{n+1}=u(x_n)$ and $x_0$ in $[0,1]$ has the following behaviour.

  • If $x_0=0$ or $x_0=z$ or $x_0=1$, $(x_n)$ is constant, that is $x_n=x_0$ for every $n\geqslant0$.
  • If $0, $(x_n)$ is increasing, $0 for every $n\geqslant0$ and $x_n\to z$ when $n\to\infty$.
  • If $z, $(x_n)$ is decreasing, $z for every $n\geqslant0$ and $x_n\to z$ when $n\to\infty$.

One sees that, for every $x_0$ in $(0,1)$, $x_n\to z$. Applying this to $(b_n)$ and to $(c_n)$, which start from $b_0=a_0$ and $c_0=a_1=\sqrt{1-a_0}$ respectively, and noting that $a_1$ is in $(0,1)$ for every $a_0$ in $(0,1)$, one sees that, for every $a_0$ in $(0,1)$, both $b_n\to z$ and $c_n\to z$, hence $a_n\to z$ when $n\to\infty$.

  • 0
    How do you conclude that, for example, that because intreating u(x) produces an increasing sequence on (0,z), that the sequence must converge to z?2011-12-09
  • 0
    @Potato: by the usual argument. Choose $x_0$ in $(0,z)$ for example. Then $(x_n)$ is increasing and bounded by $z$, hence $(x_n)$ converges to $\ell$ with $0\lt\ell\leqslant z$. Since $x_{n+1}=u(x_n)$ and $u$ is continuous, $\ell=u(\ell)$, hence $\ell=z$.2011-12-10
  • 0
    thanks @DidierPiau for your answer, i will study contractive functions.2011-12-14
2

We are considering a question equivalent to $f(x) = \sqrt{1 - x}$ for $x \in (0,1)$. It is not so hard to show that this function has a fixed point, and exactly one fixed point in the interval $(0,1)$. (In fact, this fixed point is our limit).

In your question, you seem to know that the limit exists and are able to calculate it (take the even and odd terms separately, for example). This means that you know that no matter what starting value, the iterative function $f(x)$ will converge. But there is only one fixed point in the interval of its range, and thus it must converge to that point.

This is the same reasoning that goes to show that $\cos(x) = x$, or rather $x_{n+1} = \cos(x_n)$, will always have the same limit regardless of starting point, more or less. One shows a limit exists, and then the limit must be the fixed point (for cosine, this number has a name, the Dottie Number).

  • 1
    Not sure I follow every step in your post about $f:x\mapsto\sqrt{1-x}$. For example I wonder why *there is only one fixed point in the interval of its range, and thus it must converge to that point*. One could write similar things about the function $g:x\mapsto2x^2-x^4$, namely that *It is not so hard to show that this function has a fixed point, and exactly one fixed point in the interval $(0,1)$*, although the behaviour of $(b_n)$ defined by $b_{n+1}=g(b_n)$ is quite different from the behaviour of $(a_n)$ defined by $a_{n+1}=f(a_n)$.2011-12-10
  • 0
    @Didier: I also mention the importance of knowing that it converges. The idea is that if you have an iterative function that takes a certain range (here, $f(x)$ takes only values in $(0,1)$), we know that it converges, and we know that the iterative function has exactly one fixed point in that range, then it must converge to that fixed point. But we need all three parts, not just that there exists a fixed point. Unless I am missing something?2011-12-10
  • 0
    In the example of my last comment, the sequence $(b_n)$ converges for EVERY starting point $b_0$, and $g$ has exactly one fixed point $z$ in $(0,1)$, but (unless $b_0=z$) $(b_n)$ DOES NOT converge to $z$.2011-12-10