Fibonacci numbers
Fibonacci Numbers
The Fibonacci numbers \(F_n\) are defined by a recursive formula. The first two numbers are given by \(F_1=1\) and \(F_2=1\) and, for all \(n\ge 3\), \(F_n=F_{n-1}+F_{n-2}\).
\[1,1,2,3,5,8,13,21,34,55,89,...\]
Fibonacci Numbers and the Golden Ratio
See Donald Duck in Mathmagic Land (7 minute mark - 14 minute mark).
Fibonacci Numbers and the Golden Ratio
The golden ratio \[ \phi=\frac{1+\sqrt{5}}{2} \] is the larger root of the quadratic polynomial \(x^2-x-1=0\).
Proposition: The ratio of successive Fibonacci numbers \(F_{n+1}/F_{n}\) converges to the Golden ratio.
Some Data
1 1 1.000000000
1 2 2.000000000
2 3 1.500000000
3 5 1.666666667
5 8 1.600000000
8 13 1.625000000
13 21 1.615384615
21 34 1.619047619
34 55 1.617647059
55 89 1.618181818
89 144 1.617977528
144 233 1.618055556
233 377 1.618025751
377 610 1.618037135
610 987 1.618032787Fibonacci Numbers cont’d
Proposition: \(F_{n+1}^2-F_{n}F_{n+1}-F_{n}^2=(-1)^{n}\).
\[\begin{align*} 3^2-(2)(3)-2^2&=-1 \\ 5^2-(3)(5)-3^2&=1 \\ 8^2-(5)(8)-5^2&=-1 \\ \end{align*}\]
Corollary: \(\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}}=\phi\).
Proof: Divide through by \(F_{n}^2\):
\[ (\frac{F_{n+1}}{F_{n}})^2-(\frac{F_{n+1}}{F_{n}})-1=\frac{(-1)^{n}}{F_{n}^2} \]
The right hand side goes to zero, so \((F_{n+1}/F_{n})\) converges to a root of the polynomial which is greater than one.
Proof of proposition
First check that \(F_{2}^2-F_{1}F_{2}-F_{1}^2=-1\), which is \(1^2-1-1=-1\) as we want.
- Now suppose that the formula holds for \(F_{n}\), so \(F_{n}^2-F_{n}F_{n-1}-F_{n-1}^2=(-1)^{n-1}\).
- Consider \(F_{n+1}^2-F_{n+1}F_{n}-F_{n}^2\).
- Substitute \(F_{n+1}=F_{n}+F_{n-1}\) to get
\[\begin{multline*} (F_{n}+F_{n-1})^2-(F_{n}+F_{n-1})F_{n}-F_{n}^2 = \\ F_{n}^2+2F_{n}F_{n-1}+F_{n-1}^2-F_{n}^2-F_{n-1}F_{n}-F_{n}^2 \end{multline*}\]
Then the right hand side of this equation is
\[ -F_{n}^2+F_{n}F_{n-1}+F_{n-1}^2= -(F_{n}^2-F_{n}F_{n-1}-F_{n-1}^2) =(-1)^{n} \]
where we used the inductive hypothesis to in the second-to-last step.