Prove that $s_{n+1}=s_n+\frac{1}{2}(x-s_n^2)$ converges if $0<x<1$.

Question

Here is the question.

If $s_1=0$, prove that $s_{n+1}=s_n+\frac{1}{2}(x-s_n^2)$ is monotone and converges if $0<x<1$.

I tried this question by induction, but I can't seem to find the appropriate bounds for my induction step.

This is something I tried.

Claim: $\forall n \geq 2$, one has $\frac{\sqrt x}{2} \leq s_n < \sqrt x$. For $s_2$, this is clearly true, since $s_2 = \frac{x}2 < \frac{\sqrt x}2 $. And between $0<x<1$, $\frac x 2 < \sqrt x$.

Assume $\frac{\sqrt x}{2} \leq s_n < \sqrt x$ is true for $n$, then to show: $\frac{\sqrt x}{2} \leq s_{n+1} < \sqrt x$.

\begin{align} s_{n+1}&=s_n+ \frac{1}{2}(x-s_n^2) \\ &= s_n + \frac{1}{2}x - \frac{1}{2}s_n^2 \\ &\leq \sqrt x + \frac{1}{2} x - \frac{1}{2}\left(\frac{x}{4}\right)\\ &=\sqrt x +\frac{3x}{8} \end{align} which still can't be bounded by $\sqrt x$. I've also tried different bounds, but none of them seem to work. Could someone give me a hint or another way to approach the problem?

Answer 1

Note that $$s_{n+1}={x+1-(1-s_n)^2\over 2}$$if $s_n<\sqrt x$, then $$1-s_n>1-\sqrt x>0\\(1-s_n)^2>(1-\sqrt x)^2>0\\-(1-s_n)^2<-(1-\sqrt x)^2\\{x+1-(1-s_n)^2\over 2}<{x+1-(1-\sqrt x)^2\over 2}=\sqrt x$$therefore $$s_{n+1}<\sqrt x$$

Answer 2

You may also proceed as follows considering the function

• $f(t) = t+\frac{1}{2}(x-t^2)$
• $f'(t) = 1-t \Rightarrow f(t)$ is strictly increasing on $[0,1]$
• $f(0) = \frac x2 \stackrel{x>0}{>}0$
• $f(1) = 1+\frac 12(x-1)=\frac{1+x}2 \stackrel{x<1}{<} 1$
• $\stackrel{0<x<1}{\Rightarrow} f\left([0,1]\right)=[\frac x2, \frac{1+x}2] \subset [0,1]$

Let $f^n$ denote the $n$-fold composition of $f$ with itself, then we have

• $s_n = f^n(s_0) = f^n(0) \leq \frac{1+x}2 < 1$, so $s_n$ is bounded from above
• $s_0 =0 < \frac x2 = s_1 \stackrel{induction}{\Longrightarrow}s_n =f^n(s_0) < f^n(s_1) =f^{n+1}(s_0) = s_{n+1}$

So, we have for $0<x<1$ an increasing sequence which is bounded from above and, hence, is convergent.