Prove that the sequence $b_n = 1$, $b_{n+1} = \frac{1}{1+b_n}$ converges.

Question

I need to prove that the sequence $b_1 = 1$, $b_{n+1} = \frac{1}{1+b_n}$ converges.

If $\lim_{n\to\infty} b_n = L$ then $\lim_{n\to\infty} b_{n+1} = L$, so $\lim_{n\to\infty} b_{n+1} = \frac{1}{1+\lim_{n\to\infty} b_n} \implies L = \frac{1}{1+L} \implies L^2 + L - 1 = 0 \implies L = \frac{-1+\sqrt{5}}{2}$.

So I know that if the sequence converges to $L$ then $L = \frac{-1+\sqrt{5}}{2}$. How can I prove that the sequence converges?

EDIT:

With the help of the answers I got my resolution:

Let's prove that $b_n$ converges by proving that the subsequences $b_{2n}$ and $b_{2n-1}$ are monotonic and bounded.

I want to prove that $\forall n \in \mathbb N$, $b_{2n} < b_{2(n+1)} < L$ and $b_{2n-1} > b_{2(n+1)-1} > L$.

I'm going to prove using induction.

First Step:

$\frac{1}{2} < \frac{3}{5} < \frac{-1 + \sqrt{5}}{2} \implies b_2 < b_4 < L $

and

$1> \frac{2}{3} > \frac{-1 + \sqrt{5}}{2} \implies b_1 > b_3 > L $

Second Step:

Let's prove that $b_{2n-1} > b_{2n+1} > L \implies b_{2n+1} > b_{2n+3} > L$

and $b_{2n} < b_{2n+2} < L \implies b_{2n+2} < b_{2n+4} < L$

$b_{2n-1}>b_{2n+1}>L \implies 1+b_{2n-1} > 1+b_{2n+1}>1+L \implies$

$\frac{1}{1+b_{2n-1}} = b_{2n} < \frac{1}{1+b_{2n+1}} = b_{2n+2} < \frac{1}{1+L} = L \implies $

$1+b_{2n} < 1+b_{2n+2}<1+L \implies \frac{1}{1+b_{2n}} = b_{2n +1} > \frac{1}{1+b_{2n+2}} = b_{2n+3} > \frac{1}{1+L} = L \implies$

$1+b_{2n+1} > 1+b_{2n+3} > 1+L \implies \frac{1}{1+b_{2n+1}} = b_{2n +2} < \frac{1}{1+b_{2n+3}} = b_{2n+4} < \frac{1}{1+L} = L$.

Thus $b_n$ converges.

Answer 1

Try showing that the subsequences of even and odd terms are monotonic and bounded. If this is the case, then both subsequences must converge. From there it shouldn't be too hard to show that they converge to the same thing, and therefore the overall sequence must converge.

Answer 2

Here's another interesting way of proving its convergence (And might provide some nice insights into the limit): Define $$b_n=\frac{h_n}{g_n}$$

where these are the numerator and denominator of $b_n$ (with no reductions to a simpler form after appyling the recursion formula). Then from your definition $$b_{n+1}=\frac{h_{n+1}}{g_{n+1}}=\frac{1}{1+\frac{h_n}{g_n}}=\frac{g_n}{h_n+g_n}.$$

Hence, $$h_{n+1}=g_n$$ and $$g_{n+1}=h_n+g_n.$$

Rearranging slightly, we get $$h_{n+1}=h_n+h_{n-1}$$ and $$g_{n+1}=g_n+g_{n-1}.$$

Of course, we can find just by computing the first few terms that $h_1=h_2=1$, $g_1=1$, and $g_2=2$. However, this is simply the recursion formula for the fibonacci numbers! Thus, we know $h_n=F_n$ and $g_n=F_{n+1}$ (where $F_n$ is the $n$th fibonacci number). Therefore, $$b_n=\frac{F_n}{F_{n+1}}.$$

At this point, there are many ways to show that the limit exists (And also show why you got the limit of $\frac{-1+\sqrt{5}}{2}$.).