The first lemma says that the denominators of convergents of continued fractions increase.
Lemma. Let , , , ... be a sequence of integers, where for . Define
Then for .
Proof. Let . Note that is a positive integer. So
where because the a's are positive integers from on.
The convergents of a continued fraction oscillate around the limiting value, and the convergents are always fractions in lowest terms. In fact, the convergents are the best rational approximations to the value of the continued fraction. I'll state the precise result without proof.
Theorem. Let x be irrational, and let be the k-th convergent in the continued fraction expansion of x. Suppose , , and
Then .
Here's what the result means. Draw the line through the origin in the t-y plane with slope x. Plot the points and .
The hypothesis says that the vertical distance from to is less than the vertical distance from to .
The conclusion says that . In fact, since , : The denominator of is bigger than that of .
In other words, the only way the point can be closer to the line is if its y-coordinate is bigger.
I can restate the theorem in the form of a corollary in which you can see the fractions in question approximating x.
Corollary. Let x be irrational, and let be the k-th convergent in the continued fraction expansion of x. Suppose , , and
Then .
Proof. Given the hypotheses of the corollary, suppose on the contrary that . Since
I can multiply the two inequalities to get
Apply the theorem to obtain . But then , which contradicts the fact that the q's increase.
Therefore, .
This result says that the only way a rational number can approximate a continued fraction better than a convergent is if the fraction has a bigger denominator than the convergent.
Example. Here are the convergents for the continued fraction expansion for :
, which is in error in the seventh place. The theorem says that a fraction can be closer to than only if .
The next result is sort of a converse to the previous two results. It says that if a rational number approximates an irrational number x "sufficiently well", then the rational number must be a convergent in the continued fraction expansion for x.
Theorem. Let x be irrational, and let be a rational number in lowest terms with . Suppose that
Then is a convergent in the continued fraction expansion for x.
Proof. Since for , the q's form a strictly increasing sequence of positive integers. Therefore, for some k,
Since , the contrapositive of the preceding theorem gives
Hence,
Now assume toward a contradiction that is not a convergent in the continued fraction expansion for x. In particular, , so , and hence is a positive integer.
Since ,
(The second inequality comes from the Triangle Inequality: .)
Subtracting from both sides, I get
But I assumed , so this is a contradiction.
Therefore, is a convergent in the continued fraction expansion for x.
Example. Show that is the best rational approximation to by a fraction having a denominator less than 1000.
Suppose that is a fraction in lowest terms that is a better approximation to than , and that .
Since is a fraction is a better approximation to than ,
Since ,
But
Thus,
The hypotheses of the theorem are satisfied, so must be a convergent in the continued fraction expansion of .
But the other convergents with denominators less than 1000 --- 3, , --- with denominators less than 1000 are poorer approximations to than .
Hence, is the best rational approximation to by a fraction having a denominator less than 1000.
Example. (a) Compute the first 6 convergents , ... of the continued fraction for .
(b) Show that is the best rational approximation to having denominator less than 155.
(a)
(b) Suppose that is a fraction in lowest terms which is a better approximation to than , and also that .
Since is a better approximation to than ,
Since ,
So I have
(The inequalities are approximate, but there is enough room between and that there is no problem.)
By the approximation theorem, is a convergent for . But no convergent with is a better approximation than .
This contradiction shows that is the best rational approximation to having denominator less than 155.
Copyright 2017 by Bruce Ikenaga