convergence of a recursive sequence with parameter a How can you determine if the following recursive sequence converges:
$$x_{n+1}=\frac{1}{2}(a+x_n^2)$$
where $0\le a \le 1$ and $x_1=0$
I know that the limit x (if it exists) satisfies the following equation:
$$x=\frac{1}{2}(a+x^2)$$ 
since $\lim_{x\rightarrow \infty} x_n = \lim_{x\rightarrow \infty} x_{n+1}$. Therefore $x=1\pm \sqrt{1-a}$ 
Thank you in advance :)
 A: By induction we can show that $0\leq x_n<1$.
Now, for $a=1$ we obtain $$x_{n+1}-x_n=\frac{1}{2}(x_n-1)^2\geq0$$ and the rest is smooth.
But for $a<1$ we obtain $0<r=\frac{2-\sqrt{1-a}}{2}<1$ and  $$|x_{n+1}-1+\sqrt{1-a}|=\left|\frac{1}{2}x_n^2+\frac{1}{2}a-1+\sqrt{1-a}\right|=$$
$$=\frac{1}{2}\left|x_n^2-\left(1-\sqrt{1-a}\right)^2\right|=\frac{1}{2}\left|x_n-1+\sqrt{1-a}\right|\cdot\left|x_n+1-\sqrt{1-a}\right|\leq$$
$$\leq r\left|x_n-1+\sqrt{1-a}\right|\leq...\leq r^n\left|x_1-1+\sqrt{1-a}\right|\rightarrow0.$$
A: That is a really useful obervation. Notice that by induction you can easily prove that $x_n\le 1$ which means that the option $1+\sqrt{1-a}$ is definitely not the limit for $a<1$, since then it's strictly greater than 1. If $a=1$ then $1+\sqrt{1-a}=1-\sqrt{1-a}$. That means that if the limit exists, it's equal to $1-\sqrt{1-a}$. 
Now, the case for $a=0$ is obvious since then $x_n=0$ for all $n$ so we will assume $a>1$. Notice that if we prove that the sequence is bounded from above and increasing, we will get convergence and from the above argument the limit. We can show inductively that the sequence is bounded from above by $1-\sqrt{1-a}$. The base case $x_0<1-\sqrt{1-a}$ is obviously fulfilled. Now if $x_k<1-\sqrt{1-a}$, then
$x_{k+1}=\frac{1}{2}(a+x_k^2)<\frac{1}{2}(a+(1-\sqrt{1-a})^2)=\frac{1}{2}(a+1-2\sqrt{1-a}+1-a)=1-\sqrt{1-a}$.
That complete the induction. Now to prove the sequence is increasing, you can notice that $x_n<\frac{1}{2}(a+x_n^2)$ for all $0\le x_n<1-\sqrt{1-a}$ (it's a quadratic in $x$) which means $x_{n+1}=\frac{1}{2}(a+x_n^2)>x_n$. That completes the proof that the seqence $(x_n)$ is convergent. As we stated earlier, convergence implies that the limit is $1+\sqrt{1-a}$, which means we're done.
