Continued fraction

A continued fraction is an expression such as

<math>x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3}}} </math>

where a₀ is some integer and all the other numbers a_n are positive integers. The above expression is abbreviated as x = [a₀; a₁, a₂, a₃]. Longer expressions [a₀; a₁, a₂, ..., a_n] are defined analogously. One may also define infinite continued fractions as limits:

<math>[a_{0}; a_{1}, a_{2}, a_{3}, ... ] = \lim_{n \to \infty} [a_{0}; a_{1}, a_{2}, ..., a_{n}] </math>

This limit exists for any choice of positive integers a₁, a₂, a₃ ...

Occasionally, two different finite continued fractions represent the same number, for instance [2; 3, 1] = [2; 4] = 9/4 = 2.25. Every finite continued fraction is rational, and every rational number can be represented in precisely two different ways as a finite continued fraction. Every infinite continued fraction is irrational, and every irrational number can be represented in precisely one way as an infinite continued fraction.

An infinite continued fraction representation for an irrational numbers is mainly useful because its initial segments provide excellent rational approximations to the number. These rational numbers are called the convergents of the continued fraction. Even-numbered convergents are smaller than the original number, while odd-numbered ones are bigger. For example, to calculate the convergents of pi, we set a₀ = [π] = 3 (where [x] denotes the largest integer ≤ x), define u₁ = 1/(π - 3) ≈ 113/16 = 7.0625 and a₁ = [u₁] = 7, u₂ = 1/(u₁ - 7) ≈ 31993/2000 = 15.9965 and a₂ = [u₂] = 15, u₃ = 1/(u₃ - 15) ≈ 1003/1000 = 1.003. Continuing like this, one can determine the infinite continued fraction of π as [3; 7, 15, 1, 292, 1, 1, ...]. The third convergent of π is [3; 7, 15, 1] = 355/113 = 3.14159292035... which is fairly close to the true value of π.

Let us suppose that the quotients found are, as above, [3; 7, 15, 1]. The following is a rule by which we can write down at once the convergent fractions which result from these quotients without developing the continued fraction.

The first quotient, supposed divided by unity, will give the first fraction, which will be too small, namely, 3/1. Then, multiplying the numerator and denominator of this fraction by the second quotient and adding unity to the numerator, we shall have the second fraction, 22/7, which will be too large. Multiplying in like manner the numerator and denominator of this fraction by the third quotient, and adding to the numerator the numerator of the preceding fraction, and to the denominator the denominator of the preceding fraction, we shall have the third fraction, which will be too small. Thus, the third quotient being 15, we have for our numerator (22 · 15 = 330) + 3 = 333, and for our denominator, (7 · 15 = 105) + 1 = 106. The third convergent, therefore, is 333/106. We proceed in the same manner for the fourth convergent. The fourth quotient being 1, we say 333 times 1 is 333, and this plus 22, the numerator of the fraction preceeding, is 355; similarly, 106 times 1 is 106, and this plus 7 is 113.

In this manner, by employing the four quotients [3; 7, 15, 1], we obtain the four fractions:

<math>\frac{3}{1}, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \ldots</math>

The fractions are alternately smaller and larger than the true value of π, and have the advantage of approaching nearer and nearer to its value in such wise that no other fraction can approach it nearer except the denominator be larger than the product of the denominator of the fraction in question and the denominator of the fraction following. For example, the fraction 22/7 is more than the true value, but it approaches to it nearer than any other fraction does whose denominator is not greater than the product of 7 by 106, that is 742.

The demonstration of the foregoing properties is deduced from the fact that if we seek the difference between one of the convergent fractions and the next adjacent to it we shall obtain a fraction of which the numerator is always unity and the denominator the product of the two denominators. Thus the difference between 22/7 and 3/1 is 1/7, in excess; between 333/106 and 22/7, 742, in defect; between 355/113 and 333/106, 1/11978, in excess; and so on. The result being, that by employing this series of differences we can express in another and very simple manner the fractions with which we are here concerned, by means of a second series of fractions of which the numerators are all unity and the denominators successively be the product of every two adjacent denominators. Instead of the fractions written above, we have thus the series:

<math>\frac{3}{1}+\frac{1}{1 \cdot 7}-\frac{1}{7 \cdot 106}+\frac{1}{106 \cdot 113} \cdots </math>

The first term, as we see, is the first fraction; the first and second together give the second fraction, 22/7; the first, the second and the third give the third fraction 333/106, and so on with the rest; the result being that the series entire is equivalent to the original value.

While one cannot discern any pattern in the infinite continued fraction expansion of π, this is not true for e, the base of the natural logarithm: e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, ...].

The numbers with periodic continued fraction expansion are precisely the solutions of quadratic equations with integer coefficients. For example, the golden ratio φ = [1; 1, 1, 1, 1, 1, ...] and √ 2 = [1; 2, 2, 2, 2, ...].

See also:

• Mathematical constant/Alternative sorting

References

A. Ya. Khinchin; Continued Fractions; University of Chicago Press.