Explore for convergence the following recurrence: $x_{n+1} = (1-x_n)^2, x_1 = {1\over 2}, n\in\Bbb N$ 
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?
 A: 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$
A: 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.
A: 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.
