# Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that

\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 \cr & {\phi ^5} = 5\phi + 3 \cr & \cdots = \cdots \cr & {\phi ^n} = {F_n}\phi + {F_{n - 1}} \cr}

Thus one would have

$$\frac{{{\phi ^{n + 1}} - {F_n}}}{{{\phi ^n} - {F_{n - 1}}}} = \frac{{{F_{n + 1}}}}{{{F_n}}}$$

$$\frac{{\phi - \displaystyle\frac{{{F_n}}}{{{\phi ^n}}}}}{{1 - \displaystyle\frac{{{F_{n - 1}}}}{{{\phi ^n}}}}} = \frac{{{F_{n + 1}}}}{{{F_n}}}$$

Now I remember that in Apostol's Calculus he asked to prove for $F_1 = 1$, $F_2 = 2$ $$F_n < \phi^n$$ Using this, (which I would like to prove too) you have

$$\phi - \frac{{{F_n}}}{{{\phi ^n}}} > \phi - 1$$

$$1 - \frac{1}{\phi }\frac{{{F_{n - 1}}}}{{{\phi ^{n - 1}}}} < \frac{{\phi - 1}}{\phi } < 1$$

But this would mean (I'm not 100% sure on this. EDIT: This is wrong)

$$\frac{{\phi - 1}}{{ \frac{{\phi - 1}}{\phi }}} > \frac{{\displaystyle \phi - \frac{{{F_n}}}{{{\phi ^n}}}}}{{1 - \displaystyle \frac{1}{\phi }\frac{{{F_{n - 1}}}}{{{\phi ^{n - 1}}}}}} = \frac{{{F_{n + 1}}}}{{{F_n}}}$$

$$\phi > \frac{{{F_{n + 1}}}}{{{F_n}}}$$

ADD: I guess it then can be proved that

$$\left| {\phi - \frac{{{F_{n + 1}}}}{{{F_n}}}} \right| = \left| {\phi - \frac{{\phi - \frac{{{F_n}}}{{{\phi ^n}}}}}{{1 - \frac{{{F_{n - 1}}}}{{{\phi ^n}}}}}} \right|$$

Then if you can prove $$\frac{{{F_n}}}{{{\phi ^n}}} \to L$$

$$\frac{{{F_n}}}{{{F_n}\phi + {F_{n - 1}}}} \to L$$

(It can be proved that the limit is $\frac{\phi+2}{\phi}$, but using the quotient limit, which cant be used.)

$$\left| {\phi - \frac{{{F_{n + 1}}}}{{{F_n}}}} \right| = \left| {\phi - \frac{{\phi - \frac{{{F_n}}}{{{\phi ^n}}}}}{{1 - \frac{{{F_{n - 1}}}}{{{\phi ^n}}}}}} \right| < \epsilon$$

Could someone help?

-
Upvoter, give me some feedback please (!) –  Pedro Tamaroff Feb 5 '12 at 19:10
I don't follow. If $0<\frac{F_{n - 1}}{\phi ^{n - 1}}<1$ then $1 - \frac{1}\phi\frac{F_{n - 1}}{\phi ^{n - 1}} > 1 - \frac1\phi=\frac{\phi-1}\phi$, the opposite inequality to one you state. And in any case $\phi > \frac{F_{n + 1}}{F_n}$ cannot be right: successive quotients of consecutive $F_i$ give fractions above and below $\phi$. –  Marc van Leeuwen Feb 5 '12 at 19:23
It is true that $F_n<\phi^n$. That bound is unlikely to be strong enough, since $F_n$ is well below $\phi^n$. But the start of your argument is I think a useful one. –  André Nicolas Feb 5 '12 at 19:34
If you prove Binet's formula then with the presence of an $\sqrt5$ you could prove it. Kind of cheating, perhaps. –  anon Feb 5 '12 at 19:44
@MarcvanLeeuwen van Leeuwen, you're right. Then we should aim at $\displaystyle \left|\phi-\frac{F_{n+1}}{F_n}\right| < \epsilon$ –  Pedro Tamaroff Feb 5 '12 at 19:50
show 1 more comment

The following is an argument based on the identity of the OP.

We use in addition the following standard Fibonacci number identity, which is easily proved by induction. $$F_n^2+(-1)^n=F_{n-1}F_{n+1}.$$

If $n\ne 0$, we can rewrite the above identity as $$\frac{F_{n+1}}{F_n}=\frac{F_n}{F_{n-1}} +\frac{(-1)^n}{F_{n-1}F_n}.\qquad\qquad(\ast)$$

Now we use the OP's identity $\phi^n=F_n\phi+F_{n-1}$, rewritten as two identities $$\phi^n=F_n\phi+F_{n-1} \qquad\text{and}\qquad\phi^{n+1}=F_{n+1}\phi+F_{n}.$$ Divide both sides of the first identity by $F_{n-1}$, and both sides of the second by $F_{n}$. We get $$\frac{\phi^n}{F_{n-1}}=\frac{F_n}{F_{n-1}}\phi+1,$$ $$\frac{\phi^{n+1}}{F_{n}}=\frac{F_{n+1}}{F_{n}}\phi+1.$$

By choosing $n$ large enough, we can make the two right-hand sides arbitrarily close to each other. For this we do not need to know that the limit of $F_m/F_{m-1}$ exists, all we need is $(\ast)$ and the fact that the Fibonacci numbers blow up.

So by choosing $n$ large enough, we can make the ratio of the right-hand sides (and therefore of the left-hand sides) arbitrarily close to $1$. It follows that $$\lim_{n\to\infty}\frac{\phi^n/F_{n-1}}{\phi^{n+1}/F_n}=1,$$ which immediately implies that $$\lim_{n\to\infty}\frac{F_n}{F_{n-1}}=\phi.$$

Remark: The OP has found a path to the limit that I had not seen before. It may be useful to recall two standard ways to show that our limit is $\phi$. One way is to use the Binet Formula. The limit result is then immediate.

Another way uses the identity $(\ast)$. Note that this identity says that $$\frac{F_{n+1}}{F_n}-\frac{F_n}{F_{n-1}}$$ alternates in sign and approaches $0$. Let $a_n=F_n/F_{n-1}$. Consider the two sequences $a_2, a_4, a_6,\dots$ and $a_3, a_5, a_7,\dots$. We can use $(\ast)$ to show that the first sequence is increasing, and the second is decreasing. They are both bounded, so each has a limit. Easily from $(\ast)$ the limits must be the same, so our sequence of ratios has a limit. Let the limit be $\alpha$. From $F_{n+1}=F_n+F_{n-1}$, we conclude, by dividing by $F_n$, that $\alpha=1+\frac{1}{\alpha}$. This gives a quadratic equation, and solving we find that $\alpha=\phi$.

The idea of the OP leads to an argument that is simpler than the second way, and possibly simpler than the Binet Formula argument, if you count in the cost of establishing that formula.

However, situations where terms approach something alternately from above and from below which come up moderately often, so it is good to be exposed to that idea. And one will almost certainly want to establish the Binet Formula anyway.

-
Nice. I'll wait for some more answers before "closing". I'd like to have a link for $(\star)$ –  Pedro Tamaroff Feb 5 '12 at 22:48
@Peter: I am lousy at searching. It seems not to be mentioned by Wikipedia, too simple. But it really is the first identity one proves. Look at $F_{n+1}^2-F_nF_{n+2}$. This is $F_{n+1}(F_n+F_{n-1})-F_n(F_{n}+F_{n+1})$. Expand and simplify. We get $-(F_n^2-F_{n-1}F_{n+1})$. So each time we increment $k$ by $1$, the expression $F_k^2-F_{k-1}F_{k+1}$ just switches sign. Finally, check its value at $k=1$. –  André Nicolas Feb 5 '12 at 23:24
Ok. I get it. I thought you'd realize I do know the methods in the remark, but thanks anyways. Really complete answer - almost made my day. =) –  Pedro Tamaroff Feb 5 '12 at 23:28
@Peter: I have the bad habit of writing more (much more) than necessary. Even felt mildly guilty about only giving outline of the nested interval argument. The identity I used is the basis of a standard trick, in which you take a square piece of paper, divided by lines in an $8\times 8$ grid, cut it up in a certain way, reassemble it into what looks like a $5\times 13$ rectangle. –  André Nicolas Feb 5 '12 at 23:46
Reading your answer again I must say I'd upvote again if I could! Thanks for this small compendium. –  Pedro Tamaroff Apr 18 '12 at 17:39