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
- Ceva's Theorem: A Matter of Appreciation
- When the Counting Gets Tough, the Tough Count on Mathematics
- I. Sharygin's Problem of Criminal Ministers
- Single Pile Games
- Take-Away Games>
- Number 8 Is Interesting
- Curry's Paradox
- A Problem in Checker-Jumping
- Fibonacci's Quickies
- Fibonacci Numbers in Equilateral Triangle
- Binet's Formula by Inducion
- Binet's Formula via Generating Functions
- Generating Functions from Recurrences
- Cassini's Identity
- Fibonacci Idendtities with Matrices
- GCD of Fibonacci Numbers
- Binet's Formula with Cosines
- Lame's Theorem - First Application of Fibonacci Numbers
|Contact| |Front page| |Contents| |Games| |Up|
Copyright © 1996-2018 Alexander Bogomolny72012967