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 b_i=1 we have simple continued fractions.

We shall only be concerned with the latter variety. A more convenient notation is r = [a₀,a₁,a₂,a₃,...]. To end with notations, if a₀ is an integer, most often it's separated from the rest of the coefficients with a semicolon: r = [a₀;a₁,a₂,a₃,...]. In the following, I shall assume that all a_i are integers and, for i>0, a_i>0.

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₀;a₁,a₂,a₃,...,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, [a₀;a₁,a₂,a₃,...,a_n,1] = [a₀;a₁,a₂,a₃,...,a_n+1], let's agree to exclude the finite fractions with the last quotient equal to 1. With this convention, the correspondence between rational numbers and finite continued fractions becomes 1-1.

Irrational numbers can also be uniquely associated with (simple) continued fractions. Take an irrational r and denote a₀ = [r], where [] is the floor function. Next write r = a₀ + 1/r₁, where r₁ = 1/(r - a₀). Continue in this fashion: a₁ = [r₁] and r₂ = 1/(r₁ - a₁), and more generally

where k > 1 (with the convention that r₀ = r.) We can write

Quite naturally the terms r_i are called remainders. Note that, since, for an irrational r, 1 > r - [r] > 0, r₁ = 1/(r - [r]) is also irrational and r₁>1. The same is true for k > 1: all r_k are irrational and r_k > 1. Therefore the process never stops and leads to a uniquely defined infinite continued fraction for which a_k > 0 for k>0. Note that with thus defined correspondence r₁ = [a₁,r₂] = [a₁,a₂,r₃] = ..., r₂ = [a₂,r₃] = ..., and so on.

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 s_k = [a₀;a₁,a₂,...,a_k], each s_k being a rational number: s_k= p_k/q_k with q_k > 0. Then we have the following fundamental theorem that can be proven by induction.

Theorem 1

For all k2,

(2)	pk = akpk-1 + pk-2
(2)	qk = akqk-1 + qk-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 k0,

(3)	qkpk-1 - pkqk-1 = (-1)k
(4)	qkpk-2 - pkqk-2 = (-1)k-1ak

(3) and (4) can be rewritten as

(3'1)	sk - sk-1 = (-1)k-1/(qkqk-1)
(4')	sk - sk-2 = (-1)kak/(qkqk-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

s0 < s2 < s4 < ... < s2n < ... < s2n-1 < ... < s5 < s3 < s1

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 = [a0;a1,...,ak-1,rk]

Therefore,

(5)	r = (pk-1rk + pk-2)/(qk-1rk + qk-2), k > 1.

On the other hand, obviously

(6)	sk = (pk-1ak + pk-2)/(qk-1ak + qk-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

1. r = [1;1,1,1,...] = 1 + 1/r. Therefore, r is the positive root of r ² = r+1. Thus the golden ratio (1 + 5)/2 has the simplest continued fraction representation possible.
2. Similarly, you can find [2;2,2,2,...] and, in general, [n;n,n,...].
3. 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. Or r = 2.
4. 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,...]. Let r₁ = [1;2,1,2,...]. Then (r+1) = [2;r₁] = 2·r₁. On the other hand, (r-1) = [0; r₁] = 1/r₁. 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.

5. 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.

6. The following couple belongs to L.Euler

Fibonacci Numbers

1. Ceva's Theorem: A Matter of Appreciation
2. When the Counting Gets Tough, the Tough Count on Mathematics
3. I. Sharygin's Problem of Criminal Ministers
4. Single Pile Games
5. Take-Away Games
6. Number 8 Is Interesting
7. Curry's Paradox
8. A Problem in Checker-Jumping
9. Fibonacci's Quickies

Golden Ratio

1. Golden Ratio in Geometry
2. Golden Ratio in an Irregular Pentagon
3. Golden Ratio in a Irregular Pentagon II
4. Inflection Points of Fourth Degree Polynomials
5. Wythoff's Nim
6. Inscribing a regular pentagon in a circle – and proving it
7. Cosine of 36 degrees
8. Continued Fractions

Copyright © 1996-2009 Alexander Bogomolny