Binet's Formula by Induction

Binet's formula that we obtained through elegant matrix manipulation, gives an explicit representation of the Fibonacci numbers that are defined recursively by

\(F_n= \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{if } n > 1. \\ \end{cases} \)

The formula was named after Binet who discovered it in 1843, although it is said that it was known yet to Euler, Daniel Bernoulli, and de Moivre in the seventeenth secntury. The formula directly links the Fibonacci numbers and the Golden Ratio. Golden ratio \(\phi=\frac{1+\sqrt{5}}{2}\) is the positive root of the quadratic equation

\(x^{2}-x-1=0.\)

The second root of the equation is negative: \(\frac{1-\sqrt{5}}{2}\). It is variably denoted as \(\tau\) or \(\hat{\phi}\). I'll be using the first of these as more amenable to typesetting.

With this preliminaries, let's return to Binet's formula:

\(F_{n}=\frac{1}{\sqrt{5}}({\phi}^{n}-{\tau}^{n}).\)

Since \(\phi \tau = -1\), the formula often appears in another form:

\(F_{n}=\frac{1}{\sqrt{5}}({\phi}^{n}-(-\phi)^{-n}).\)

The proof below follows one from Ross Honsberger's Mathematical Gems (pp 171-172). It depends on the following

Lemma

For any solution \(x\) of \(x^{2}-x-1=0\), \(x^{n} = xF_{n}+F_{n-1}, n\ge 1.\)

Proof of Lemma

The proof is by induction. By definition, \(F_{1}=1\) and \(F_{0}=0\) so that, indeed, \(x^{1}=x\cdot 1+0=x\).

For \(n=2\), \(F_{2}=F_{1}=1\), and

\(x\cdot F_{2}+F_{1} = x\cdot 1 + 1 = x + 1 = x^{2}.\)

Assume now that, for some \(n\), \(x^{n} = xF_{n}+F_{n-1}\) and prove that \(x^{n+1} = xF_{n+1}+F_{n}\). To this end, multiply the identity by \(x\):

\( \begin{align} \\ x^{n+1} &= x^{2}F_{n}+xF_{n-1} \\ &= (x+1)F_{n} + xF_{n-1} \\ &= x(F_{n}+F_{n-1})+F_{n} \\ &= xF_{n+1} + F_{n}. \\ \end{align} \)

Proof of Binet's formula

By Lemma,

\({\phi}^{n} = {\phi}F_{n}+F_{n-1}\) and \({\tau}^{n} = {\tau}F_{n}+F_{n-1}\).

Subtracting one from the other gives \({\phi}^{n} - {\tau}^{n} = ({\phi} - {\tau})F_{n}\). It follows that

\(\displaystyle F_{n} = \frac{{\phi}^{n}- {\tau}^{n}}{\phi - \tau}\).

To obtain Binet's formula observe that \({\phi - \tau}=\sqrt{5}\).

The proof may not teach much but its simplicity is enchanting.

References

R. Honsberger, Mathematical Gems, MAA, 1973, pp. 171-172
R. Honsberger, Mathematical Gems III, MAA, 1976, pp. 108-109

Fibonacci Numbers

Golden Ratio in Geometry

71534638