The word 'fraction' derives from the Latin fractio - to break. However, there are continuous fractions.
Well, not quite. The accepted terminology is continued fraction. However, one of the Russian terms for what I want to discuss on this page is indeed continuous fraction. Continued fraction are extremely important in the theory of rational approximation. They also provide a simple way to construct a variety of transcendental numbers. Here's the definition.
In general, continued fraction is an expression in the form
where a_{i} and b_{i} may be any kind of numbers, variables, or functions. With all
We shall only be concerned with the latter variety. A more convenient notation is
3796 = 1387·2 + 1022
which also can be written as
3796/1387 | = 2 + 1022/1387 |
= 2 + 1/(1387/1022). |
The key step of the algorithm is exactly this: "Keep dividing the smaller number 1387 into the larger one." Thus, let's continue
1387/1022 | = 1 + 365/1022 |
= 1 + 1/(1022/365). |
In other words,
3796/1387 | = 2 + 1022/1387 |
= 2 + 1/(1 + 1/(1022/365)). |
Further
1022 = 365·2 + 292
365 = 292·1 + 73
292 = 73·4
Omitting parentheses (as is customary), we may write
3796/1387 | = 2 + 1022/1387 |
= 2+1/1+ 1/(1022/365) | |
= 2+1/1+1/2+ 1/(365/292) | |
= 2+1/1+1/2+1/1+1/4. |
Finally, 3796/1387 = [2;1,2,1,4]. The above explains why the terms a_{i} are usually called quotients.
Also, it shows that every rational number can be associated with a finite continued fraction. On the other hand,
given a finite fraction [a_{0};a_{1},a_{2},a_{3},...,a_{n}], we may as well carry
out the arithmetic operations in the reverse order. Which will ultimately lead to a rational number r. Since, obviously,
Irrational numbers can also be uniquely associated with (simple) continued fractions. Take an irrational r and denote
a_{k} = [r_{k}]
r_{k} = 1/(r_{k-1} - a_{k-1}),
where k > 1 (with the convention that r_{0} = r.) We can write
r = [a_{0};r_{1}] = [a_{0};a_{1},r_{2}] = [a_{0};a_{1},a_{2},r_{3}] ...
Quite naturally the terms r_{i} are called remainders. Note that, since, for an irrational r,
As we see, the association between real numbers and continued fractions is defined recursively. It will come then as no surprise that many of the features of the continued fractions are expressed in recursive terms. For example, for a continued fraction (either finite or infinite) one defines a family of finite segments
Theorem 1
For all k ≥ 2,
(1) | p_{k} = a_{k}p_{k-1} + p_{k-2} |
(2) | q_{k} = a_{k}q_{k-1} + q_{k-2} |
Set p_{-1} = 1 and q_{-1} = 0. First subtracting (2) multiplied by p_{k-1} from (1) multiplied by q_{k-1} and then subtracting (2) multiplied by p_{k-2} from (1) multiplied by q_{k-2} we further get
Theorem 2
For all k ≥ 0,
(3) | q_{k}p_{k-1} - p_{k}q_{k-1} = (-1)^{k} |
(4) | q_{k}p_{k-2} - p_{k}q_{k-2} = (-1)^{k-1}a_{k} |
(3) and (4) can be rewritten as
(3') | s_{k} - s_{k-1} = (-1)^{k-1}/(q_{k}q_{k-1}) |
(4') | s_{k} - s_{k-2} = (-1)^{k}a_{k}/(q_{k}q_{k-2}) |
It's about time I start drawing some conclusions.
- From (2), q_{i} grows with i.
- All fractions s_{k} with k >1 are irreducible. This follows from (3); for a common factor of p_{k} and q_{k} would divide 1.
- From (4'), if k is even, s_{k} is an increasing sequence. For k odd, s_{k} decreases.
- From (3'), if k is even, s_{k} < s_{k-1}. If k is odd, the reverse inequality holds.
- Combining 3. and 4. we get
s_{0} < s_{2} < s_{4} < ... < s_{2n} < ... < s_{2n-1} < ... < s_{5} < s_{3} < s_{1}
- Therefore, s_{k} converges both for even and odd indices. From 1. and (3') the limits coincide. Thus, s_{k} is a convergent sequence. It's a gratifying fact that the sequence converges to r. For this reason the fractions s_{k} are known as Convergents. Let's prove this. As we know,
r = [a_{0};a_{1},...,a_{k-1},r_{k}]
Therefore,
(5) | r = (p_{k-1}r_{k} + p_{k-2})/(q_{k-1}r_{k} + q_{k-2}), k > 1. |
On the other hand, obviously
(6) | s_{k} = (p_{k-1}a_{k} + p_{k-2})/(q_{k-1}a_{k} + q_{k-2}), k>1 |
From (5) and (6)
which implies
which, in view of 1., not only proves that s_{k} converges to r but also gives an estimate for the rate of convergence. Note that this is the same inequality we once proved using the Pigeonhole principle. The new proof supplies a constructive way to approximate an irrational number.
Examples
- r = [1;1,1,1,...] = 1 + 1/r. Therefore, r is the positive root of
r^{ 2} = r+1. Thus the golden ratio(1 + √5)/2 has the simplest continued fraction representation possible. - Similarly, you can find [2;2,2,2,...] and, in general, [n;n,n,...].
- r = [1;2,2,2,...] can be found once you know [2;2,2,...]. But there is another way. r-1 = [0;2,2,2,...] whereas r+1 = [2;2,2,2,...]. Therefore
(r - 1)(r + 1) = 1. Orr = √2. - r = [1;1,2,1,2,1,2,...]. Similar to the above, r+1 = [2;1,2,1,2,...] whereas
r-1 = [0;1,2,1,2,...]. Letr_{1} = [1;2,1,2,...]. Then (r+1) = [2;r_{1}] = 2·r_{1}. On the other hand,(r-1) = [0; r_{1}] = 1/r_{1}. Thus we get(r+1)(r-1) = 2. Finally,r = √3. All of the above fractions are periodic in the sense we apply to decimal fractions. Le comte J. L. Lagrange (1736-1813) proved that this is a characteristic property of roots of quadratic polynomials.
The next two examples are due to S. Ramanujan, one of the greatest mathematical geniuses. Being a poor uneducated clerk, in 1913 Ramanujan sent a letter to
G. H. Hardy who was by this time a world famous mathematician. He was accustomed to receiving letters from cranks. So he was bored more than anything else. Then it dawned on him that "They must be true because, if they were not true, no one would have had the imagination to invent them." The examples below were among 120 theorems from the Ramanujan's letter and are specifically referred to in the above passage.- The following couple belongs to L. Euler
Note: a non-judicious use of continued fractions may lead to contradictions.
|Contact| |Front page| |Contents| |Did you know?|
Copyright © 1996-2018 Alexander Bogomolny66195931