## Wednesday, February 06, 2008

### The Intimate Relationship of the Golden Ratio and Fibonacci Numbers

The Golden Ratio is all around us. You can find it in art, architecture, and algorithms (and that's just the A's!). We define the Golden Ratio as the ratio between the sum of two quantities and the larger of the same two quantities such that it is equal to the ratio between the larger one and the smaller, as in the following diagram. [1] The Golden Ratio, φ = (1 + √5)/2 = 1.6180... , is an irrational number. We can't make an integer ratio to represent it fully, but we can approximate it with one. The ratio of successively larger and larger Fibonacci Numbers gets closer and closer to the Golden Ratio.

1/1 = 1
2/1 = 2
3/2 = 1.5
5/3 = 1.667
8/5 = 1.6
13/8 = 1.625
21/13 = 1.615
...
F(n)/F(n-1) = φ ; as n-> ∞
φ = 1.6180...

Really, this should be no surprise, as the golden ratio and the Fibonacci Series are intimately linked. Other than the first two defined terms, F(0) = 0 and F(1) = 1, the series is defined by the relation F(n) = F(n-1) + F(n-2). If you divide both sides by F(n-1), you get the relation

F(n)/F(n-1) = 1 + F(n-2)/F(n-1)

the left side of which is immediately apparent as the successive approximation of φ (above) that converges to φ at n->∞. However, this new equation provides a better understanding of why a ratio of successive Fibonacci numbers converges on φ.

Define φn = F(n)/F(n-1), and φn-1 = F(n-1)/F(n-2). If you substitute these two definitions into the previous equation, you get:

φn = 1 + 1/φn-1

Each time you iterate through that equation, the approximation for φn gets better and better (i.e. it converges on φ). This iterative process (called fixed point iteration) can be demonstrated graphically. Let the left and right sides of the iterative equation be represented by F(φ) and G(φ), respectively. (note: F(φ) is not the same function as F(n), given earlier) Both F(φ) and G(φ) are plotted on the same graph in the image below.

The first value for F(φ) = 2 is the first valid value shown, taken from the ratio of the Fibonacci numbers 2/1. This gets used as the seed value for G(2) = 1.5, with a line drawn from F(φ) directly to G(φ). The next iteration uses F(1.5) = 1.5 (which is the ratio of the Fibonacci numbers 3/2), and G(1.5) = 1.666... , and so on. This iterative algorithm that converges on the Golden Ratio is exactly representative of successive ratios of Fibonacci numbers. Illustrative lines are drawn on the graph below to demonstrate how the algorithm converges on φ. As the iterations approach infinity, φn = φn-1 = φ = 1.6180...

Using the same equation for the iterative solution of φ, φn = 1 + 1/φn-1, for n->∞ it can simply be said:
φ = 1 + 1/φ

The positive root of this equation is φ = (1 + √5)/2, which was stated at the beginning of the article. By algebraically solving this equation (via the quadratic method) you get an algebraic irrational solution. By using the iterative method, you quickly converge on a finite n-digit approximation.

This method is also able to give you an approximation for φ in any base of your choosing. Here it was done in decimal, but it could be in binary, sexagesimal, or even base φ, as well! (In a later post I will examine the interesting features of using base φ [2])

What might not be immediately apparent until represented with this iterative method is that it doesn't matter if the sequence of values are the Fibonacci Sequence, only a Fibonacci-esque sequence. You can start with any two unique initial values (>0) for the sequence, not just 0 and 1. For instance, starting with the arbitrarily chosen numbers 42 and 1729, you get a sequence of values of {42, 1729, 1771, 3500, 5271, 8771, 14042, ...}, and a sequence of successive approximations as follows:

1729/42 = 41.667...
1771/1729 = 1.024...
3500/1771 = 1.976...
5271/3500 = 1.506...
8771/5271 = 1.664...
14042/8771 = 1.601...

As you can see, the choice of the initial two values are largely irrelevant, as it is the definition of the iteration itself from which convergence on the golden ratio springs.

So whenever you see something in math that appears related to another something, there's usually a good demonstrable reason for it. It's not typically a coincidence.

Burton MacKenZie www.burtonmackenzie.com

[1] This image is declared to be in the public domain at the Wikimedia Commons.

[2] Base φ was first examined by Bergman in 1957 (he referred to it as Tau). Bergman, G. "A Number System with an Irrational Base." Math. Mag. 31, 98-110, 1957/58