You are here

Connecting Greek Ladders and Continued Fractions - Continued Fractions

Author(s): 
Kurt Herzinger (United States Air Force Academy) and Robert Wisner (New Mexico State University)

A continued fraction is a fraction of the form

\[a_1 + \frac{b_1}{a_2 +\frac{b_2}{a_3 + \frac{b_3}{a_4 + \frac{b_4}{\ddots}}}}\]

where \(a_i\) and \(b_i\) are real or complex numbers. There may be a finite number of terms or infinitely many. Much investigation has been devoted to continued fractions in the case where \(b_i = 1\) for all \(i\), the \(a_i\) are all integers, and \(a_i >0\) for \(i\ge 2\). Such fractions are called simple continued fractions. We use the shorthand notation \([a_1,a_2,a_3,a_4,\dots]\) to represent the simple continued fraction

\[a_1 + \frac{1}{a_2 +\frac{1}{a_3 + \frac{1}{a_4 + \frac{1}{\ddots}}}}\]

The notation \([a_1,a_2,\dots,a_n]\) represents a finite simple continued fraction whose value can be computed easily. For example, \([1,4,1,2] = \frac{17}{14}.\) This terminology and notation is consistent with that in [5].

In the case of a continued fraction which is not simple we will use the shorthand notation \([a_1; b_1, a_2; b_2, a_3; \dots]\). We define the \(n\)th convergent of a continued fraction as

\[S_n = [a_1; b_1, a_2; \dots ; b_{n-1},a_n].\]

For example \([1;2,3;3,4]\) represents

\[1 + \frac{2}{3 +\frac{3}{4}} = \frac{23}{15}.\]

We say the continued fraction \([a_1; b_1, a_2; b_2, a_3; \dots]\) converges provided \(\lim_{n\rightarrow\infty}{S_n}\) exists. As an example, consider the simple continued fraction \([1,2,2,2,\dots,]\) which corresponds to

\[1 + \frac{1}{2 +\frac{1}{2 + \frac{1}{2 + \frac{1}{\ddots}}}}\]

In Section 3.2 of [5], the author proves that if this continued fraction converges, then it converges to \(\sqrt{2}\). As a brief summary of that work, note that for \(n \ge 2\) we have

\[S_n = [1,2,2,\dots,2] \ \ ({\rm with}\ n-1 \ 2{\rm{s}})\]

\[= 1 + \frac{1}{2 +\frac{1}{2 + \frac{1}{2 + \frac{1}{\ddots \frac{1}{2+\frac{1}{2}}}}}}\]

\[= 1 + \frac{1}{1 +\left( 1+ \frac{1}{2 + \frac{1}{2 + \frac{1}{\ddots \frac{1}{2+\frac{1}{2}}}}}\right)}\]

But by definition of the convergents, the expression in parentheses is \(S_{n-1}.\) Thus,

\[S_n = 1+\frac{1}{S_{n-1}+1}\quad\quad{\rm{(Equation}}\ 1).\]

If we assume that \(\lim_{n \rightarrow \infty} S_n\) exists and is equal to \(L\), then letting \(n \rightarrow \infty\) yields

\[L=1+\frac{1}{L+1}.\]

Solving for \(L\) we see that \(L= \sqrt{2}\). Thus, we know that if the simple continued fraction \([1,2,2,2,\dots]\) converges, it converges to \(\sqrt{2}\). For a proof that this limit exists, see Section 3.6 of [5]. Thus, the convergents of this continued fraction provide us with a sequence of rational numbers which can be used as more and more accurate approximations to \(\sqrt{2}\).

For an algorithm that produces a simple continued fraction converging to a given real number, see Section 3.2 of [5]. Briefly, the algorithm proceeds as follows: let \(x\) be a real number. Let

\[a_1=\lfloor x \rfloor\ {\rm and}\ r_1 = x-a_1.\]

For \(n \ge 2\),

\[a_n = \bigg\lfloor{\frac{1}{r_{n-1}}}\bigg\rfloor\ {\rm and}\ r_n = \frac{1}{r_{n-1}}-a_n.\]

Then \([a_1,a_2,a_3,\dots]\) is a simple continued fraction that converges to \(x\). The reader can check that the simple continued fraction \([1,2,2,2,\dots]\) converging to \(\sqrt{2}\) is the result of this algorithm.

Moreover, for a real number \(x\), the representation of \(x\) as a simple continued fraction is unique. That is, if \(x\) is expressed as a simple continued fraction by \([a_1, a_2, a_3, \dots]\) and by \([b_1, b_2, b_3, \dots]\), then \(a_k=b_k\) for all \(k\). A proof by induction can be found in many number theory texts, such as Theorem 12.16 of [8] and Theorem 15.6 of [2].

Kurt Herzinger (United States Air Force Academy) and Robert Wisner (New Mexico State University), "Connecting Greek Ladders and Continued Fractions - Continued Fractions," Loci (January 2014)

Dummy View - NOT TO BE DELETED