Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?!

share|improve this question
6  
I would start with the fact that the limit is obviously bounded above by $2$ (can you see this?), and show it is monotonic. –  Daniel Littlewood Feb 23 at 21:12
1  
A simple way is to use the "Binet" formula for $F_n$. –  André Nicolas Feb 23 at 21:15
    
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. –  Guest Feb 23 at 21:17
add comment

marked as duplicate by Ma Ming, Michael Hoppe, Davide Giraudo, some1.new4u, froggie Feb 23 at 22:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

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.

share|improve this answer
    
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? –  Guest Feb 23 at 21:45
    
I've sketched a proof in the answer - is this clear enough? –  Daniel Littlewood Feb 23 at 22:13
    
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... –  Guest Feb 23 at 22:14
    
Simply replace $n$ by $2n$. Clearly when $n$ is even the difference is positive and when $n$ is odd the difference is negative! –  Daniel Littlewood Feb 23 at 23:13
    
Yes, I did that. 2n and 2n+1 for even and odd respectively. But then what? –  Guest Feb 23 at 23:15
show 9 more comments

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.).

share|improve this answer
    
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$? –  Guest Feb 23 at 21:19
    
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? –  Guest Feb 23 at 21:44
    
@Guest If you showed my claim, then $f_1<f_2<f_3\cdots \le \phi$. –  Ma Ming Feb 23 at 22:57
add comment

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