Eureka

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

Call the first element u₁, the second one u₂, the third u₃, and so on. The sequences starts with two 1s, then each subsequent element is the sum of the two preceding ones:

u₁ = u₂ = 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 φ, a simple calculation shows its value:

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² - x - 1 = ( x - φ)(x - φ') = x² - (φ + φ')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:

φ² = φ + 1
φ³ = φ² + φ
φ⁴ = φ³ + φ²
φ⁵ = φ⁴ + φ³
    .
    .

These expressions imply that 1, φ, φ², φ³, φ⁴, φ⁵ ... 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, φ', φ'², φ'³, φ'⁴, φ'⁵ ... 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₁ and S₂ is a sequence S:

S = aS₁ + bS₂

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₁ and S₂.

The idea is to let S₁ be the φ Fibonacci-like sequence and S2 the φ' sequence and then choose a and b so that:

aS₁ + bS₂ = 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
        = (φⁿ / √5) - (φ'ⁿ / √5)

This is the Binet formula giving the Fibonacci numbers as powers of φ and φ'. The dominant term is φⁿ / √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:

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² = 1 ⋅ 2 - 1
2² = 1 ⋅ 3 + 1
3² = 2 ⋅ 5 - 1
5² = 3 ⋅ 8 + 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 ² = (½)² + 1²
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 = φ² - φ
φ² - φ - 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:

φ² = φ² + 1² - 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² = φ² + 1² - 2⋅φ⋅1⋅cos(β)

φ² = 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.

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

Internet Developer Certificate
IT Department
Madison Area Technical College

May 17, 2010