Proof by induction when the first element is defined in an interval Given that, for a sequence $x_n$:


*

*$1<x_1<2$

*$x_{n+1} = 1 + x_n - \frac{1}{2}(x_n)^2$ for $n \ge 2$
Prove that, for $n\ge3$, $|x_n - \sqrt2| < \frac{1}{2^n}$

So, at first I tried to verify the base case by first calculating $x_2$.
Thus, I got $|x_2 - \frac{3}{2}| < \frac{1}{2}$
But surprisingly, for $x_3$:
$\frac{1}{2} < |x_3 - \frac{3}{2}| < 2$
I wonder where does that $\sqrt2$ comes from.

Later, while working on the induction step, I've found that
$x_{k+2} = 2 - \frac{1}{2}x_{k+1}$
It seems that I'm stuck on this problem but close to the actual proof.
Could you guys give me any elucidation?

This problem can be solved by letting $a_n = x_n - \sqrt 2$. Rewriting the condition, we obtain $a_{n+1} + \sqrt 2 = 1 + a_n + \sqrt 2 - \frac{1}{2}(a_n + \sqrt 2)^2$, and expanding and rearranging gives $a_{n+1} = (1-\sqrt 2)a_n - \frac{1}{2} a_n^2 = (1- \sqrt 2 - \frac{a_n}{2})a_n$. 
Now if $|a_n| < 3 - 2 \sqrt 2$, we have $1- \sqrt 2 - \frac{a_n}{2}> 1 - \sqrt 2 - \frac{3}{2} + \sqrt 2= \frac{-1}{2}$. Similarly, we have $1- \sqrt 2 - \frac{a_n}{2} < 1 - \sqrt 2 + \frac{3}{2} - \sqrt 2 = \frac{5}{2} - 2 \sqrt 2 < 0$.
So now, using $a_{n+1} = (1- \sqrt 2 - \frac{a_n}{2})a_n$, we get that $|a_{n+1}| < \frac{1}{2} |a_n|$. Note that as soon as $|a_n| < 3 - 2 \sqrt 2$ holds for some $n$, it holds for all later $n$ as the absolute value is at least halved each time. So now all that remains is to prove the base case $a_3$; this is a fairly straightforward computation.
