6.1: Basic Notations
( \newcommand{\kernel}{\mathrm{null}\,}\)
In general, a (simple) continued fraction is an expression of the form a0+1a1+1a2+…, where the letters a0, a1, a2, … denote independent variables, and may be interpreted as one wants (e.g. real or complex numbers, functions, etc.). This expression has precise sense if the number of terms is finite, and may have no meaning for an infinite number of terms. In this section we only discuss the simplest classical setting.
The letters a1, a2, … denote positive integers. The letter a0 denotes an integer.
The following standard notation is very convenient.
We write [a0;a1,a2,…,an]=a0+1a1+1a2+…+1an if the number of terms is finite, and [a0;a1,a2,…]=a0+1a1+1a2+… for an infinite number of terms.
Still, in the case of infinite number of terms a certain amount of work must be carried out in order to make the above formula meaningful. At the same time, for the finite number of terms the formula makes sense.
[−2;1,3,5]=−2+1/(1+1/(3+1/5))=−2+1/(1+5/16)=−2+1/(21/16)=−2+16/21=−26/21
For a finite continued fraction [a0;a1,a2,…,an] and a positive integer k≤n, the k-th remainder is defined as the continued fraction rk=[ak;ak+1,ak+2,…,an].
Similarly, for an infinite continued fraction [a0;a1,a2,…] and a positive integer k, the k-th remainder is defined as the continued fraction rk=[ak;ak+1,ak+2,…].
Thus, at least in the case of a finite continued fraction, α=[a0;a1,a2,…,an]=a0+1/(a1+1/(a2+…+1/an)) we have α=a0+1/(a1+1/(a2+…+1/(ak−1+1/rk)))="[a0;a1,a2,…,ak−1,rk]" for any positive k≤n. Quotation signs appear because we consider the expressions of this kind only with integer entries but the quantity rk may be a non-integer.
It is not difficult to expand any rational number α into a continued fraction. Indeed, let a0=[α] be the greatest integer not exceeding α. Thus the difference δ=α−a0<1 and, of course, δ≥0. If δ=0 then we are done. Otherwise put r1=1/δ, find a1=[r1] and non-negative δ=α1−a1<1. Continue the procedure until you obtain δ=0.
Consider the continued fraction expansion for 42/31. We obtain a0=[42/31]=1, δ=42/31−1=11/31. Now r1=1/δ=31/11 and a1=[α1]=[31/11]=2. The new δ=31/11−2=9/11. Now r2=1/δ=11/9 and a2=[α2]=[11/9]=1. It follows that δ=11/9−1=2/9. Now r3=1/δ=9/2 and a3=[α3]=[9/2]=4. It follows that δ=9/2−4=1/2. Now r4=1/δ=2 and a4=[α4]=[2]=2. It follows that δ=2−2=0 and we are done.
Thus we have calculated 42/31=[a0;a1,a2,a3,a4]=[1;2,1,4,2].
The above example shows that the algorithm stops after finitely many steps. This is in fact quite a general phenomenon. In order to practice with the introduced notations let us prove a simple but important proposition.
[ratrep] Any rational number can be represented as a finite continued fraction.
Proof. By construction, all remainders are positive rationals. For a positive integer k put rk=A/B and let ak=[rk]. Then rk−ak=A−BakB:=CB. with C<B because rk−ak<1 by construction. If C=0, then the algorithm stops at this point and we are done. Assume now that C≠0. It follows from ([remainder]) that rk=ak+1rk+1. Compare now ([l2]) with ([l1]) to find that rk+1=BC. Since C<B, the rational number rk+1 has a denominator which is smaller than the the denominator of the previous remainder rk. It follows that after a finite number of steps we obtain an integer (a rational with 1 in the denominator) rn=an and the procedure stops at this point.
There appear several natural questions in the connection with Proposition [ratrep].
Is such a continued fraction representation unique? The immediate answer is "no". Here are two "different" continued fraction representations for 1/2: 12=[0;2]=[0;1,1]. However, we require that an>1, where an is the last element of a finite continued fraction. Then the answer is "yes".
Hint. Make use of the formulas ([main]) below.
From now on we assume that an>1.
Another natural question is about infinite continued fractions and (as one can easily guess) real numbers. The proof of the corresponding result is slightly more involved, and we do not give it here. In this brief introduction we just formulate the result and refer to the literature () for a complete proof. We, however, provide some remarks concerning this result below. In particular, we will explain at some point, what the convergence means.
[realrep] An infinite continued fraction converges and defines a real number. There is a one-to-one correspondence between
∙ all (finite and infinite) continued fractions [a0;a1,a2,…] with an integer a0 and positive integers ak for k>0 (and the last term an>1 in the case of finite continued fractions)
and
∙ real numbers.
Note that the algorithm we developed above can be applied to any real number and provides the corresponding continued fraction.
Theorem [realrep] has certain theoretical significance. L.Kronecker (1823-1891) said, "God created the integers; the rest is work of man". Several ways to represent real numbers out of integers are well-known. Theorem [realrep] provides yet another way to fulfill this task. This way is constructive and at the same time is not tied to any particular base (say to decimal or binary decomposition).
We will discuss some examples later.
Exercises
- Prove that under the assumption an>1 the continued fraction representation given in Proposition [ratrep] is unique. In other words, the correspondence between
∙ finite continued fractions [a0;a1,a2,…an] with an integer a0, positive integers ak for k>0 and an>1
and
∙ rational numbers
is one-to-one.
Contributors and Attributions
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.