## Fibonacci numbers, 4

In the preceding post in this series, we saw a connection between the Fibonacci numbers and the golden ratio α = (1+√5)/2. I am going to look at this from a different perspective, that of continued fractions.

The simplest continued fractions are expressions like 1+1/(2+1/(3+1/4)). Since counting brackets becomes tedious, I will write this as [1;2,3,4], just giving the numbers which occur first in the denominators. We can easily evaluate such an expression “from the bottom up”: 3+1/4 = 13/4, then 2+4/13 = 30/13, and finally 1+13/30 = 43/30.

To go in the other direction, given any rational number m/n, we use Euclid’s algorithm for the greatest common divisor. This algorithm has been taught to generations of students. Given a fraction like 43/30, we divide the denominator into the numerator, obtaining a quotient and a remainder. Then we successively divide the remainder at the preceding step into the divisor at the preceding step until the division goes exactly; the last divisor is the greatest common divisor of the two numbers. Thus,

 43 = 1·30+13 30 = 2·13+4 13 = 3·4+1 4 = 4·1

So the greatest common divisor of 43 and 30 is 1. We also obtain the continued fraction by simply reading off the successive quotients 1, 2, 3, 4.

Euclid and his contemporaries thought in terms of geometry rather than arithmetic or algebra. He phrased the algorithm like this. To divide m by n, assume that you are given two line segments with lengths m and n. Using the compass set to measure the distance n, lay out as many copies of this along the other segment as will fit. The number of copies is the quotient, and the piece left over is the remainder. Repeat the procedure until the smaller interval fits a whole number of times into the larger; then the interval you just used is the “greatest common divisor” of m and n, in the sense of being the largest interval of which m and n are exact multiples.

If the ratio m/n is equal to u, the algorithm can be expressed as follows:

• Set y0 = u.
• Suppose that yn has been calculated. If it is an integer, then let an = yn and stop. Otherwise, let an be the “floor” of yn (the greatest integer not exceeding yn), and yn+1 = 1/(ynan), and continue.

We see that, if the ratio of the two lengths is rational, then Euclid’s procedure will terminate, and the integers a0, a1, … give the continued fraction for this ratio. If the algorithm doesn’t terminate, then the ratio is irrational.

If we divide a line segment into two pieces in such a way that the ratio of the whole line to the larger is equal to the ratio of the larger to the smaller, then this ratio is the golden ratio. Letting α be the golden ratio, we see that α/1 = 1/(α−1), so α2−α−1 = 0. Solving this quadratic and taking the positive solution gives the value α = (1+√5)/2, as claimed. After one step in Euclid’s algorithm, the ratio of the two lengths is 1/(α−1) = α/1, that is, is exactly the same as it was at the start. So the algorithm “spins its wheels” and never terminates; thus, the golden ratio is irrational.

(The historian of mathematics David Fowler speculated that the Pythagorean proof of the irrationality of √2 went along these lines rather than the “proof by contradiction” that is standard textbook fodder today. A simple geometric argument shows that Euclid’s algorithm also “spins its wheels” on 1+√2.)

We see also that, if we attempt to compute the continued fraction for α, every quotient is equal to 1, so the result is [1;1,1,1,…]. This “infinite continued fraction” can be given a rigorous interpretation.

Take any sequence of integers, say a0, a1, …, where all except possibly the first are positive. Let xn be the continued fraction [a0,a1,…an]. Then it can be shown that the rational numbers xn converge to a limit as n→∞, and we can define this limit to be the value of the infinite continued fraction.

Now we have [a0;a1,…] = a0+1/[a1;…]. So the value α of the continued fraction with every entry 1 satisfies α = 1+1/α, giving us the same quadratic (and hence the same value of α) as before.

The numbers xn are called the convergents to the infinite continued fraction, since they do indeed converge to its value. In the case of the continued fraction for α=1.618…, the convergents are

 x0 = [1;] = 1/1 = 1, x1 = [1;1] = 2/1 = 2, x2 = [1;1,1] = 3/2 = 1.5, x3 = [1;1,1,1] = 5/3 = 1.666…, x4 = [1;1,1,1,1] = 8/5 = 1.6, x5 = [1;1,1,1,1,1] = 13/8 = 1.625,

and so on; an easy induction shows that the convergents are the quotients of consecutive Fibonacci numbers. So the ratio of consecutive Fibonacci numbers converges to α.

This is not the end of the story.

Every real irrational number u has a continued fraction, which is generated by Euclid’s algorithm. It can be shown that the convergents to this continued fraction are “best rational approximations” to u, in the sense that, if xn = pn/qn is the nth convergent, then no fraction with denominator qn or smaller is closer to u than xn is. Furthermore, we will see shortly that the difference between u and xn is smaller than the difference between xn+1 and xn, which can be shown to be 1/(qnqn+1).

The denominators qn satisfy the recurrence relation

qn+1 = anqn+qn−1.

The numerators pn satisfy the same recurrence relation, but with different initial conditions. Thus, x0 = a0 and x1 = a0+1/a1, so we have

 p0 = a0, p1 = a0a1+1, q0 = 1, q1 = a1.

We see from the recurrence that, in fact, the difference between u and its approximation pn/qn is smaller than 1/(qn2). We say that we have an “approximation to order 2” for u.

The difference between u and xn is also at least half of this estimate. This is because the differences alternate in sign; the even-numbered convergents are all smaller than u and increase, while the odd-numbered convergents are greater than u and decrease; the differences betweem u and the convergents decrease in absolute value. The pattern is illustrated by the convergents to the golden ratio α given above. This alternation explains why

(|xn+1xn|)/2 ≤ |uxn| ≤ |xn+1xn|.

When all the an are equal to 1, this reduces to the Fibonacci recurrence, as it should. But we also see that the smallest possible denominators occur when all the an are equal to 1. Of course, smaller denominators mean larger difference between u and its approximations. The conclusion can be stated like this:

The golden ratio is the irrational number which is hardest to approximate by rational numbers.

I will say something about the significance of this in the next exciting instalment.

Before leaving this, I mention one curiosity. We see from the recurrence for the denominators that, if the value an is very large, then qn is very much larger than qn−1, and so the convergent xn−1 is a very good approximation to u. Now the continued fraction for π begins [3;7,15,1,292,1,…]. So the convergents [3;7] = 22/7 and [3;7,15,1] = 355/113 are unexpectedly good approximations to π. The latter differs from π by only about 0.000000266764189…. These approximations to π have been known since ancient times.

The calculations run as follows, using the recurrence relations for numerator and denominator of the convergents:

 x0 = 3 = 3/1 x1 = 3+1/7 = 22/7 x2 = (15·22+3)/(15·7+1) = 333/106 x3 = (1·333+22)/(1·106+7) = 355/113

It is not known whether there is a “pattern” in the numbers occurring in the continued fraction for π; it may be that the future performance of the stock market is encoded more accurately in the continued fraction than in the decimal digits. As a cautionary tale, however, there is a simple pattern to the continued fraction for the second most famous irrational number, Euler’s number (the base for natural logarithms):

e = [2;1,2,1,1,4,1,1,6,1,1,8,1,…] 