Fibonacci Numbers

The Fibonacci numbers are a simple sequence of integers F_n defined as follows

F₀=F₁=1,

$$F_{n+2} = F_{n+1} +F_n, \hbox{ for all } n\geq0.$$

In words, the next number is the sum of the two preceding numbers. This sequence is easy to calculate:

$$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233,\ 377,\ 610, ...$$

For many centuries, the properties of these numbers have fascinated mathematicians of all levels. There is even a mathematical journal, The Fibonacci Quarterly, devoted exclusively to the study of these numbers. Some calculations suggest that the ratios F_n+1/F_n tend to a definite limit as n increases. We shall sketch a proof of the following:

$$\lim_{n\to \infty} {F_{n+1}\over F_n} = {1+\sqrt{5}\over 2}$$

The number on the right was called the ``golden mean'' by the ancient Greeks. A rectangle whose sides have ratio equal to the golden mean has the property that when we take away the square based on the smaller side we are left with a rectangle whose sides also have ratio equal to the golden mean. The golden mean was to the Greek eye the perfect ratio with which to design outlines of buildings (such as the Parthenon).

The proof of the above limit is based on consideration of the Taylor series

$$f(T) = \sum_{n=0}^\infty F_n T^n$$

where T is an indeterminate variable. This is an example of a ``generating series,'' a function that collects all the Fibonacci numbers together. We shall show that f(T) is a very simple function. First of all, splitting off the first two terms of the sum, we have

$$\begin{eqnarray*}f(T) &=& 1 +T +\sum_{n=2}^\infty F_n T^n\\ &=& 1+T +\sum_{n=0}^\infty F_{n+2} T^{n+2} \end{eqnarray*}$$

Check that the sum on the second line is exactly the same as that on the first. We have simply reindexed the terms. Now use the definition of the Fibonacci numbers

$$\begin{eqnarray*}f(T) &=& 1 +T +\sum_{n=0}^\infty (F_{n+1}+F_n) T^{n+2}\\ &=& 1... ..._{n=0}^\infty F_{n+1} T^{n+1} +T^2\sum_{n=0}^\infty F_n T^n \\ \end{eqnarray*}$$

Here we factored some powers of T out of the sum. Look at the last sum that appears. It is nothing other than the original Taylor expansion f(T). The first sum is f(T) minus only the very first term. Then we have

f(T)=1+T +T(f(T)-1) + T²f(T).

This equation can be solved for f(T):

$$f(T) = {1\over 1-T-T^2}.$$

The polynomial in the denominator factors into two linear terms:

$$1-T-T^2 = (1 - \left( {1+\sqrt{5}\over 2}\right) T) (1 - \left( {1-\sqrt{5}\over 2}\right) T).$$

Multiply this out to check! By the theory of partial fractions, we know that there is an expression of the form

$${1\over 1-T-T^2} = {A\over (1 - \left( {1+\sqrt{5}\over 2}\right) T)} + {B\over (1 - \left( {1-\sqrt{5}\over 2}\right) T)}.$$

Putting the right side over a common denominator, we can solve for A and B. This way we obtain

$$f(T)= {{1+\sqrt{5}\over2\sqrt{5}}\over (1 - \left( {1+\sqrt{5... ...ver2\sqrt{5}}\over (1 - \left( {1+\sqrt{5}\over 2}\right) T)}.$$

Finally, we expand this again as a Taylor series. We know the geometric series

$${1\over 1-X} = \sum_{n=0}^\infty X^n.$$

Thus, we have

$${{1+\sqrt{5}\over2\sqrt{5}}\over (1 - \left( {1+\sqrt{5}\over... ...\sum_{n=0}^\infty \left( {1+\sqrt{5}\over 2}\right)^{n+1} T^n.$$

All together, we have

$$\sum_{n=0}^\infty F_n T^n = = {1\over \sqrt{5}} \sum_{n=0}^\... ...{n+1} - \left( {1-\sqrt{5}\over 2}\right)^{n+1} \right\}\;T^n.$$

Two Taylor series are equal if and only if all their corresponding coefficients are equal. Finally we obtain the following beautiful formula for the n-th Fibonacci number

$$F_n= {1\over \sqrt{5}} \left\{\left( {1+\sqrt{5}\over 2}\right)^{n+1} - \left( {1-\sqrt{5}\over 2}\right)^{n+1} \right\}.$$

Now, $(1+\sqrt{5})/2 = 1.61...$ and $(1-\sqrt{5})/2 = -.61...$. Thus, the n-th power of the latter number tends to 0 as n tends to $\infty$, while the n-th power of the former tends to infinity. Take ratios and conclude that

$$\lim_{n\to \infty} {F_{n+1}\over F_n} = \lim_{n\to \infty} {... ...\sqrt{5}\over 2}\right)^{n+1}} = {1+\sqrt{5}\over 2} \;\; !!!!$$