Explore for convergence the following recurrence: $x_{n+1} = (1-x_n)^2, x_1 = {1\over 2}, n\in\Bbb N$

Question

Explore for convergence the following recurrence: $$ x_{n+1} = (1-x_n)^2\\ x_1 = {1\over 2}\\ n\in\Bbb N $$

To show a sequence is convergent it suffices to show it is bounded and monotonic. Obviously the the sequence is bounded by $1$ and $0$: $$ 0 \le x_n \le 1 $$

Check whether the sequence is monotonic: $$ {1\over 2} = x_1 > x_2 = {1\over 4} $$

Put $P(n): x_n > x_{n+1}\forall n\in\Bbb N$. $P(1)$ is true. Assume $P(n)$ is true. Then: $$ x_{n+1} < x_n\\ -x_{n+1} > -x_n \\ 1 - x_{n+1} > 1 - x_n \\ (1 - x_{n+1})^2 > (1 - x_n)^2 \\ x_{n+2} > x_{n+1} $$

showing the induction hypotheses doesn't hold. However if we put it the following way: $$ x_{n+1} < x_n \\ x_{k+1} - 1 < x_n - 1 \\ (x_{k+1} - 1)^2 < (x_n - 1)^2 \\ (1 - x_{k+1})^2 < (1 - x_n)^2 \\ x_{n+2} < x_{n+1} $$

which completes the induction.

Clearly that is impossible. I believe the mistake is in the squaring step. Apparently there is a veil before my eyes preventing me from spotting it. What went wrong with the two cases?

Answer 1

You can not do $x_{n+1} - 1 < x_n - 1 \\ \implies (x_{n+1} - 1)^2 < (x_n - 1)^2 $

because both LHS and RHS of inequalities is negative.

For eg. $-1 > -2$ but $1^2 < 2^2$

Answer 2

If you look at the sequences $\newcommand{\N}{\mathbb{N}}(a_n)_{n\in\N} :=(x_{2n})_{n\in\N}$ and $(b_n)_{n\in\N}:=(x_{2n-1})_{n\in\N}$ then you can show that both of them will converge to different limits. We start with using the recursion twice $$ x_{n+2} = (1-x_{n+1})^2 = (1-(1-x_n)^2)^2 = \dots = x_n^4 - 4x_n^3 + 4x_n^2 $$ We define the polynomial function $p(x) := x^4 - 4x^3 + 4x^2$. some curve sketching yields that this function is monoton increasing for $x\in (0,1)$. The recursion for $a_n$ and $b_n$ is given by $$ a_{n+1} = a_n^4 - 4a_n^3 + 4a_n^2, \quad a_1 = \frac{1}{4} \\ b_{n+1} = b_n^4 - 4b_n^3 + 4b_n^2, \quad b_1 = \frac{1}{2} $$ As you already said $0<x_n<1$. Clearly, this is also true for $a_n$ and $b_n$. It is straight forward to check that $b_2 > b_1$. Hence, $(b_n)_{n\in\N}$ is convergent. To evaluate the limit point you have to solve $x = p(x)$. It is easy to see that $0$ and $1$ are solutions. By polynomial division you can find the other solution by solving a quadratic equation. You will realize that only the solution $1$ can be the limit of $(b_n)_{n\in\N}$.

Since $a_n = (1-b_n)^2$, the limit of $(a_n)_{n\in\N}$ is $0$. Therefore, $(x_n)_{n\in \N}$ cannot converge.

Answer 3

Just to have a complete answer, from $x_{n+1}=f(x_n)$, where $f(x)=(1-x)^2$, we have $f'(x)=-2(1-x)$. Or $f(x)$ is descending on $[0,1]$. Sequence is bounded indeed $0\leq x_n \leq 1$, can be show using induction. Let's compute a few values $$x_1=\frac{1}{2} > x_2=\frac{1}{4} > x_4=\frac{49}{256}$$ $$x_1=\frac{1}{2}< x_3=\frac{9}{16} < x_5=\frac{42849}{65536}$$ and because the function $f(x)$ is descending $$f(x_2)\leq f(x_4) \iff x_3 \leq x_5 \\ f(x_3) \geq f(x_5) \iff x_4 \geq x_6 \\ f(x_4) \leq f(x_6) \iff x_5 \leq x_7 \\ ...$$ By induction, we have $$x_1>x_2>x_4\geq x_6 \geq ... \geq x_{2k} \geq ...$$ $$x_1<x_3<x_5\leq x_7 \leq ... \leq x_{2k+1} \leq ...$$ i.e. we have a decreasing subsequence $\left(x_{2k}\right)_{k\in\mathbb{N}}$ and increasing one $\left(x_{2k+1}\right)_{k\in\mathbb{N}}$ both bounded, so both these subsequences have limits $$\frac{1}{4}=x_2 \geq \lim\limits_{k\rightarrow\infty}x_{2k}$$ $$\frac{9}{16}=x_3 \leq \lim\limits_{k\rightarrow\infty}x_{2k+1}$$ and these limits are different. As a result, the original sequence is diverging.