Here is the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Call the first element u_{1}, the second one u_{2}, the third u_{3}, and so on. The sequence starts with two 1s, then each subsequent element is the sum of the two preceding ones:

u_{1} = u_{2} = 1

u_{n+2} = u_{n+1} + u_{n}, n ≥ 1.

Defining something in terms of itself is called *recursion*, a major concept in Computer Science and Mathematics.

Fact 1: (3/2)⋅u_{n} ≤ u_{n+1} ≤ (2/1)⋅u_{n}, all n

Fact 2: (8/5)⋅u_{n} ≤ u_{n+1} ≤ (5/3)⋅u_{n}, n ≥ 4

These formulas can be proven by induction, as can similar ones, walking up the sequence for the constants. It turns out that as n increases, u_{n+1} / u_{n} oscillates around a fixed value, which they approach ever more closely. That is, u_{n+1} / u_{n} converges as n → ∞. Assuming convergence to some fixed value φ (proof here), a simple calculation shows its value:

u_{n+2} = u_{n+1} + u_{n} |
(defining formula) |

u_{n+2} / u_{n+1} = 1 + u_{n} / u_{n+1} |
(divide by u_{n+1}) |

φ = 1 + 1 / φ | (taking limits) |

φ^{2} = φ + 1 |
(multiply by φ) |

This last is a quadratic equation in φ, which has two real roots:

φ = (1 + √5) / 2 = 1.618034 ...

φ' = (1 - √5) / 2 = -0.618034 ...

The positive root is the one we're looking for, so Lim_{n → ∞} ( u_{n+1} / u_{n}) = φ. φ is called the *Golden Ratio* or the *Golden Section* and is one of the most well-known constants in mathematics.

Because φ and φ' are roots of the same quadratic equation, we have some simple relations between them:

x^{2} - x - 1 = ( x - φ)(x - φ') = x^{2} - (φ + φ')x + φφ';

Therefore φ + φ' = 1 and φφ' = -1.

We want to find a formula for the n^{th} Fibonacci number. To this end, consider the following statements, the first from the definition of φ and then multiplying by φ at each step:

φ^{2} = φ + 1

φ^{3} = φ^{2} + φ

φ^{4} = φ^{3} + φ^{2}

φ^{5} = φ^{4} + φ^{3}

.

.

These expressions imply that 1, φ, φ^{2}, φ^{3}, φ^{4}, φ^{5} ... is a Fibonacci-like sequence, in that every element from the third on is the sum of the two previous elements. It differs from the standard Fibonacci sequence by starting with (1, φ) instead of (1, 1), and of course the values are not integers (amazingly enough, they approach integers as n increases). The same argument applies to φ', so 1, φ', φ'^{2}, φ'^{3}, φ'^{4}, φ'^{5} ... is also a Fibonacci-like sequence.

Here is a key point: *a linear combination of two Fibonacci-like sequences is also a Fibonacci-like sequence*, a fact easily proven by induction. A "linear combination" of two sequences S_{1} and S_{2} is a sequence S:

S = aS_{1} + bS_{2}

where a and b are any real numbers and it is understood that the n^{th} element of S is calculated as suggested from the n^{th} elements of S_{1} and S_{2}.

The idea is to let S_{1} be the φ Fibonacci-like sequence and S2 the φ' sequence and then choose a and b so that:

aS_{1} + bS_{2} = standard Fibonacci sequence

All that is needed is to identify the first two elements on each side, because such sequences are completely determined by the first two elements:

a + b = 1

φa + φ' b = 1

This is a system of two equations in two unknowns a and b. Solving results in:

a = φ / √5

b = -φ' / √5

∴ u_{n} = aφ^{n-1} + bφ'^{n-1}

= (φ / √5)φ^{n-1} - (φ' / √5)φ'^{n-1}

= (φ^{n} / √5) - (φ'^{n} / √5)

This is the Binet formula giving the Fibonacci numbers as powers of φ and φ'. The dominant term is φ^{n} / √5, which approaches the approximated Fibonacci number closer and closer as n increases. The second term is the adjustment, negative and positive in turns, which approaches zero. It is amazing that such a complex formula involving √5 produces integers, much less the Fibonacci numbers. √5 plays the role of a book-keeping mechanism, collecting integer parts just right and so that the terms involving √5 cancel in the end. Here are the two key formulas derived so far:

\[ \lim_{n \to \infty} {u_{n+1} \over u_n} = {{1 + \sqrt{5}} \over 2} \]

\[ u_n = {1 \over \sqrt{5}} \left( {1 + \sqrt{5} \over 2} \right) ^n - {1 \over \sqrt{5}} \left( {1 - \sqrt{5} \over 2} \right) ^n, \hspace{20pt} n \geq 1 \]

**4) Fibonacci Formulas.**

There are thousands of Fibonacci formulas, many proved by Mathematical Induction. Consider this:

1 + 1 = 2

1 + 1 + 2 = 4

1 + 1 + 2 + 3 = 7

1 + 1 + 2 + 3 + 5 = 12

It seems that the sum of the Fibonacci numbers up to a certain point equals the Fibonacci number two further minus 1. This is indeed the case. Here is another pattern:

1^{2} = 1 ⋅ 2 - 1

2^{2} = 1 ⋅ 3 + 1

3^{2} = 2 ⋅ 5 - 1

5^{2} = 3 ⋅ 8 + 1

Here are these two formulas in mathematical notation:

\[ \sum_{k=1}^{n} u_k = u_{n + 2} - 1 \]

\[ u_n^2 = u_{n - 1} u_{n + 1} + (-1)^{n - 1} \]

**5) The Golden Section.**

A *Golden Rectangle* has sides in proportion φ : 1. Construct as follows. Start with a square of side 1 and bisect the bottom edge into two parts of length 1/2. Draw a circle centered at the point of bisection going through the upper right corner. Extend the bottom edge of the square to the right to intersect the circle and build a rectangle as shown to the right of the square. The width of the larger rectangle is φ:

r ^{2} = (½)^{2} + 1^{2}

r = √5 / 2

width = r + ½ = (√5 + 1) / 2 = φ

There is more -- the smaller rectangle just tacked on to the right of the square is also a golden rectangle! This is because its dimensions are 1 : ( φ - 1) and these steps are reversible:

1 / (φ - 1) = φ / 1

1 ⋅ 1 = φ (φ - 1)

1 = φ^{2} - φ

φ^{2} - φ - 1 = 0

Build an isosceles triangle with base 1 and taller equal sides φ as shown, the tall triangle in the middle with base angle α. The Law of Cosines says:

φ^{2} = φ^{2} + 1^{2} - 2⋅φ⋅1⋅cos(α)

Simplifying: 2⋅φ⋅cos(α) = 1

cos(α) = 1 / (2φ) = 0.309016

α = cos^{-1}(1 / (2φ)) = 72°

Therefore, the triangle with sides φ - φ - 1 has angles 72° - 72° - 36°. 72° is one fifth of a circle, so right there you know you can construct a regular pentagon. But let's proceed with *this* construction. Build two more isosceles triangles outwards based on the tall sides, with arms of length one. The entire figure is an equilateral pentagon, all sides of length one by construction. To show that it is a regular pentagon, it remains only to show that all the pentagonal angles are equal.

Again apply the Law of Cosines to one of these new triangles with base angle β:

1^{2} = φ^{2} + 1^{2} - 2⋅φ⋅1⋅cos(β)

φ^{2} = 2⋅φ⋅cos(β)

cos(β) = φ / 2 = 0.809016

β = cos^{-1}(φ / 2) = 36°

The new triangles have side 1 - 1 - φ and angles 36° - 36° - 108°. Simple calculations then show that all pentagonal angles equal 108° and that the figure is therefore a regular pentagon. I've got more on the regular pentagon here.

The regular dodecahedron, much beloved by the ancient Greeks and taken up at the end of Euclid's Elements, is also implicated. It's twenty corners are given by these Cartesian coordinates in an xyz system, where the edge length is 2/φ = √5–1 and the circumscribing sphere has radius √3:

(±1, ±1, ±1)

(0, ±1/φ, ±φ)

(±1/φ, ±φ, 0)

(±φ, 0, ±1/φ)

- Mike Bertrand

IT Department

Madison Area Technical College

May 17, 2010

^ Update (Jan 6, 2014): Proceed as follows to prove that the ratios \(u_{n + 1}/u_n\) have a limit as \(n \to \infty\). Let \(\phi_n = u_{n + 1}/u_n\):

\[ \phi_n = {{1 \over 1}, {2 \over 1}, {3 \over 2}, {5 \over 3}, {8 \over 5}, {13 \over 8}, {21 \over 13}, {34 \over 21}} \dots \]

First show that \(1 \leq \phi_n \leq 2\). This is evidently true for the first few elements of the sequence, so assume true for some value of *n*. Then:

\[ \phi_{n+1} = {u_{n+2} \over u_{n+1}} = {{u_{n+1}+u_n} \over u_{n+1}} = 1 + {u_n \over u_{n+1}} = {1 + {1 \over \phi_n}} \]

Taking reciprocals of the inductive hypothesis and then adding 1 gives:

\[ {1 \over 2} \leq {1 \over \phi_n} \leq 1 \]

\[ {3 \over 2} \leq {1 + {1 \over \phi_n}} \leq 2 \]

Thus \(1 \leq \phi_{n+1} \leq 2\), and the result follows for all *n*.

The fractions jump around when advancing through the sequence, but look at *every other* one: \(\phi'_n = 1/1, 3/2, 8/5, 21/13 , \dots \). They are monotonically increasing, at least the first few, eg.:

\[ \phi_5 = {8 \over 5} < {21 \over 13} = \phi_7 \]

\[ 104 = {8 \cdot 13} < {5 \cdot 21} = 105 \]

The difference of one between the two products pops out and in fact this is always the case:

\[ {u_k \cdot u_{k + 3}} - {u_{k + 2} \cdot u_{k + 1}} = -1, \hspace{20pt} k \text{ even} \]

We'll prove the more general result:

\[ {u_k \cdot u_{k + 3}} - {u_{k + 2} \cdot u_{k + 1}} = {(-1)}^k, \hspace{20pt} k \geq 1 \hspace{60pt} \text{(1)} \]

which proves not only that \(\phi'_n\) is monotonically increasing, but also that the subsequence interspersed with that one, \(\phi''_n = 2/1, 5/3, 13/8, 34/21 , \dots \), is monotonically *decreasing*. So assume the inductive hypothesis (1) for some k. Then expanding the first term \(u_k\):

\[ {{(u_{k + 2} - u_{k + 1})} \cdot u_{k + 3}} - {u_{k + 2} \cdot u_{k + 1}} = {(-1)}^k \]

\[ { {u_{k + 2} \cdot u_{k + 3}} - {u_{k + 1} \cdot u_{k + 3}} - {u_{k + 2} \cdot u_{k + 1}}} = {(-1)}^k \]

\[ {{u_{k + 2} \cdot u_{k + 3}} - {u_{k + 1} \cdot {(u_{k + 3} + u_{k + 2})}}} = {(-1)}^k \]

Substituting \(u_{k + 4}\) for \(u_{k + 3} + u_{k + 2}\) and rearranging a bit gives:

\[ {-{u_{k + 1} \cdot u_{k + 4}} + {u_{k + 2} \cdot u_{k + 3}} } = {(-1)}^k \]

Multiplying through by -1 gives (1) with k + 1 instead of k, completing the proof of (1). So \(\phi'_n\) is increasing and bounded above by 2, hence has a limit less than or equal to 2. Similarly \(\phi''_n\) is decreasing and bounded below by 1, so has a limit greater than or equal to 1.

(1) compares two fractions from \(\phi_n\) that are *two apart*. There is also a relation for adjacent elements of \(\phi_n\) exemplified by:

\[ \phi_7 = {21 \over 13} < {34 \over 21} = \phi_8 \]

\[ 441 = {21^2} < {13 \cdot 34} = 442 \]

The formula is the one mentioned at the end of section 4 above:

\[ u_n^2 = u_{n - 1} u_{n + 1} + (-1)^{n - 1} \]

and is proven by induction similarly to (1). Therefore, for any two adjacent fractions \(\phi_n\) and \(\phi_{n + 1}\):

\[ {\phi_{n + 1} - \phi_n} = {{u_{n + 2} \over u_{n + 1}} - {u_{n + 1} \over u_n} = { {u_{n + 2} \cdot u_n - u_{n + 1} ^2} \over {u_{n + 1} \cdot u_n } } } = { {(-1)}^{n + 1} \over {u_{n + 1} \cdot u_n }} \rightarrow 0 \text{ as } n \rightarrow \infty \]

For odd n, \(\phi_{n + 1}\) is an element of the decreasing sequence \(\phi''_n\) and \(\phi_n\) is the analogous element of the increasing sequence \(\phi'_n\) and they are as close as you like, but with the first greater than the second. This shows that all the elements of \(\phi'_n\) are less than all those of \(\phi''_n\) and that their limits are the same. That is, the original sequence \(\phi_n\) has a limit. QED