Fibonacci Sequence, Golden Ratio

I've been asked to show that $x_n \rightarrow L$ as $n \rightarrow \infty$ where $x_n = F_{n+1}/F_{n}$ for $n \in \mathbb{Z}^+$, where $F_n$ denotes the $n^{th}$ Fibonacci number. I am supposed to use this and the fact that $1/x_n \rightarrow 1/L$ as $n \rightarrow \infty$ to prove that $L$ is the golden ratio. I'm not sure how to go about computing this. Should I use the standard $|x_n -L| < \epsilon$ proof? That doesn't seem to get me anywhere when I try it.

Solution 1:

Let $R = \frac{F_{n+1}}{F_n}$, and suppose that as $n\to\infty$ this converges to some limit $L$. Then the following is true: $$L = \lim_{n\to\infty}\frac{F_{n+1}}{F_n} = \lim_{n\to\infty} 1 + \frac{F_{n-1}}{F_n} = \lim_{n\to\infty} 1 + \frac{F_{n}}{F_{n+1}} = 1 + \frac1{L}$$

So assuming the above, $$L = 1+\frac{1}{L}\implies L^2 - L - 1 = 0\implies L = \frac{1\pm \sqrt{5}}{2}$$ Clearly, $L$ should be positive, and we are left with $$L = \frac{1+ \sqrt{5}}{2} = \phi$$

Solution 2:

Try this, which is not as slick as it might be.

Since $F_n\gt 0$, $0\lt x_n \lt 1$

Using the Fibonacci relationship $x_n=\cfrac {F_n}{F_n+F_{n-1}}=\cfrac 1{1+x_{n-1}}$

$$x_n-x_{n-1}=\cfrac 1{1+x_{n-1}}-\cfrac 1{1+x_{n-2}}=-\cfrac {x_{n-1}-x_{n-2}}{(1+x_{n-1})(1+x_{n-2})}$$

In the case that $x_{n-1}\gt x_{n-2}$ we have $x_n-x_{n-1}\lt 0$ and $$x_{n}-x_{n-1}\gt x_{n-2}-x_{n-1}; x_{n-1}\gt x_n\gt x_{n-2}$$

In the case that $x_{n-1}\lt x_{n-2}$ we have $x_{n-1}\lt x_{n}\lt x_{n-2}$.

We also have $|x_n-x_{n-1}|\lt|x_{n-1}- x_{n-2}|$ (we can prove $\lt \frac 12 |x_{n-1}- x_{n-2}|$ once we know the $x_i$ are all $\ge \frac 12$)

If the Fibonacci sequence is indexed so that the terms are $1,1,2,3,5\dots$ then $x_1=1, x_2=0.5 \dots$ and $x_1\gt x_2$ and we have $x_1\gt x_3\gt x_5\gt x_7 \dots \gt x_{2n+1} \gt x_{2n}$ and also $x_2\lt x_4\lt x_6\dots \lt x_{2n}\lt x_{2n-1}$.

The odd terms are decreasing and bounded below, the even terms are increasing and bounded above, and the absolute value of the difference between odd and even goes to zero. It follows tha the two sequences (odd and even) tend separately to a limit and that limit must be the same for both. This is a special case of a theorem on convergence of continued fractions.

Note this is done without identifying what the limit is (when dealing with general continued fractions, you don't know).