Existence of Limit for $x_{n+1} = 1+1/x_{n}$ I'm attempting to prove that if one defines a sequence with $x_{1} = 1$ and 
$$x_{n+1} = 1+\frac{1}{x_{n}}$$
for all $n >1$ then the limit of $\{x_{n}\}_{n \ge 1}$ exists. 
My Attempt:
Since $\{x_{n}\}_{n \ge 1}$ was defined recursively I immediately thought to try and prove that the sequence is monotone and bounded. The problem is that $\{x_{n}\}_{n \ge 1}$ is an alternating sequence. Its first few values are $1,2,3/2,5/8,\ldots$. I checked boundedness next. Since $x_{1} = 1 \le \frac{1+\sqrt{5}}{2}$ we induct on $n$ and assume $x_{n} \le \frac{1+\sqrt{5}}{2}$. For the $x_{n+1}$ case we find that $x_{n+1} \ge \frac{1+\sqrt{5}}{2}$ which I thought was a little odd... Is there another way I should be attacking this proof or can I fiddle with the sequence a bit to use MCT?
 A: You probably mean $1, 2, \frac{3}{2}, \frac{5}{3}, ...$
Yes you can use MCT. As you have observed $x_n$ somehow "alternates". More precisely, $x_{2n+1}$ seems to increase while $x_{2n}$ seems to decrease. Also, $x_1<x_2$ and perhaps $x_{2n+1}<x_{2n}$. In that case, you have the inequality
$$
x_1<x_3<x_5<...<x_6<x_4<x_2
$$
with which we are almost there. Try then to prove that the extracted sequences $x_{2n}$ and $x_{2n+1}$ are indeed monotonous. Convergence should follow from the above inequalities.
A: This is a trick I have learned here a few years ago.
Let's say you have a sequence $x_n$ defined by some sort of iteration.
If the limit $\lambda$ of the sequence satisfies a quadratic equation with roots $\alpha, \beta$ and one construct an auxiliary sequence by
$$y_n = \frac{x_n - \alpha}{x_n - \beta}$$
Sometimes, the recurrence relation for $y_n$ will be so simple to the point we can deduce the convergence of $x_n$ or even an closed form expression of $x_n$.
For the problem at hand, the sequence is generated by the iteration.
$$x_{n+1} = 1 + \frac{1}{x_n}$$ 
The limit $\lambda$ need to satisfies a quadratic equation
$$\lambda = 1 + \frac{1}{\lambda}\quad\iff\quad \lambda^2 - \lambda - 1 = 0$$
which have roots $\alpha = \varphi, \beta = -\frac{1}{\varphi}$ where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.
If one define $\displaystyle\;y_n = \frac{x_n - \varphi}{1 + \varphi x_n}\;$, we have:
$$\begin{align}y_{n+1} 
&= \frac{x_{n+1} - \varphi}{1 + \varphi x_{n+1}}
= \frac{1 + \frac{1}{x_n} - \varphi}{1 + \varphi( 1 + \frac{1}{x_n} ) }
= \frac{(1-\varphi)x_n + 1}{(1+\varphi)x_n + \varphi}\\
&= \frac{1}{\varphi}\frac{(\varphi - \varphi^2)x_n + \varphi}{\varphi^2 x_n + \varphi}
= -\frac{1}{\varphi^2}\frac{x_n - \varphi}{1 + \varphi x_n}
= -\frac{1}{\varphi^2} y_n
\end{align}
$$
Since this is true for all $n \ge 1$, we can solve the recurrence relation and obtain a closed form expression for $y_n$:
$$y_n = \left(-\frac{1}{\varphi^2}\right)^{n-1} y_1 = 
\left(-\frac{1}{\varphi^2}\right)^{n-1} \left(\frac{1-\varphi}{1+\varphi}\right)$$
Since $\left| -\frac{1}{\varphi^2} \right| < 1$, we have $y_n \to 0$ as $n \to \infty$. As a result,
$$\lim_{n\to\infty} x_n = \lim_{n\to\infty} \frac{y_n + \varphi}{1 - \varphi y_n} = \frac{0 + \varphi}{1 - \varphi \cdot 0} = \varphi$$
A: One way to prove it would be to note that the terms are ratios of consecutive Fibonacci numbers. I imagine any other proof of convergence would essentially mimic the proof that the ratio of consecutive Fibonacci numbers converges, namely to $\varphi=\frac{1+\sqrt{5}}{2}$.
A: The function $y = 1 + (1/x)$ is strictly decreasing for $x > 0$ with a single fixed point at the golden ratio $\phi$. Thus if $x_n$ is less than the golden ratio, $x_{n+1}$ will be greater, and vice versa. Thus the function oscillates back and forth over the golden ratio, hopefully converging to it. To prove convergence we compare $|x_n - \phi|$ to $|x_{n+1} - \phi|$. 
$$|x_{n+1} - \phi| = |1 + \frac{1}{x_n} - \phi| = |(1-\phi) + \frac{1}{x_n}|$$
Next we use the special property of the golden ratio, that $1 - \phi = -1/\phi$.
$$ = |\frac{1}{x_n} - \frac{1}{\phi}| = |\frac{\phi - x_n}{\phi x_n}|$$
Thus the terms $|x_{n} - \phi|$ are decreasing, each time by a factor at least $\phi x_n \geq \phi \geq 1.6$, since it is clear that $x_{n} \geq 1$. Hence $|x_{n} - \phi|$ must be going to zero, so that $x_{n} \to \phi$.
A: Yet another angle of approach comes from looking at the double-iterate: that is, looking at $x_{n+2}$, not $x_{n+1}$, in relation to $x_n$.  Note that we have $x_{n+2}=1+1/x_{n+1}$ $=1+1/(1+1/x_n)$ $=1+\frac{x_n}{x_n+1}$.  Now, this is obviously $\leq 2$ for $x_n\geq 0$; what's more, we can check monotonicity: $x_{n+2}\gt x_n$ iff $1+\frac{x_n}{x_n+1}\gt x_n$ iff $(x_n+1)+x_n\gt x_n(x_n+1)$ iff $x_n+1\gt x_n^2$ iff $x_n\lt\phi$ (check this last assertion yourself!).  Thus, since $x_0=1$, the even terms of the series are monotone increasing and bounded and thus they converge to a limit $L_e$. What's more, since $x_1=2\gt\phi$, the odd terms of the series are monotone decreasing and (trivially) bounded from below by $1$; therefore, they also converge to a limit $L_o$. Now you just have to show that $L_e=L_o$... (hint: $L_e=1+\frac1{L_o}$ and $L_o=1+\frac1{L_e}$ — why?)
