Proof that the following sequence converges to $\sqrt{2}$ I am trying to prove that that $\lim_{i \to \infty} x_i = \sqrt{2}$ where $x_0 = 1$ and $x_{i+1} = 1 + \frac{1}{1 + x_i}$.
It's easy to show that if there is a limit $x^*$ that it must be equal to $\sqrt{2}$ since $$x^* = 1 + \frac{1}{1 + x^*}$$ implies $x^* = \pm \sqrt{2}$. And the sequence is strictly positive which rules out $-\sqrt{2}$.
However, while I am able to show what the limit must be if it exists, I am not able to prove that the sequence actually does converge to a limit.
Some things I know about the sequence are:


*

*It's bounded between 1 and 3/2 and its elements oscillate above and below the $\sqrt{2}$ limit.

*The even elements of the sequence appear to be monotonically increasing while the odd elements appear to be monotonically decreasing. Therefore the even and odd sequences must both converge (though not necessarily to the same limit) since they are bounded above/below, respectively.


Any tips for how to prove convergence is appreciated.
 A: HINT:
$$\frac{x_{n+1} - \sqrt{2}}{x_n -\sqrt{2}}= \frac{1-\sqrt{2}}{1+x_n}$$
Or, for $y_n= x_n -1$, the recurrence $y_0 = 0$ and $y_{n+1} = \frac{1}{2 + y_n}$, so $y_n$ is the sequence of partial quotients of the number 
$[0;2,2,2,\ldots] = \sqrt{2}-1$.
A: One approach is to show that each successive iterate is closer to $\sqrt 2$ than the previous one by a factor that is less than and bounded away from $1$.  Write $x_i=\sqrt 2 + \epsilon$, where we assume $\epsilon$ is small enough.  Then
$$\begin {align} x_{i+1}&=1+\frac 1{1+\sqrt 2 + \epsilon}\\
&=1+\frac{\sqrt 2-1}{1+\epsilon(\sqrt 2-1)}\\
&\approx1+(\sqrt 2-1)(1-\epsilon(\sqrt 2-1))\\
&\approx\sqrt2-\epsilon(\sqrt 2-1)^2\\
&\approx \sqrt 2-0.172\epsilon  \end {align}$$
The approximation comes from $\frac 1{1+x} \approx 1-x$, valid when $x \ll 1$  To be more careful, you can demand that $\epsilon$ be less than some limit, then worry about the quadratic error committed.
A: Actually, it is possible to derive a closed form expression for $x_n$.
For sequence obtained by repeat iteration of some function $f(x)$ (i.e. 
a sequence of the form $y_{n+1} = f(y_n)$ ), sometimes one can extract
detail information of it by studying rational function of the form
$\frac{\prod_k (x_n-\alpha_k)}{\prod_\ell(x_n - \beta_\ell)}$ 
where $\alpha_k, \beta_\ell$ are fixed points of the function $f(x)$.
For the problem at hand, $f(x) = 1 + \frac{1}{1+x}$. It has two fixed points at $\pm 2$.
For any $n \ge 0$, we have
$$\frac{x_{n+1}-\sqrt{2}}{x_{n+1}+\sqrt{2}}
= \frac{1 + \frac{1}{1+x_n} - \sqrt{2}}{1 + \frac{1}{1+x_n} + \sqrt{2}}
= \frac{(1-\sqrt{2})(1+x_n)+1}{(1+\sqrt{2})(1+x_n)+1}
= \lambda\left(\frac{x_n - \sqrt{2}}{x_n + \sqrt{2}}\right)
$$
where $\displaystyle\;\lambda = \frac{1-\sqrt{2}}{1+\sqrt{2}}\;$. Since this is true for all $n$, 
we find
$$\frac{x_n - \sqrt{2}}{x_n + \sqrt{2}} = \lambda^n \left(\frac{x_0-\sqrt{2}}{x_0+\sqrt{2}}\right)
\lambda^n \left(\frac{1-\sqrt{2}}{1+\sqrt{2}}\right) = \lambda^{n+1}
\quad\implies\quad
x_n = \sqrt{2} \left(\frac{1+\lambda^{n+1}}{1 - \lambda^{n+1}}\right)$$
Using the fact $|\lambda| \approx 0.17157 < 1$, the sequence $x_n$ converges to:
$$\lim_{n\to\infty} x_n = \sqrt{2}\left(\frac{1 + 0}{1 - 0}\right) = \sqrt{2}$$
