Continued fractions have been studied for over two thousand years, with one of the first recorded studies being that of Euclid around 300 BC (in his book Elements) when he used them to find the greatest common divisor of two integers (using what is known today as the Euclidean algorithm).
Since then, continued fractions have shown up in a variety of other areas, including, but not limited to,
There are two types of continued fractions:
- finite continued fractions
- infinite continued fractions.
A finite continued fraction is a general representation of a real number in the form
where and are integers and .
An infinite continued fraction is a general representation of a real number in the form
where and are integers.
An infinite continued fraction representation of a real number is in some ways analogous to its decimal expansion. For instance, the equation means that the sequence of truncated decimals converges to Similarly, an infinite continued fraction
is simply the limit (if it exists) of the sequence of truncated continued fractions
When the and are integers, these truncated continued fractions are all rational numbers, just as the truncated decimal expansions are.
Continued fractions have many beautiful properties related to rational approximation, with numerous applications, including solutions to Pell's equation.
Above, continued fractions were defined by two sets of integers and .
Now, if we set , then they are called simple continued fractions.
An infinite simple continued fraction representation of a real number is in the form
where is an integer, and are positive integers. This is often written more compactly in the following ways:
Similarly, a finite simple continued fraction representation of a real number is in the form
As noted above, a finite simple continued fraction is a rational number. The converse is also true, i.e. any rational number can be converted to a finite simple continued fraction, via the Euclidean algorithm: if then and the process continues by dividing by Here is an illustrative example.
Reduce to a simple continued fraction.
First, write down the Euclidean algorithm for dividing by
Using this, we have
Note that the result of the computation can be read off from the quotients in the Euclidean algorithm:
Assuming that equals some real number, find the number.
So but clearly so is the golden ratio .
Here is another example:
Assuming it exists, find the value of
so because it is positive.
As with rational numbers, this process can be reversed.
Write as a simple continued fraction.
The idea is to iterate the process of taking the greatest integer and reciprocating, as follows:
and the process repeats.
This gives the continued fraction
These examples motivate the following theorem about periodic continued fractions.
Let be a real number, and suppose is an infinite simple continued fraction expansion of where the are integers, with positive. Then the sequence of is periodic (that is, there is a positive integer such that for sufficiently large ) if and only if is the root of a quadratic polynomial with integer coefficients.
This gives a complete description of the real numbers with periodic simple continued fraction expansions. In the special case the expansion has many other special and useful properties, related to the solutions to Pell's equation see the Pell's Equation wiki for details.
This section gives an overview of some of the useful general properties of simple continued fractions, with a focus on the problem of rational approximation: what are the "best" approximations of an irrational number by a rational number?
Let be a real number. If is rational, there is a unique sequence of integers, with positive and such that Otherwise, if is irrational, there is a unique infinite sequence of integers, with positive, such that This equality means that the sequence of truncated continued fractions converges to
Let and be given by the following recursive formulas:
Then equals the truncated continued fraction
The fractions are called the convergents to the irrational number
Find the convergents to the golden ratio
In this case, since the continued fraction is the recursive formula is and similarly for So the numerators and denominators of the convergents are consecutive terms of the Fibonacci sequence:
The theorem says that these fractions converge to the golden ratio.
The continued fraction for starts out Find the first four convergents to
Applying the formulas, we get The second convergent should look somewhat familiar, and the fourth convergent is less well-known but is an amazingly good approximation to : Notice that it is less than from even though its denominator is only
The intuition behind this is that is especially large, and the difference between the fourth and fifth convergent is especially small, since it corresponds to adding to the bottom-most denominator of the fourth convergent.
This approximation was known to, and used by, Chinese mathematicians in the century AD.
The next section expands on the ideas in the previous example, giving some general properties of convergents and approximation.
Let be an irrational real number and let be its convergents. Then
and are on opposite sides of ; the convergents "bounce back and forth" on the left and right side of on the number line.
Note that the left side of this equality is exactly the sum of the two quantities in the previous inequality.
Of any consecutive pair of convergents and at least one satisfies the inequality Note that the previous inequality implies that they both satisfy
If then must be a convergent.
If then That is, the convergents are "best" approximations to in the sense that no other rational number with smaller denominator can get closer to (Note that not all best approximations in this sense are convergents, but all convergents are best approximations.)
If has the property that is smaller than for any then must be a convergent; and conversely all convergents have this property. (So in this alternate sense of best approximation, convergents are exactly the best approximations.)
This theorem gives a comprehensive picture of the special nature of convergents and their use in giving effective approximations to real numbers.
There are other recursive expressions similar to continued fractions that are occasionally useful in applications.
One application of general continued fractions is an alternate approximation of square roots, using the following identity:
Start with Factor the LHS: Divide both sides by Replace in the fraction with the RHS: and this process can be continued infinitely.
Truncating these continued fractions gives a sequence converging to which may not converge as fast as the simple continued fraction, but has the advantage that no computation is required to write down the general continued fraction.
The formula gives and the truncated continued fractions give a sequence that converges to Note that it appears to be going much slower than the sequence of convergents to the simple continued fraction which are