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

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

Fibonacci Numbers

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|Contact| |Front page| |Contents| |Games| |Up|

Copyright © 1996-2018 Alexander Bogomolny

72012967