6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Presumably you're supposed to show that $1/x_n\to L-1$, right? $\endgroup$ – Alex Becker Apr 4 '14 at 6:17
  • $\begingroup$ @Alex, $L-1=1/L$! $\endgroup$ – user134824 Apr 4 '14 at 6:18
  • 1
    $\begingroup$ Wait guys, isn't $$\lim_{n\to\infty} \frac{f_n}{f_{n+1}} =\frac1{\phi}$$? $\endgroup$ – Guy Apr 4 '14 at 6:19
  • $\begingroup$ This is not a duplicate, but I once elaborated the computation here, have a look. $\endgroup$ – k.stm Apr 4 '14 at 6:22
  • $\begingroup$ @Sabyasachi I meant to say that $x_n = \frac{F_{n+1}}{F_n}}$. I have just edited it. $\endgroup$ – notGauss Apr 4 '14 at 6:42
6
$\begingroup$

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}\lt x_{n-2}|$ (we can prove $\lt \frac 12 |x_{n-1}\lt 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).

$\endgroup$
  • 1
    $\begingroup$ This is along the lines of what I was looking for. Thank you for your insight. $\endgroup$ – notGauss Apr 7 '14 at 17:19
6
$\begingroup$

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$$

$\endgroup$
3
$\begingroup$

You can use $F_n = \frac{φ^n - ψ^n}{√5}$ where $φ$ and $ψ$ with $φ > ψ$ are the zeros of $X^2 - X - 1$ to compute the limit. It turns out, the limit is $1/φ = -ψ$.

$\endgroup$
2
$\begingroup$

We have: $x_n = \dfrac{F_n}{F_{n+1}} = \dfrac{a^n - b^n}{a^{n+1} - b^{n+1}} = a \cdot\dfrac{a^{2n} - (-1)^n}{a^{2n+2} - (-1)^n} = a \cdot \dfrac{1 - (-1)^na^{-2n}}{a^2 - (-1)^na^{-2n}} \to \dfrac{1}{a}$ as $ n \to \infty$. Here $a = \dfrac{1 + \sqrt{5}}{2}$, and $b = \dfrac{1 - \sqrt{5}}{2}$, and $a \cdot b = -1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.