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?

Solution 1:

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.