How can I prove this sequence convergent? I am trying to prove the sequence $(u_n)$ so that $u_1=1$ and $u_{n+1}=1+\dfrac{1}{u_n}$ is convergent. With some first items, I guess that the subsequence $(u_{2n})$ is decreasing and the subsequence $(u_{2n-1})$ is increasing, but I can't proof this. How can I proof?
 A: Hint: We can write
$$u_{3} = 1 + \frac{1}{1 + \frac{1}{u_1}} = 1 + \frac{u_1}{u_1+1} = 
\frac{u_1+1}{u_1+1} + \frac{u_1}{u_1+1}
= \frac{2u_1+1}{u_1+1}$$
$$u_{4} = 1+\frac{u_1+1}{2u_1+1} = 
\frac{2u_1+1}{2u_1+1} + \frac{u_1+1}{2u_1+1} =
\frac{3u_1+2}{2u_1+1}$$
$$u_{5} = 1 + \frac{2u_1+1}{3u_1+2} =
\frac{3u_1+2}{3u_1+2} + \frac{2u_1+1}{3u_1+2} = 
 \frac{5u_1+3}{3u_1+2}$$
Notice a pattern? You can prove it using induction!
A: First, solve your recurrence for its limit by writing $L=1+\frac 1L$.  Now you can look at the distance from $L$ by writing 
$$u_{k+1}-L=1+\frac 1{(u_k-L)+L}-L$$
and note that if $u_k \lt L, u_{k+1} \gt L$ and vice versa.  This shows the even terms are bounded below by $L$ and the odd terms are bounded above by $L$.
Now plug the definition for $u_k$ in terms of $u_{k-1}$ into the above and show the distance on the left is decreasing toward zero for the even terms and increasing toward zero for the odd terms.
A: I want to show another possible approach.
Consider $f(x) = 1 + \frac{1}{x}$ for $x>0$. $f$ is clearly decreasing.
Thus $f \circ f$ is increasing.
We also have $u_1=1$, $u_2 = 2$, $u_3 = \frac{3}{2} > u_1$ and $u_4 = \frac{5}{3} < u_2$.
Since $u_{n+2} = f(f(u_n))$ it's very easy to see (by induction and using $f \circ f$ increasing) that $u_1 < u_3 < u_5 < \ldots$ and that $u_2 > u_4 > u_6 > \ldots$!
Let's call $\varphi = \frac{1+ \sqrt{5}}{2}$ the fixed point of $f$. Again by induction on $n$, it's easy to verify that $u_{2n+1} < \varphi < u_{2n}$ for any $n \in \mathbb{N}$.
Now because of boundness in the right direction both $u_{2n}$ and $u_{2n+1}$ converge. Let's call $l$ and $m$ the two limits. We have (since $u_{n+1} = f(u_n)$ and $f$ is continuous) $l = f(m)$ and $m = f(l)$.
Thus $lm = l+1$ and $lm = m+1$. So $l=m$ and $l= \varphi$.
Therefore the sequence converges to $\varphi$
