I have to solve this exercise but I'm having issues with it. Here is the question :
Suppose that $R>0$, and let us define the sequence $x_0 > 0$, and
$$x_{n+1} = \frac{1}{2} \left( \frac{R}{x_n} + x_n \right) $$
Prove that, for any $n\geq 1$,
$$x_n > x_{n+1} > \sqrt{R}$$
and
$$ x_n - \sqrt{R} \leq \frac{1}{2^n} \frac{(x_0 - \sqrt{R})^2}{x_0}$$
I tried to prove it by recurrence, but I usually get lost in computations.
Thanks in advance !
Here, you have an example of a sequence that is defined as $x_{n+1} = f(x_n)$. So you can start by studying $f$.
First, $f$ has a unique fixed point on $(0, + \infty)$ which is $\sqrt{R}$. Then, $f(x) \geq \sqrt{R}$ on $(0, \sqrt{R}]$, and $\sqrt{R} < f(x) < x$ on $( \sqrt{R}, +\infty)$. This directly tells you that no matter the value of $x_0$, you will always have $x_1 \geq \sqrt{R}$ and that the sequence $(x_i)_{i \geq 1}$ is non-increasing (notice that we excluded $x_0$). Hence, $(x_i)_{i \geq 1}$ is a non-increasing sequence that is lower-bounded (by $\sqrt{R}$), and so it converges. Since $f$ is continuous, its limit is necessarily a fixed point of $f$, and since $\sqrt{R}$ is the only one, $(x_i)_{i \geq 0}$ converges to $\sqrt{K}$. Thus, it makes sense to look at the sequence $(x_i - \sqrt{R})_{i \geq 0}$ in order to characterize the convergence speed.
For any $n \geq 0$ you have that $$x_{n+1} - \sqrt{R} = f(x_n) - f( \sqrt{R}) = \frac{1}{2} \left(R \left(\frac{1}{x_n} - \frac{1}{\sqrt{R}}\right) + x_n - \sqrt{R}\right)$$
and so, when $n \geq 1$, $$x_{n+1} - \sqrt{R} \leq \frac{x_n - \sqrt{R}}{2}$$
because $\frac{1}{x_n} - \frac{1}{\sqrt{R}} \leq 0$.
Now, you're only left to show that $x_{1} - \sqrt{R} \leq \frac{(x_{0} - \sqrt{R})^2}{2x_0}$, which is a direct calculus in the second to last equation that we wrote.
Now a direct recurrence concludes your exercise (we've already written the equations for the initialization and for the heredity).
Note : As pointed out by @D S, there is a typo in the exercise and one of the strict inequalities has to be large. Indeed taking $x_0 = \sqrt{R}$ does not respect strict monotony. Alternatively, imposing $x_0 \neq \sqrt{R}$ solves this issue.