5
$\begingroup$

Using the definition of Fibonacci numbers, $F_n=F_{n-1}+F_{n-2}$, I can prove that the limit of $\frac{F_{n+1}}{F_n}$ as $n\to\infty$ is $\phi$ if we assume that the limit exists.

How can we prove that the limit does in fact exist?

Is there more than one method?


I do not think this is a duplicate. Please can someone explicitly show how to split the odd and even terms of this ratio sequence into two sequences- one monotonic increasing and one monotonic decreasing- and given that all ratios are between 1 and 2, show that the limit exists and we do not oscillate forever.


Most of the question has been answered.

I have shown that there are two subsequences- one increasing and bounded above by 2 and one decreasing, bounded below by 1. Using the fact that the limit exists, I can show it has value $\phi$. But how can I show the limit is the same for both subsequences?!

$\endgroup$
  • 6
    $\begingroup$ I would start with the fact that the limit is obviously bounded above by $2$ (can you see this?), and show it is monotonic. $\endgroup$ – preferred_anon Feb 23 '14 at 21:12
  • 1
    $\begingroup$ A simple way is to use the "Binet" formula for $F_n$. $\endgroup$ – André Nicolas Feb 23 '14 at 21:15
  • $\begingroup$ Daniel Littlewood- thank you. The only problem is that the sequence of ratios oscillates to the limit, right? If I could say it was monotonic increasing and bounded above then I would know what to do, or monotonic decreasing and bounded below, but that isn't the case. Andre Nicolas- Thanks for that answer. The Binet formula is quite incredible! I've seen that proof and would like to use that as a second solution. I would also really like to be able to show the limit exists using only real analysis if possible. $\endgroup$ – Guest Feb 23 '14 at 21:17
  • $\begingroup$ @preferred_anon only monotonic considering even or odd terms. $\endgroup$ – qwr Feb 15 '19 at 17:15
6
$\begingroup$

By Cassini's Identity: $$\left|\frac{F_{n+1}}{F_{n}}-\frac{F_{n}}{F_{n-1}}\right|=\left|\frac{F_{n+1}F_{n-1}-F_{n}^{2}}{F_{n}F_{n-1}}\right|=\left|\frac{(-1)^{n}}{F_{n}F_{n-1}}\right| \to 0$$

Proof of Cassini's Identity: $$F_{n+1}F_{n-1}-F_{n}^{2}\\ =(F_{n}+F_{n-1})F_{n-1}-F_{n}^{2}\\ =F_{n-1}F_{n}-F_{n}^{2}+F_{n-1}^{2}\\ =-(F_{n}(F_{n}-F_{n-1})-F_{n-1}^{2})\\ =-(F_{n}F_{n-2}-F_{n-1}^{2})$$ You can fill in the rest by induction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I like this a lot. I haven't heard of Cassini's Identity before. Could you please link to a proof or derivation of it? $\endgroup$ – Guest Feb 23 '14 at 21:45
  • $\begingroup$ I've sketched a proof in the answer - is this clear enough? $\endgroup$ – preferred_anon Feb 23 '14 at 22:13
  • $\begingroup$ Yes this is good, thank you! What I really want to do is split the sequence of ratios into two sequences- a monotonic increasing one and a monotonic decreasing one and go from there. But I don't know how to do it... $\endgroup$ – Guest Feb 23 '14 at 22:14
  • $\begingroup$ Simply replace $n$ by $2n$. Clearly when $n$ is even the difference is positive and when $n$ is odd the difference is negative! $\endgroup$ – preferred_anon Feb 23 '14 at 23:13
  • $\begingroup$ Yes, I did that. 2n and 2n+1 for even and odd respectively. But then what? $\endgroup$ – Guest Feb 23 '14 at 23:15
3
$\begingroup$

Hint: Consider $\frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}$. Let $f_n=\frac{F_n}{F_{n-1}}$. We have $$f_n=1+\frac{1}{f_{n-1}}.$$

Let $f(x)=1+\frac{1}{x}$ for $1<x<2$. Show if $x<\phi$, then $x<f(x)<\phi$ (We also have $\phi<f(x)<x$ for $x>\phi$, but it is irrelevant to our concern.).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this answer. This is how I was able to show that the limit was $\phi$ if it exists, but how do you know $f_n$ exists and is a real number as $n \to \infty$? $\endgroup$ – Guest Feb 23 '14 at 21:19
  • $\begingroup$ Thanks for the edit. Would you be able to do the next step? Sorry- I am still unclear on how this would prove the existence of the limit given its oscillation? $\endgroup$ – Guest Feb 23 '14 at 21:44
  • $\begingroup$ @Guest If you showed my claim, then $f_1<f_2<f_3\cdots \le \phi$. $\endgroup$ – Ma Ming Feb 23 '14 at 22:57

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