Chapter IV

Chapter IV

4.1.1 The Gulf Between the Finite and the Infinite As you can already evaluate terminating continued fractions, you will now learn how to deal with non-terminating ones. Interest in such extensions are the background of all scientific endeavour.

Any rational number can be converted into a terminating continued fraction. Conversely, any terminating continued fraction represents a rational number. Could it be that non-terminating fractions yield the means for representation of irrational numbers?

Quite a few mathematical concepts which are familiar to you in finite form have intriguing infinite analogues. Several examples follow.

The meaning of decimal fractions is quite clear. For example, 0.33 denotes 33/100. But what is the meaning of 0.333···*?

* An ellipsis (···) is a mathematical symbol with two meanings. With a formula (for example,
1+x+x²···+xⁿ), it denotes a certain number of omitted terms, at the end (for example, 1+x+x²+ ···) it denotes and so on to infinity. Ellipses can also replace entire rows.

The sum of a finite number of terms is also readily understood. For example, 1 + 1/2 + 1/4 = 7/4. But what about 1 + 1/2 + 1/4 + 1/8 + ···?

There are finite polynomials such as 1 + 2x + 3x². But can you operate with polynomials with an infinite number of terms such as 1+x+x²+···+xⁿ+···?

In spite of the apparent similarity, finite and infinite quantities are separated by a deep and wide gulf. Mathematicians overlooked this gulf until the 19th Century. Ignoring the dangers, they treated infinite objects in the same way as finite ones and sometimes obtained absurd results. In the 19th Century, the way for dealing with the infinite was discovered gradually and reliable bridges were erected across the separating gulf. Let us walk across one of these bridges.

Note that a terminating decimal fraction is in no way different from an ordinary fraction; the only difference is the notation. The fraction 0.33 has the numerator 33 and the denominator 100. But what is the numerator of the non-terminating fraction 0.333···? We do not yet know the answer to this question, which indicates clearly that a non-terminating decimal fraction does not have the meaning carried by a terminating one. N.N. Luzon used to say that drawing a symbol 0.333··· does not impart a meaning to this symbol. It remains but a pattern. However, we can give this symbol a meaning.

The sum 1 + 1/2 + 1/4 has a meaning, because we can calculate it by successive additions: 1 + 1/2 = 3/2, 3/2 + 1/4 = 7/4. But we cannot determine the infinite sum 1 + 1/2 + 1/4 + 1/8 + ··· by this method, because the process of consecutive additions will never terminate. And this is not a technicality, but a basic obstacle. It would be frivolous to hide behind the argument that successive additions of terms in 1 + 1/2 + 1/4 + 1/8 + ··· yield approximate values of the infinite sum. You cannot look for what does not exist! The meaning of infinite sums must first be defined; only afterwards can we speak of approximate values of such sums.

We promised to cross the gulf between the finite and the infinite by one of many bridges. Its name is the Principle of Nested Segments or Cantor's Continuity Axiom*.

*Georg Cantor (1845-1918) created the Theory of Aggregates (Set Theory) which became the foundation of all of mathematics.

4.1.2 Principle of Nested Segments It is often said that the number line is continuous. Mathematicians always have to seek logically impeccable statements which replace intuitive notions. The Principle of Nested Segments is the axiom which expresses precisely that property of the number line which is called continuity.

Recall that a segment was defined as a set of points of a number line which consists of two distinct points a and b (called the ends of the segment) and all the points between a and b. A segment is denoted by [a,b]. A set including all the points between a and b but not the points a and b themselves is called the interval and is denoted by (a,b). The interval (a,b) contains two points less than the segment [a,b] and in certain cases this difference is extremely important. If one of the end points is added to the set of points between a and b, the result is a half-closed interval. The same symbol can be used to denote a point of the number line and the number corresponding to it. Thus

segment [a,b]: a £ x £ b;
interval (a,b): a < x < b;
half-closed interval [a,b): a £ x < b;
half-closed interval (a,b]: a < x £ b.

Consider on the number line the sequence of segments

[a₁,b₁], [a₂,b₂], ··· [a_n,b_n], ···

with the properties: 1. each segment (beginning with the second one) is nested in the preceding one, 2. the length of the segments tends to zero (as n ® ¥).

Property 1 means that all the points of the nth segment belong to the (n-1)th segment (Fig. 10).

Property 2 says that for an arbitrary fixed length e there exists a number n such that the length of th segment [a_n,b_n] is smaller than e (and the segments with greater numbers are obviously even shorter).

Then there exists a unique point which belongs to all segments.

A compact reformulation of the axiom is:

Cantor's Continuity Axiom If an infinite sequence of segments is given on a straight line such that 1. each next segment is nested within the preceding one , 2. the length of the segments tends to zero, then there exists a unique point which belongs to all the segments.

Consider the axiom in greater detail. Fig. 10 shows the first few segments of the sequence. Define the nth step as the transition from the nth to the (n+1)th segment. For example, Point A in Fig. 10 belongs to the first, but not the second segment. Hence this point will be eliminated at the first step of the process. Point B will survive the first step, but is eliminated at the second step. Point C survives the first two steps, but exits at the third step, etc. Each point of the segment [a₁,b₁] has its own fate. Some fall inside the 1000th segment, but stay outside the 1001th segment. These points have survived 1000 steps, but are eliminated at the 1001th step.

The principle of nested segments implies that there exists the point X which will never be eliminated, that is, it survives each step; in other words, it belongs to any segment regardless of its number.

The axiom states that such a point exists. As regards the uniqueness of this point, it was introduced in the same formulation for the sake of convenience and is readily proved. In fact, assume that there exist two such points: X and Y. Let d denote the distance between them. It has been demanded that the length of the segments of the sequence tends to zero. Find a number n such that the length of the segment [a_n,b_n] is less than d:

[a_n,b_n] < d.

Then the segment [a_n,b_n] cannot cover the segment XY = d, that is, both the points X and Y cannot belong to the segment [a_n,b_n] (and those following it). Hence it has been proved that there cannot exist two points belonging to all segments.

Example 1. Consider the following segments on the number line:

Obviously, the point 1/2 and only this point belongs to all of these segments.

Example 2. Let there be given the sequence of segments

Point 0 and only it belongs to all of the segments.

Each of the examples deals with a sequence of nested segments. The unique point common to the segments was readily selected. The principle of nested segments states that such a point exists always, however the sequence has been generated the two stated conditions.

Note: If we had considered in Example 2 the sequence of intervals

(0,1), (0,1/2), (.0,1/3), ··· , (0,1/n), ···,

it would not contain a point common to all the intervals, although they are nested and their lengths tend to zero. In fact, the point 0 does not belong to any of them, while any other point of the interval (0,1) will be left out at some step.

Hence it is essential that Cantor's axiom be applied to segments. A similar statements would not apply to intervals.

The principle of nested segments expresses the continuity of the number line: Segments converge to a point of the line, not to a hole. Break the continuity of the line by piercing it at the point 1/2, that is, remove the point 1/2 from the number line. The remaining set of points M cannot be called a line. It is an assemblage of two open rays, that is, rays without vertices (-¥,1/2) and (1/2,¥). Following Example 1, consider now a sequence of segments which are not segments of a line, because they lack one point, but segments on a set M. Each of them contains two ends and all the points of the set M between them. The Principle of nested Segments does not apply to M!

4.1.3 The Set of Rational Numbers Consider the process of gradually filling in the number line with numbers. To start with, mark all integers. By tradition, the set of all integers is denoted by Z. There is no need for subtle arguments to shows that the points of the set Z do not fill completely the number line. Any two integers are separated by a solid mass of points (an interval) which hitherto has not yet been named.

The next step is to mark the rational numbers. It will be sufficient to mark all rational numbers within the interval between 0 and 1. All rational points on the number line will then be obtained by displacements of the segment [0,1] to the left hand side and the right hand side an integral number of times.

Mark the rational numbers on the segment [0,1] in the following manner:

Step 1. Mark all fractions with the denominator 2. There is only the single 1/2.

Step 2. Mark all fractions with the denominator 3, arranging them in the order of increasing numerators: 1/3, 2/3.

Step 3. Mark all fractions with the denominator 4, arranging them in ascending order: 1/4, (2/4), 3/4. The fraction 2/4 = 1/2 is in brackets, because this number has appeared before.

························································································

Step (n-1) Mark all fractions with the denominator n, arranging them in ascending order: 1/n, 2/n, 3/n, ··· , (n-1)/n. If any fractions are reducible to lower terms, previously encountered, they are crossed out!

···························································································

This process is infinite. Although it cannot be completed, it is sure to mark all rational numbers in the interval between 0 and 1. In fact, does there exist a fraction the turn of which will never come? Select an arbitrary fraction in this interval, say, 37/89. Obviously, at some step of marking fractions with denominators 2, 3, 4, ··· (namely at the 88th step), the denominator 89 will have been reached. Then, arranging the fractions in ascending order, 1/89. 2/89. 3/89. etc. will occur until 37/89 turns up. Hence, whatever fraction between 0 and 1 is selected, it will certainly be reached and marked off on the segment [0,1]. Displacement of these points by 1, 2, 3, ··· to the right and to the left, will mark all rational numbers. In the sequel, this set will be denoted by Q.

4.1.4 Existence of Non-rational Points on the Number Line. Is the number line filled completely by the points of the set Q? No, it is not! Some of the points of the line do not belong to Q; they are not rational. However, this is not as obvious as for the set Z, and subtle arguments are required to clarify this case. Pythagoras is reputed to have made the great discovery: There exists no number* the square of which equals 2. An equivalent formulation is: The diagonal of a square is in-commensurate with its side. If all rational points are marked on the number line (Fig. 11), the arc of a circle the radius of which is the diagonal of the square OA passes freely through the number axis without intersecting the set Q.

* In fact, no arational number. The qualification has not been made, because you do not yet know any other numbers!

Nevertheless, on the number line, the set Q is everywhere dense . This means that any segment of the number line, however short, contains rational points. Consequently, even though rational points do not exhaust the number line, this line does not contain segments which would be absolutely free of rational points. This can be readily proved if you recall how you proceeded to mark the rational points on the segment [0,1].

Consider next sequences of nested segments

[a₁,b₁], [a₂,b₂], ··· , [a_n,b_n], ···

on the set Q (that is, the ends of the segments are rational points). The principle of nested segments does not hold on the set Q. Even if the conditions of Cantor's continuity axiom are met, there may not exist a point in Q which belongs to all these segments. It will be seen below that this fact can be used to invent numbers of a new type: Irrational numbers.

4.1.5 Non-terminating Decimal Fractions By terminating such a fraction after each decimal place, you obtain the left ends of segments. Adding unity to the last decimal place, you find the right ends of the segments. For example, the fraction 0.313131 ··· denotes the sequence of nested elements on the set Q:

[0.3;0.4], [0.31;0.32]; [0.313;0.314], ···.

Each step reduces the length of these segments by a factor of 10, whence the length tends to zero, regardless of the fraction selected.

Consider two examples which are superficially alike, but in fact differ profoundly.

Example 1: The non-terminating periodical decimal 0.333 ··· represents the sequence of nested segments:

[0.3;0.4], [0.33;0.34]; [0.333;0.334], ···.

Is there a point which belongs to all these segments? Here and in what follows , a point is to lie in Q. Undoubtedly, there is such a point on the number line. It is the point x = 1/3.

There hold the inequalities:

0.3 < 1/3 < 0.4;
0.33 < 1/3 < 0.34;
0.333 < 1/3 < 0.334;
································

(15)

Hence the number 1/3 is said to be the value of the non-terminating fraction 0.333 ···. A formal definition of this concept will be given below, but first consider

Example 2: Form two sequences: a. The largest decimal with 0, 1, 2, ···, n, ··· decimal places the square of which is less than 2; b. The least decimal the square with 0, 1, 2, ···, n, ··· decimal places of which is larger than 2. Step by step, you find

1² < 2		but	2² > 2²
1.4² < 2		"	1.5² > 2²
1.41² < 2		"	1.42² > 2
··············	···	·····	··············

You can continue this process indefinitely. Is there a point in Q which belongs to all the segments

[1;2], [1.4;1.5], 1.41,1.42], ··· ?

In other words, does there exist a rational number x which satisfies each of the inequalities:

1		£ x £		2
1.4		£ x £		1.5	(16)
1.41		£ x £		1.42
······	···	··········	···	·········

[Note that the sign £ (not <) has been used and, because you are looking for point belonging to the segment, that is, a point which may coincide with one of the ends. Accidentally, the number in Example 1 is always within a segment. If you had started with the fraction 0.2000 ···, corresponding to the number 1/5. you would have to use the sign £.

It is well known that there does not exist a rational number which satisfies all the inequalities (16). This means that any rational number would violate the inequalities (16), beginning with some line. It also means that the corresponding non-terminating fraction 1.414 213 6 ··· determined by the process described above is meaningless.

Now the time has arrived to present the lacking meaning.

4.1.6 Irrational Numbers The notation 1/3 can be interpreted in two ways: a. As a fraction 1/3, that is, as the ratio of the two natural numbers 1 and 3 or b. as a non-terminating decimal 0.333 ···, that is, as the common point of the nested segments

[0.3;0.4], [0.33;0.34], [0.333;0.334], ···.

The first interpretation does not apply to the required number x which is sought with the inequalities (16). However, this number corresponds to a non- terminating decimal, that is, the system of nested segments

[1;2], [1.4;1.5], [1.41; 1.42], ···..

Let us agree that this non-terminating decimal or, what is the same thing, this system of nested segments defines a number. It is a number of a new type: It cannot be presented as a ratio of natural numbers and is called irrational.

In order to clarify the idea of the introduction of irrational numbers, recall that the infinite sequence of nested segments (15) defines a number. It happens to be the rational number 1/3. We can operate with it, ignoring the sequence (15).

The infinite sequence of nested segments (16) also defines a number, but the type of this number is not yet familiar to you (it is assumed that you only know rational numbers) and those known to you appear as the sequence (15).

4.1.7 Real Numbers The name for rational and irrational numbers is real numbers R; it is the union of the sets of rational and irrational numbers.

When the concept of number is extended and generalized, the old numbers should be treated as particular cases of a broader concept instead of being opposed to the new numbers. In other words, there must be a universal principle of formation and universal notation for all real numbers.

The universal notation, also constituting the universal method of formation, is that adopted for non-terminating decimals.

Certain rational numbers can be presented as terminating decimals. However, let us agree, in order to have a universal notation for all real numbers, to convert any decimal into a non-terminating decimal. This can be done in two ways, for example,

0.5 = 0.5000···,
0.5 = 0.4999.

For the unique representation of every real number by a non-terminating decimal, adopt the

Convention: It is forbidden to use non-terminating decimals with the number 9 as period. Then the number 0.5 can only be written as a non-terminating decimal in the unique manner: 0.5000···.

With this convention, every real number is written as a non-terminating decimal fraction in a unique manner, that is, no two distinct non-terminating decimals can represent the same real number.

We emphasise now that this definition actually identifies a real number as a non-terminating decimal fraction. Certain real numbers can be written in other ways. For example, rational numbers can be represented by common fractions. Roots of natural numbers are denoted by Ö 2, Ö 3, ···. Finally, certain numbers have been given individual (personal) symbols: p, e, etc. However, non-terminating decimals yield a universal method of forming and presenting real numbers.

The method of introduction of real numbers does not create the set R out of the air. It assumes that a certain subset of R, namely the set of all terminating decimals, already, exists. The method admits supplementation of this set to R by means of nested segments the ends of which are given by terminating decimals. Real numbers can be defined differently; if you fo not start from the set of terminating decimals, but from some other set which is everywhere dense on the number line.

You would make a mistake if you were thinking that the theory of real numbers has already been constructed. The above definition of real numbers is only a first step. Many more steps would be required to construct the theory, namely ordering of real numbers (i.e., finding a method for the comparison of magnitudes), defining operations with real numbers (addition, multiplication, etc. ), just to name a few. However, this aspect will not be further treated here. The purpose of this sub-section is to clarify the principle of nested segments, to be used for the interpretation of non-terminating continued fractions.

4.1.8 Representation of Real Numbers on the Number Line Let there be given a positive real number

x = a₀, a₁a₂ ··· a_n. (17)

This is the decimal notation, where a₀is an arbitrary non-negative integer and the remaining a_iare numerals from 0 to 9. A terminating decimal fraction

obtained by omission of the numerals beginning with a_n+1in (17), is called the approximate value of x with n decimal places by defect. If you add 1 to the last decimal

you obtain the approximate value of x with n decimal places in excess. If a_n=9, the 1 can change the preceding numerals. For example, for x=892/900=0.99111···, you find = 0.99, = 1.00.

Disregarding the logical foundation, we can write down the obvious inequalities

We ask now: Why is the sign on the left-hand side of the inequality £, while that on the right hand side is < ? Can they be reversed the preceding definitions are modified?

The following fact is of great importance: If all the real numbers are marked on the number line, the line is completely covered. A better formulation of this statement follows and will be proved:

Theorem 1 Every real number corresponds to a unique point of the number line.

Proof: Consider a positive real number x = a₀, a₁a₂a₃···. It belongs to an infinite sequence of nested intervals

The lengths of these segments form a geometric progression with the common ratio 1/10. By Cantor's continuity axiom, the number line contains a unique point belonging to all these segments. This is the point which corresponds to the number x.

Theorem 2 Every point of the number line corresponds to a unique real number.

Proof: Let a point x be given on the number line (x lying somewhere on the positive side of the axis). If x is an integer, no further proof is required. Otherwise, x lies between two neighbouring integers a₀ and a₀ + 1. Start the decimal notation of the number x with its integral part, that is,

x = a₀···.

Divide the segment (a₀; a₀+ 1) into ten equal parts. If x does not coincide with any one of the ten division points, it will be found between a₀,a₁ and a₀,a₁+ 1. Extend the decimal presentation of x:

x = a₀,a₁ ···

and subdivide the segment [a₀,a₁;a₀,a₁ + 0.1] into ten equal parts.

If at some step of this process the point x coincides with one the subdivision points, then

x = a₀,a₁a₂ ··· a_n 000··· .

If there is no coincidence, then

x = a₀,a₁a₂ ··· a_n ···

and x lies strictly inside all the segments (n = 0, 1, 2, ··· ).

Corollary The set R obeys the principle of nested segments.

4.1.9 Condition of Rationality of Non-terminating Decimals. We know from high school mathematics that each rational number can be expressed by a periodical (pure or mixed) decimal . For example,

1/3 = 0.333 ···; 13/90 = 0.1444 ···; 1/5 = 0.2000 ···.

Conversely, Every periodical decimal expresses a rational number, whence it follows that each irrational number is expressed by a non-periodical non-terminating decimal. For example, using the algorithm for extracting square roots, you can find any desired number of digits in the decimal representing Ö2:

Ö2 = 1.4142135 ···.

We can always find one additional digit of the sequence. And although we do not know the formal law for the generation of this sequence of digits (i.e. cannot find a function j (n) yielding the nth decimal), we are sure that this fraction is not periodical.

Conversely, every non-periodical decimal is an irrational number. For example, consider the fraction

0.1010010001...,

where the number of 0s between two consecutive 1s increases each time by 1. This fraction is non-periodical, whence it stands for an irrational number. In this example, the formal law for the sequence of numerals is quite simple; if u_n is the nth decimal, then

4.2 Non-terminating Continued Fractions

4.2.1 Numerical Value of a Non-terminating Continued Fraction

By terminating the non-terminating continued fraction [a₀;a₁,a₂,a₃,···] after every successive term, generate the consecutive convergents

Although a non-terminating continued fraction is only a symbol to which no numerical value is assigned, convergents are rational numbers. They define an infinite sequence of nested segments

It has already been mentioned that the denominators of convergents strictly increase (cf. (6)):

However, Equation (13) then yields

The difference between neighbouring convergents tends to zero! In such statements, it is always assumed that n ® ¥.

Each segment (18) is nested within the preceding one (cf. Fig. 8). By Cantor's continuity axiom, there exists a unique point on the number line or, in other words, a unique real number which belongs to all these segments. It is this number which we define as the value of the - conti- continued fraction.

This definition implies the corollaries:

1. The value of a nonterminating continued fraction lies between any two neighbouring convergents.
2. All even-numbered and odd-numbered convergents are approximate values by defect and and excess, respectively, of non-terminating continued fractions. Look again at Fig. 9. If the continued fraction is non-terminating, the broken line does not have the last segment the end of which lies on the dashed horizontal line. The broken line has an infinite number of vertices which in turn fall above and below the dashed line; a is the value of the non-terminating continued fraction.

3. The sequence of the even-numbered convergents

increases monotonely and tends to a on the left hand side, that of the odd-numbered convergents

decreases and tends monotonely to a on the right hand side. Look carefully at the sequence of Segments (18) above. Their ends are rational numbers. In the present notation, the first entry is alternately a left and a right end. This is obviously of no principal importance.

4.2.2 Representation of Irrationals by Non-terminating Continued Fractions You have already learned the algorithm for the expansion of a real number into a continued fraction. Let this algorithm now be applied to an irrational a ; we obtain a non-terminating continued fraction [a₀; a₁, a₂, a₃, ···]. Earlier this continued fraction was said to correspond to the number

a = [a₀; a₁, a₂, a₃, ···].

Now we know how to determine the value of non-terminating continued fractions. There arises naturally the question: Does a or another number give the numerical value of [a₀; a₁, a₂, a₃, ···]? In other words, is the correspondence between a and [a₀; a₁, a₂, a₃, ···] symmetrical? Answer: Yes, it is!

Indeed, the convergents obtained in the process of expanding a into a continued fraction are alternately greater and smaller than a. For example, consider the first two steps of the process:

a = a₀ + 1/x₁,

whence

a₀< a .

Moreover,

x₁, = 1/(a - a₀) = a₁ + 1/x₂,

whence

1/(a - a₀) > a₁, a - a₀ < 1/a₁, a < a₀ + 1/a₁.

As a result,

a₀< a < a₀ + 1/a₁

or, in a different form,

p₀/q₀ < a < p₁/q₁.

This chain of arguments can be extended, that is, a lies between any two neighbouring convergents.

If you wish to reverse the arguments and find the value of the obtained non-terminating continued fraction, you must recall that, by definition, this value is the common point of all segments (18), that is, of all segments between neighbouring convergents.

However, there exists only one point which belongs to all segments (18), whence the number a and the value of the continued fraction [a₀; a₁, a₂, a₃, ···] coincide. Hence you are entitled to replace the symbol » by an equality sign:

a = [a₀; a₁, a₂, a₃, ···].

4.2.3 The Single-valuedness of the Representation of a Real Number by a Continued Fraction Do continued fractions offer universal means of representing real numbers? In other words, is it true that any real number* can be represented by a continued fraction, and in a unique manner?

* For the sake of simplicity, we assume that the numbers is positive. Nevertheless, it is clear that the answer to the question will not change for negative numbers.

The first part of the question has already been answered. Indeed, every real number can be expanded into a continued fraction: Rationals expand into terminating, irrationals into a non-terminating continued fractions, but the aspect of single-valuedness has not yet been studied.

Example:

or, in contracted notation,

[0; 6,4] = [0; 6, 3, 1].

This transformation - splitting off of 1 from the last term - can be effected in any fraction the last term of which differs from 1. If the last term is 1, it can be added to the last but one term (that is, we can read the last example from the right to the left.)

It is readily proved that this is the only reason for the lack of single-valuedness of the representation of a (positive) rational number by a continued fraction. We shall eliminate this cause by introducing the convention: The last term of a continued fraction must not be 1. From now on, we will choose the first of the two notations [0; 6, 4] and [0; 6, 3, 1] for the same number.

Theorem: Two continued fractions [a₀; a₁, a₂, ···] and [b₀; b₁, b₂, ···] (terminating or non-terminating) are equal if and only if, 1. they have identical numbers of terms 2. their respective terms coincide, that is, a₀ = b₀, a₁ = b₁, etc.

You must understand the condition they have identical terms as follows: Either both fractions are terminating and have identical numbers of terms or both of them are non-terminating.

Proof: Let a denote the value of two equal continued fractions (where we do not know whether both of them are terminating or non-terminating):

a = [a₀; a₁, a₂, ···] = [b₀; b₁, b₂, ···].

The term a₀(as well as b₀) equals E(a₀)* and thus splits off a in a single- valued manner, whence

a₀ = b₀.

* The definition of the function E(a) is: The largest integer not larger than a.. For example, E(5/2) = 2, E(1) = 1, E(-5/2) = - 3. You read the symbol E(a) The integral part of a; the letter E arises from the French word entier.

Subtract a₀from a :

a - a₀= [0; a₁, a₂, ···] = [0; b₁, b₂, ···].

and consider the reciprocal

1/(a - a₀) = [a₁; a₂, ···] = [b₁; b₂, ···].

The term a₁(and b₁) is E(1/(a - a₀), whence it is determined in a single-valued manner by the value of 1/(a - a₀) and therefore

a₁ = b₁,

etc. By repeating these arguments , it can be proved that a₂ = b₂, a₃ = b₃, etc.

Can two equal continued fractions have unequal numbers of terms? Let the first continued fraction terminate, while the second fraction either terminates with t terms, t > s, or it does not. Then

whence

which is impossible,whence t = s.

The conclusion is that every real number is uniquely expressible by a continued fraction.

This proof has employed a frequently used rule: When the expansion of a into a (terminating or non-terminating) continued fraction is known, one has to act as follows to find the expansion of 1/a :

1. If a₀ ¹ 0, move the entire comb one step to the right and insert 0 instead of the integer or
2. if a₀ = 0, move the entire comb one step to the left.

Examples

a = [3; 1, 2, 5], 1/a = [0; 3, 1, 2, 5];
b = [0; 2, 2, 2, ···], 1/b = (2; 2, 2, ···].

The proof follows from a study of the two fractions:

4.3 The nature of Numbers Given by Continued Fractions

4.3.1. Classification of Irrationals You know already the important fact: Every rational number is given by a terminating, every irrational number by a non-terminating continued fraction.

No more will be said regarding rational numbers. However, irrational numbers have very different types. Consider their classification

The equation

a₀xⁿ + a₁x^n-1+ ··· + ax_n-1 + a_n = 0 (19)

with a₀ ¹ 0 is called an algebraic equation of degree n. We shall only consider the case when all the coefficients in (19) are rational or even integers. These two cases are identical. If the coefficients are fractions, you can multiply both sides of the equation by the common denominator of these coefficients, thus obtaining an equation with integer coefficients equivalent to the initial equation.

In the discussion of (19), it will be assumed hereafter that its coefficients are integers (positive, negative, or zero). An additional constraint is imposed on the coefficient of the leading term: a₀ ¹ 0.

A real number is called an algebraic number of degree n, if the number is a root of an algebraic equation of degree n with integral coefficients, but is not a root of any other algebraic equation of lower degree with integral coefficients.

Example 1 Each rational number p/q is an algebraic number of the first degree, because it is the root of the equation

qx— p = 0.

Example 2 The number Ö 2 is an algebraic number of the second degree, because it is a root of the quadratic equation

x² - 2 = 0.

You know that Ö 2 cannot be a root of any equation of the first degree with integral coefficients, because such an equation (a₀x + a₁ = 0) has the rational root x = - a₁/a₀.

Algebraic numbers of the second degree are called quadratic irrationals.

Non-algebraic numbers have been found to exist. These numbers are called transcendental numbers. Their definition is: A real number a is said to be transcendental, if it is not a root of any algebraic equation with integral coefficients.

It is not easy to discover transcendental numbers. If you want to prove that a number a is algebraic, it is sufficient to find an algebraic equation with integral coefficients of which a is a root. However, if you cannot find such an equation, you cannot conclude that a is transcendental, for you have to prove that no such equation exists. This problem was solved for the first time by the French mathematician Joseph Liouville in 1844. He proved the transcendency of specific real numbers. In 1882, the German mathematician Ferdinand Lindemann proved that p is a transcendental number. Today, very many examples of transcendental numbers are known. For example, decimal logarithms of all rational numbers, except for numbers of the type 10¹⁰, are transcendental.

You must be warned regarding a misunderstanding. The fact that examples of transcendental numbers are difficult to find does not at all mean that they are rare. Quite the opposite is true! Georg Cantor has shown that in a certain sense (it cannot be explained here what this means) almost all real numbers are transcendental, that is, algebraic numbers are rare exceptions. However, the nature of algebraic numbers is simpler, whence many examples can be given. As regards transcendental numbers, it is always very difficult to prove their transcendence in any specific case.

4.3.2 Quadratic Irrationals You know from the preceding section that a quadratic irrational is an irrational number which is a root of a quadratic equation with integral coefficients.

The word irrational replaces the following phrase in the preceding definition: and it is not a root of any algebraic equation of lower degree with integral coefficients. In the case under consideration, this means: It is not the root. of any equation of first degree with integral coefficients", that is, it is not a rational number.

Consider the quadratic equation

a₀x² + a₁x + a₂, = 0,

where a₀, a₁, a₂ are integers and a₀ ¹ 0. Its roots are given by the formula

These roots are quadratic irrationals under the following necessary and sufficient conditions:

1. The discriminant D = a²₁— 4a₀a₂ must be non-negative. If D <0, the roots would not be real,
2. The discriminant D must not be a perfect square. If D = N², the roots would be rational.

These conditions allow to give a different definition of the quadratic irrational: A quadratic irrational is a number of a type p + qÖ D, where p and q are rational numbers and D is a natural number which is not exactly a square.

Before analysing some examples of quadratic irrationals, four useful lemmas will be proved. To start with, certain notations and definitions of certain terms will be introduced in order to eliminate repetitions.

Lower case Roman letters p, g, . . . shall always denote rationals (positive, negative, or zero). In particular, they may be integers.

Capital Roman letters D, M, N, . .. shall denote natural numbers which are not exact squares: 2,3,5,6,7,8,10,...*.

*Actually, there exists a simple method for the construction of continued fractions the values of which are transcendental numbers. However, if you face the problem of proving the transcendencc of a number which has been defined by different means {p , log 2, sin 1, etc.), this always creates a very difficult problem.

Two square-root radicals* Ö M and Ö N are said to be similar, if Ö N =pÖ M, Otherwise, that is, if the ratio Ö M/Ö N is not rational, the radicals Ö M and Ö N are not similar. For example, Ö2 and Ö8 are similar, but Ö2 and Ö10 are not.

* This is an example of common usage: The term square-root means not only the symbol Ö which stands for the operation of extraction of a square-root, but also refers to any number of the type Ö2, Ö 3, etc.

If ÖM and ÖN are not similar radicals, then ÖMN is also a square-root (i.e. it is not an exact square), not similar to either of the initial two. This is clear from the identities

Lemma 1 If ÖM and ÖN are non-similar radicals, then the equation

holds only if k =l = m = 0.

In a more concise notation,

Proof: You must consider the two cases: 1. l ¹ 0 and m ¹ 0 (for any k), 2. one of the coefficients l, m is non-zero while the other vanishes.

In the first case, shift k to the right-hand side and square both sides of the equation. After some manipulations, you obtain

that is, Ö MN is rational, which is not true. Hence, the first case cannot occur. In the second case, (20) above shows that Ö M or Ö N is a rational, which contradicts the imposed condition. Hence, the second case is also rejected.

We thus have to recognize that l = m = 0. Equation (20) then shows that also k=0.

Lemma 2: If ÖM and ÖN are non-similar radicals, then

is possible only if k = l = m = n = 0; it may be rewritten

Proof: Assume that l ¹ 0, m ¹ 0, n ¹ 0.Transform (21) into

Square both sides and obtain

that is, Ö MN is a rational, which is not true. Hence the assumption l¹0, m¹0, n¹0 must be rejected, that is, it must be assumed that at least one of the coefficients l, m, n vanishes. But then (21) reduces to (20), so that, by Lemma 1 all the remaining coefficients vanish.

Lemma 3: If p + qÖM is a root of the equation

with integral coefficients, then p—qÖ M is also a root of this equation.

Proof: Given

it has to be proved that

Remove the brackets in (22). The terms (qÖM)^a obtained come in two types: 1) a is even (including a=0). All these terms are rational. Denote their sum by k.
2) a is odd. All these terms are of the form sÖM. Denote their sum by lÖM.

Equation (32) thus becomes

Transform in a similar manner (23), obtained from (22) by substitution of —qÖM for qÖM. This substitution does not affect the terms containing even powers of qÖM, while the terms containing odd powers of qÖM only have their signs reversed. (23) thus becomes

(24) can only hold if k = l = 0.

Indeed, if l ¹ 0, (24) indicates that ÖM is rational. And if l = 0, then also k = 0. But if k = l = 0, then (25) also holds.

Recall the idea of the proof. Equations (24) and (25) are the appropriately transformed equations (22) and (23). Equation (24) yields k = l = 0, and k=l=0 implies that (25) holds.

Lemma 4: If p + qÖM+rÖN, where ÖM and ÖN are dissimilar radicals, is a root of an equation with integral coefficients, then the numbers p±qÖ M± rÖN, regardless of the combination of signs, are also roots of this equation.

In order to simplify the notations, let

Given

it has to be proved that

Proof: Remove the parentheses in (26). All the term will then have the form

where A are coefficients and a, b, g are non-negative integers. These terms arise in four different types:

After removal of the brackets in (26), you obtain

If you substitute -qÖM for qÖM, it will not change terms of TypeS 1 and 2, while Types 3 and 4 only have their signs reversed, whence, if

then

Taking similar steps with the other sign combinations, you find, if

then

if P(p + qÖM + rÖN) = 0, then, by Lemma 2, k = l = m = n = 0. But this implies that all the other values of P(p ± qÖM ± rÖN) vanish.

Example 1 The number 1 + Ö2 is a quadratic irrational. How can an equation be found which generates it?

Lemma 3 states that the number 1 - Ö2 is also a root of this equation, whence the equation is

Example 2. The number Ö2 + Ö3 is not a quadratic irrational. The equation with integral coefficients generating it has, by Lemma 4, the roots:

Hence this equation is

Note 1 If the roots are known, the equation can obviously also be found by Vieta's formulae. For the normalized equation of fourth degree

Vieta's formulae are

Note 2 You may be somewhat surprised if you try to check whether the equation indeed corresponds to the prescribed roots. In fact, the equation yields

At a first glance, this result differs from the given roots ±Ö2 ± Ö3. However, in fact, . This is readily verified either by squaring both sides of the equation or by employment of the formula for the transformation of complex roots:

(27) is only of help when A²— B is a perfect square, which is not the case in the example.

4.3.3. Euler's Theorem A non-terminating continued fraction is said to be periodical, if its terms form a periodical sequence. For example, fractions like

The first two fractions are purely periodical and the third one is a mixed periodical continued fraction. In this classification, the integral component a₀ is ignored. A more straightforward definition is:

A non-terminating continued fraction is said to be purely periodical, if there exist natural numbers N and k such that

a_n+h = a_n

for any n ³ N.

The following theorem, proved by Leonard Euler in 1737, applies to continued fractions

Theorem The value of every periodical continued fraction is a quadratic irrational.

Proof:

Example 1. You have [0; 1, 1, 1, ...], that is,

Apply an operation of rewinding, that is, 1. taking the reciprocal of each side, 2. subtracting the integral part (entier) from each side. In this particular case, these steps are only taken once:

On the right hand side, you have the initial fraction, that is a:

which yields for a the quadratic equation

whence (naturally, the negative root must be rejected.)

This analysis shows that any fraction of the type [0; a, a, a, ...] represents a quadratic irrational.

And what if the period consists not of one, but of k numerals? Then k pairs of steps will be made during rewinding.

Example 2 [0; 1, 2, 1, 2, . . .].

whence

Note that the root cannot be rational whatever the period, because the initial continued fraction is non-terminating.

However, what happens if a₀ is non-zero? In that case, shift a₀to the left-hand side and begin rewinding.

However, this method is cumbersome if the period is long. Hence another proof follows; it is not as lucid as the one the one above, but shorter.

Second proof Let a non-terminating continued fraction a = [0; a₁, a₂, ···]be pure periodical with the period length k. Then a = a_k+1 (recall that a_k+1 is the (k + 1)th complete quotient):

Equation (9) now yields

whence

that is, a satisfies a quadratic equation

The roots of this equation have opposite signs and a is the positive root.

If the fraction is a mixed periodical one,

you must first rewind from the right to the left the first part of the fraction up to and including the term a_N and then apply the above proof.

Note The number a is irrational, because !t is represented by a non-terminating continued fraction. Hence the discriminant of Equation (23) must not be an perfect square. This statement can be tested by direct evaluation:

Adding and subtracting the term 4p_kq_k-1, you obtain

Now apply (13):

Finally, you find

It is seen that D is not a perfect square. The difference between squares of natural numbers cannot be equal to 4. If the set of natural numbers is supplemented by zero, you will find a unique pair of squares spaced 4: 0 and 4.

4.3.4. Lagrange's Theorem As you have seen in the preceding section, Euler's theorem is readily proved. The proof of the inverse theorem is considerably more difficult. It was proved by Lagrange in 1770.

Lagrange Theorem. Every quadratic irrational is represented by a periodic continued fraction.

Lagrange's proof of this theorem was very complicated. Quite a few mathematicians have tried to simplify his proof. A hundred odd years later, the French mathematician Charves sugested a simpler proof, based on a different idea. We will present the detailed proof after an outline of Chavers' reasoning.

Let a be a quadratic irrational and expand it into a continued fraction, interrupting the process at each step beginning with the second step:

where a₁, a₂, ···, a_n, ··· are complete quotients. It has been shown in 3.1.5 that, if a certain complete quotient happens to be repeated, that is, if a_n = a_n+_l, then the continued fraction will be periodical.

To start with, we shall prove that each term satisfies a quadratic equation with integral coefficients:

Of course, this equation can vary for different values of a_n, and for this reason the coefficients A, B, C have been given subscripts. Rather, it should be said: Each a_n satisfies its own quadratic equation with integral coefficients.

Next, we shall prove that the magnitudes of the coefficients in (29) are bounded:*

* We assume that a quadratic equation with integral coefficients is written in a form which cannot be reduced to lower terms. Otherwise, this would be meaningless.

Here is Charves' clever idea. The bounds L, M, N are independent of n (they depend exclusively on a). Since A_n, B_n, C_n are integers, there exist only a finite number of admissible values, whence, for each given a, the number of possible equations (29) and hence the number of possible roots of these equations is finite. Obviously, the sequence of complete quotients a₁, a₂, ···, a_n, ··· will inevitably start to repeat, a fact which has to be proved.

We shall execute this plan in stages. Firstly, we prove (29), and then (30).

Proof: The quadratic irrational a satisfies a certain quadratic equation with integral coefficients.

By (9),

Substitute (32) into (31) and remove the denominator:

where

It must still be proved that the coefficients (33) are bounded. By (14),

This can be rewritten in the form

where (-1 < d < 1), whence

Substitute this expression for p_n-1 into the first Equation (33) above:

Obviously, the expression in brackets vanishes by (31):

But d < 1, so that

We shall also take into account that q²_n-1 > 1 (q₀ = 1, and the sequence q_n is strictly increasing). The inequality is only strengthened if you drop q²_n-1(i.e., replace it by unity):

Thus, you have obtained for |A_n| a bound, which is independent of n.

Instead of conducting similar manipulations for |C_n| note that C_n is obtained from A_n by replacing n by n— I, that is, C_n = A_n-1. The bound established above does nod depend on n, and thus also applies to C_n. As regards B_n, a detour will be more effective. Calculate the discriminant of (29) by means of (33). Omitting long and dull manipulations*, the final result is:

* These manipulations are left to the reader. A mathematician should be patient and not afraid of long chains of transformations!

However, by (12),

whence

This formula expresses a natural fact: When a quadratic irrational number a is expanded into a continued fraction, the complete quotients are quadratic irrationals of the same kind as a, being determined by the discriminant. They are all of the type

for the same D.

(34) shows that

All terms on the right-hand side being bounded, B²_n, and with it |B_n| are also bounded.

Euler's and Lagrange's theorems can be merged as follows: Quadratic irrationals, and only they, are represented by periodical continued fractions.

* These manipulations are left to the reader. A mathematician should be patient and not afraid of long chains of transformations.

last next