How can I prove this sequence convergent?

Question

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?

Answer 1

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!

Answer 2

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.

Answer 3

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$