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 y_{0} = u.
- Suppose that y_{n} has been calculated. If it is an integer, then let a_{n} = y_{n} and stop. Otherwise, let a_{n} be the “floor” of y_{n} (the greatest integer not exceeding y_{n}), and y_{n+1} = 1/(y_{n}−a_{n}), and continue.
We see that, if the ratio of the two lengths is rational, then Euclid’s procedure will terminate, and the integers a_{0}, a_{1}, … 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 a_{0}, a_{1}, …, where all except possibly the first are positive. Let x_{n} be the continued fraction [a_{0},a_{1},…a_{n}]. Then it can be shown that the rational numbers x_{n} converge to a limit as n→∞, and we can define this limit to be the value of the infinite continued fraction.
Now we have [a_{0};a_{1},…] = a_{0}+1/[a_{1};…]. 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 x_{n} 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
x_{0} | = | [1;] | = | 1/1 | = | 1, |
x_{1} | = | [1;1] | = | 2/1 | = | 2, |
x_{2} | = | [1;1,1] | = | 3/2 | = | 1.5, |
x_{3} | = | [1;1,1,1] | = | 5/3 | = | 1.666…, |
x_{4} | = | [1;1,1,1,1] | = | 8/5 | = | 1.6, |
x_{5} | = | [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 x_{n} = p_{n}/q_{n} is the nth convergent, then no fraction with denominator q_{n} or smaller is closer to u than x_{n} is. Furthermore, we will see shortly that the difference between u and x_{n} is smaller than the difference between x_{n+1} and x_{n}, which can be shown to be 1/(q_{n}q_{n+1}).
The denominators q_{n} satisfy the recurrence relation
q_{n+1} = a_{n}q_{n}+q_{n−1}.
The numerators p_{n} satisfy the same recurrence relation, but with different initial conditions. Thus, x_{0} = a_{0} and x_{1} = a_{0}+1/a_{1}, so we have
p_{0} | = | a_{0}, | p_{1} | = | a_{0}a_{1}+1, | |
q_{0} | = | 1, | q_{1} | = | a_{1}. | |
We see from the recurrence that, in fact, the difference between u and its approximation p_{n}/q_{n} is smaller than 1/(q_{n}^{2}). We say that we have an “approximation to order 2” for u.
The difference between u and x_{n} 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
(|x_{n+1}−x_{n}|)/2 ≤ |u−x_{n}| ≤ |x_{n+1}−x_{n}|.
When all the a_{n} 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 a_{n} 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 a_{n} is very large, then q_{n} is very much larger than q_{n−1}, and so the convergent x_{n−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:
x_{0} | = | 3 | = | 3/1 |
x_{1} | = | 3+1/7 | = | 22/7 |
x_{2} | = | (15·22+3)/(15·7+1) | = | 333/106 |
x_{3} | = | (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,…]
Pingback: On Fibonacci numbers and the golden ratio « Maximal determinant blog
Pingback: Weekly links for March 25 | God plays dice