There is a story about the followers of Pythagoras, the Pythagoreans, that seeks to explain the circumstances by which people first engaged the concept of irrational numbers. According to the story, in the 5th century B.C.E., a member of the Pythagoreans, Hippasus of Metapontum, demonstrated that the length of the hypotenuse of the right triangle with two legs of length 1 cannot be expressed as the ratio of two integers. The story goes on to say that the Pythagoreans were on a boat in the Adriatic Sea at the time of this announcement and that, in order to silence him, they threw Hippasus overboard to drown. They swore themselves to secrecy about the incident to protect the Pythagorean doctrine that “all is number” – that is, all phenomena in the universe can be reduced to whole numbers or their ratios.

Much has been written concerning this incident involving Hippasus and about the Pythagoreans in general. Some sources, such as the articles on “Pythagoras” [11] and “Pythagoreanism” [12] in the Stanford Encyclopedia of Philosophy, state that Pythagoras and his followers had very little to do with mathematics at all. It may have been that Hippasus was instrumental in a split of the Pythagoreans into two groups. One of these groups, the mathêmatici, began to focus on mathematics and studying the natural world. A few accounts credit Pythagoras himself with tossing Hippasus overboard, but this seems impossible given that history records that their lifespans did not intersect. Further, there are numerous sources that state Pythagoras himself never existed but was a legend created by the Pythagoreans. Because of their commitment to secrecy, accurate information about the life of Pythagoras and his followers is not abundant. We may never know the truth.

None of this changes the fact that at some point in human history there came the realization of quantities, such as the lengths of the diagonals of various rectangles, that could not be expressed as ratios of integers. In [4] (p. 39), Victor Katz wrote:

We do not know who discovered this result, but scholars believe that the discovery took place in approximately 430 B.C.E. And although it is frequently stated that this discovery precipitated a crisis in Greek mathematics, the only reliable evidence shows that the discovery simply opened up the possibility of some new mathematical theories.

Perhaps one of the earliest references to irrational numbers is attributed to Theodorus of Cyrene (late 5th century B.C.E.) in Plato’s Theaetetus (399 B.C.E.). From this work we learn that Theodorus demonstrated that square roots of non-square integers up to 17 are irrational. Thus, there is no solid evidence that Pythagoras (if he existed) knew about irrational numbers.

We do know for certain that significant time and effort have been spent investigating Diophantine approximations; that is, approximations of irrational numbers using rationals. The term "Diophantine" is in honor of Diophantus of Alexandria (circa 207–291 C.E.). For example, a common approximation for \(\pi\) is \(\frac{22}{7}.\) This approximation is within \(0.0013\) of the true value of \(\pi\). Further, Archimedes (circa 287 B.C.E.) offered \(\frac{265}{153}\) as an approximation for \(\sqrt{3}\) (see [10]). This approximation is within \(0.00003\) of the true value. Roger Cotes (1682–1716), an assistant of Isaac Newton, offered \(\frac{44}{37}\) as an approximation for \(\sqrt[4]{2},\) which is within \(0.00002\) of the true value (see the conclusion of [9]) .

Many techniques of Diophantine approximation have developed over the centuries. Herein we will focus on two such techniques and how they produce rational approximations for \(\sqrt{k}\) where \(k\) is a positive integer. The two techniques, continued fractions and Greek ladders, have been examined by mathematicians on many occasions (see [1], [3], [5], [6], [7], [9], and [10]). Our purpose is not to provide new insights into the efficacy of either technique but rather to demonstrate that, with a little care, the two techniques will produce the same sequence of approximations for \(\sqrt{k}\).

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

It is not clear when the notion of continued fractions was first realized. From [5] (pp. 28–29) we read that there are instances of ancient arithmetic which are suggestive of the notion of continued fractions without any formal development. For example, we have Euclid’s algorithm from the seventh book of his Elements (circa 300 B.C.E.). The algorithm computes the greatest common divisor of two integers but can be modified to produce a simple continued fraction for a rational number. For example, we can use Euclid's algorithm to compute \(\gcd(21,51)\) as follows:

There is a reference to continued fractions in the works of the Indian mathematician Aryabhata (476–550 C.E.). In a work called the Aryabhatiya, we find one of the earliest attempts to produce a general solution to a linear indeterminate equation of the form \(by=ax+c\) where \(a,b,\) and \(c\) are integers. The technique demonstrated by Aryabhata is clearly related to continued fractions.

From 1202 C.E. we find in the Liber Abaci (The Book of Calculations) by Leonardo of Pisa, or Fibonacci, the symbol \(\frac{111}{345}\) which he used as an abbreviation for

\[\frac{1+\frac{1+\frac{1}{5}}{4}}{3} = \frac{1}{3}+\frac{1}{3\cdot 4}+\frac{1}{3\cdot 4\cdot 5}.\]

See section 15.2 of [2]. We might also write this as

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

Most modern authorities agree that the theory of continued fractions began with Rafael Bombelli [5] (pp. 29–30). In his L'Algebra Opera (1572), Bombelli essentially proved that \(\sqrt{13}\) is the limit of the infinite continued fraction

\[3+\frac{4}{6+\frac{4}{6+\frac{4}{\ddots}}}\]

That is, \(\sqrt{13} = [3;4,6;4,6;4,6;\dots]\). However, in the notation of the time, Bombelli would have written this continued fraction as

\[\sqrt{13}=3+\frac{4}{6} _+ \frac{4}{6}_+\frac{4}{6}_+ \dots\]

We also find this notation used in modern texts such as [5].

Shortly after Bombelli, Pietro Antonio Cataldi expressed \(\sqrt{18}\) as \([4;2,8;2,8;2,8;\dots]\) and modified the notation as

\[\sqrt{18}=4\ \&\ \frac{2}{8.}\ \&\ \frac{2}{8.}\ \& \dots\]

William Brouncker (1620–1684) established this interesting identity:

\[\frac{4}{\pi} = 1+\frac{1^2}{2+\frac{3^2}{2+\frac{5^2}{2+\frac{7^2}{\ddots}}}}.\]

Brouncker made no further use of continued fractions. However his contemporary John Wallis, perhaps motivated by Brouncker's fraction, established many of the basic properties of convergents in his 1655 book Arithmetica Infinitorum. He also used the term "continued fraction" for the first time.

Christian Huygens (1629–1695) is credited with being the first to use continued fractions in a practical application. He used continued fractions for approximating gear ratios in the building of a mechanical planetarium.

The theory of continued fractions was developed further through the 18th and 19th centuries by Euler, Lambert, Lagrange, and many others. Continued fractions continue to play an important role today in number theory and Diophantine approximations.

Another Diophantine approximation technique for \(\sqrt{k}\) is the Greek ladder. This method involves starting with two integers, not both zero, which we will call \(x_1\) and \(y_1\). We then recursively define \(x_n\) and \(y_n\) for \(n \ge 2\) by

Then, the sequence of rationals \(\frac{y_1}{x_1}, \frac{y_2}{x_2}, \frac{y_3}{x_3}, \dots\) converges to \(\sqrt{k}\) (see [3]). When we refer to the classic Greek ladder, we mean the Greek ladder with \(x_1 = 1\) and \(y_1 = 1\).

As an example, the first several rungs of the classic Greek ladder for \(\sqrt{2}\) are:

There is less known about the history of Greek ladders when compared to the extensive history of continued fractions. It is thought by many that Theon of Alexandria (335–405 C.E.) was the "father" of Greek ladders. In fact, Greek ladders are often referred to as "Theon's ladders." It is conjectured that the motivation for Greek ladders could be the realization that if \(b/a \approx \sqrt{k}\), then, it is generally true that \((ka + b)/(a + b)\) is a closer approximation to \(\sqrt{k}\). We leave to the reader the exercise of coming up with the exact statement and giving a detailed proof of this "generally true" statement. However, we offer the following sketch as a guide:

First assume that \(a,b,\) and \(k\) are positive integers and define \(\epsilon = (\frac{b}{a})^2-k\). Now, prove the following:

\[\left(\frac{ka+b}{a+b}\right)^2-k = -\epsilon (k-1)\left(\frac{a}{a+b}\right)^2.\]

We conclude that if \((k-1)\left(\frac{a}{a+b}\right)^2 < 1\), then \(\frac{ka+b}{a+b}\) is a closer approximation to \(\sqrt{k}\) than \(\frac{b}{a}\). Further we see that if \(\frac{b}{a}\) is an overestimate (underestimate), then \(\frac{ka+b}{a+b}\) is an underestimate (overestimate). Finally, establish the conditions that are necessary and sufficient to conclude \((k-1)\left(\frac{a}{a+b}\right)^2 < 1\).

As an example, let \(k = 3\), \(a = 2,\) and \(b = 3\). Then \(\epsilon = \left(\frac{3}{2}\right)^2-3 = -\frac{3}{4}.\) Now, \[\left(\frac{ka+b}{a+b}\right)^2-k = -\epsilon (k-1)\left(\frac{a}{a+b}\right)^2 = -\frac{8}{25}\epsilon = \frac{6}{25}.\]

For additional history and results concerning Greek ladders, the reader should consider [3], [6], [7], [9], and [10] as resources.

As we noted earlier, the simple continued fraction converging to \(\sqrt{2}\) is \([1,2,2,2 \dots]\). It is easy to check that the \(n\)th convergent of this continued fraction is equal to the value of \(\frac{y_n}{x_n}\) produced by the classic Greek ladder for \(\sqrt{2}\) by hand (or computer) up to any \(n\) we wish. A general proof for all \(n\) is left to the reader but we should note that the proof is a special case of the induction proof we will demonstrate later in this section. Similarly, the simple continued fraction converging to \(\sqrt{3}\) is \([1,1,2,1,2,1,2,\dots]\) and the sequence of convergents of this continued fraction is equal to the sequence of rational numbers produced by the classic Greek ladder for \(\sqrt{3}\). We might expect this relationship to continue for \(\sqrt{k}\) for any positive integer \(k,\) but when \(k = 5\) we see the simple continued fraction that converges to \(\sqrt{5}\) is \([2,4,4,4,4\dots],\) which produces convergents \[S_1 = 2,\ S_2 = \frac{9}{4}=2.25,\ S_3=\frac{38}{17}=2.23529,\ S_4=\frac{161}{72}=2.23611,\ \dots.\] However, the classic Greek ladder approximating \(\sqrt{5}\) is:

For \(k \ge 5\) we know that the first convergent of the simple continued fraction for \(\sqrt{k}\) is at least \(2,\) whereas the classic Greek ladder always start with \(1\). The reader is encouraged to investigate and attempt to prove that even adjusting the starting values of the Greek ladder so that \(y_1/x_1 = S_1\) will not make the two sequences equal.

The question we pose is, "can we find a continued fraction converging to \(\sqrt{k}\) such that the sequence of convergents is identical to the sequence of approximations that comes from the classic Greek ladder for all \(k \ge 2\)?" The answer to our question is, "yes." However, the continued fraction in question will not be a simple continued fraction. For example, \([1;4,2;4,2;4,2;\dots]\) is a continued fraction that converges to \(\sqrt{5}\) and the sequence of convergents of this continued fraction is equal to the sequence \(\frac{y_n}{x_n}\) created by the classic Greek ladder for \(\sqrt{5}\).

Claim:  We claim that the sequence of approximations created by the classic Greek ladder for \(\sqrt{k}\) is identical to the convergents of the continued fraction

\[[1; k-1,2;k-1,2;k-1,2;\dots].\]

The proof will proceed by induction; however, the induction argument is somewhat more sophisticated than standard induction proofs that establish common identities such as

\[1+2+\cdots+n = \frac{(n)(n+1)}{2}\]

for all positive integers \(n.\)

We believe that students who have had some experience with basic induction arguments will find it enlightening to examine this proof. Such students might attempt this proof on their own before reading what follows. We believe this exercise will be useful as a project in an introductory proofs course or an introductory Combinatorics class studying recursion. For a more challenging project, instructors might require that students discover the continued fraction on their own. In this case, students will need to create several examples, look for patterns, and test conjectures before attempting a proof.

Proof of the claim:  We start with the classic Greek ladder for \(\sqrt{k}\):

Recall that \(x_n = x_{n-1} + y_{n-1}\) and \(y_n = kx_{n-1} + y_{n-1}\) for \(n \ge 2.\)

Now, consider the continued fraction:

\[1+\frac{k-1}{2+\frac{k-1}{2 + \frac{k-1}{2+\frac{k-1}{\vdots}}}}\]

For \(n = 1\), we have \(S_1 = 1 = \frac{y_1}{x_1}\).

For \(n=2\), we have \(S_2 = 1+\frac{k-1}{2} = \frac{k+1}{2} = \frac{y_2}{x_2}\).

This establishes the truth of our statement for \(n=1\) and \(n=2\) and hence the base cases for our induction argument. Before proceeding with the inductive step we take a moment to note something about the convergents of the continued fraction:

\[S_3-1 = \frac{k-1}{2+\frac{k-1}{2}}=\frac{k-1}{{S_2}+1}\]

\[S_4-1 = \frac{k-1}{2+\frac{k-1}{2 + \frac{k-1}{2}}}=\frac{k-1}{{S_3}+1}\]

\[\vdots\]

Following the discussion that led to Equation (1), we see that for \(n\ge3\) we have,

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

Now, our induction hypothesis states that for \(n\ge3\) we assume that the \((n-1)\)th convergent of the continued fraction is equal to \(\frac{y_{n-1}}{x_{n-1}}\). That is, we assume that

\[S_{n-1} = \frac{y_{n-1}}{x_{n-1}}.\]

Then, from Equation (2) we have

\[S_n-1 = \frac{k-1}{S_{n-1}+1}\]

\[= \frac{k-1}{\frac{y_{n-1}}{x_{n-1}}+1}\]

\[= \frac{k-1}{\frac{x_{n-1}+y_{n-1}}{x_{n-1}}}\]

\[= \frac{(k-1)x_{n-1}}{x_{n-1}+y_{n-1}}.\]

Adding \(1\) to both sides of the equation yields

\[S_n = \frac{(k-1)x_{n-1}}{x_{n-1}+y_{n-1}}+1\]

\[= \frac{kx_{n-1}+y_{n-1}}{x_{n-1}+y_{n-1}}.\]

Recalling the recursive definitions of \(x_n\) and \(y_n\) we have

\[S_n = \frac{y_n}{x_n}.\]

We have shown for \(n\ge 3\) that if \({S_{n-1}}={\frac{y_{n-1}}{x_{n-1}}},\) then \(S_n=\frac{y_n}{x_n}\). This completes the proof by induction that \(S_n=\frac{y_n}{x_n}\) for all \(n\ge1.\)

The key step in the preceding proof was establishing the recursive relation in Equation (2). This relation is very similar to Equation (1). If students have seen the proof that \([1,2,2,\dots]\) converges to \(\sqrt{2}\), then they may be on the look-out for a similar sort of relation. The instructor will need to be ready to help students realize Equation (2) in order to keep them moving forward on the proof.

It is left to the reader to confirm that we can start a Greek ladder for \(\sqrt{k}\) with any non-negative integers \(x_1\) and \(y_1\) (as long as they are not both zero) and the sequence of approximations produced by the ladder will still converge to \(\sqrt{k}\). Thus, a natural question to ask is, "If we don't start the Greek ladder with initial values \(x_1=1\) and \(y_1=1\), can we still find a continued fraction with convergents that match the Greek ladder at every term?" We leave this question as an opportunity for further investigation by students who wish to engage in mathematical research on their own. We offer the following examples as enticement.

Example 1:  If we start with \(x_1 = 1\) and \(y_1=2\), the ladder for \(\sqrt{k}\) looks like:

The continued fraction that matches it is

\[[2;k-4,3;k-1,2;k-1,2;k-1,2,\dots].\]

Example 2:  If we start with \(x_1 = 2\) and \(y_1=3\), the ladder for \(\sqrt{k}\) looks like:

The continued fraction that matches it is

\[[3/2;4k-9,10;2k-2,1;k-1,4;k-1,1;k-1,4;k-1,1; \dots].\]

We say that a continued fraction of this type is eventually periodic of period 2.

We believe there are additional patterns and general statements that can be proved concerning the starting values of the ladder and its corresponding continued fraction.

References

[1] Brezinski, Claude, History of Continued Fractions and Pade Approximants, Springer-Verlag, New York, 1980

[2] Burton, David, Elementary Number Theory (7th ed.), McGraw-Hill, New York, 2011

[3] Giberson, S. and Osler, T. J., Extending Theon’s ladder to any square root, The College Mathematics Journal 35 (2004), 222-226

[4] Katz, Victor, A History of Mathematics: An Introduction (3rd ed.), Addison-Wesley, Boston, 2009

[5] Olds, C.D., Continued Fractions, Random House: New York, 1963

[6] Osler, T. J., Wright, M. and Orchard, M., Theon’s ladder for any root, International Journal of Mathematical Education in Science and Technology 36 (2005), 389–398

[7] Osler, T. J., Using Theon’s ladder to find roots of quadratic equations, Mathematics and Computer Education 42 (2008), 23–27

[8] Rosen, Kenneth, Elementary Number Theory and Its Applications (4th ed.), Addison-Wesley, Boston, 2000

[9] Wisner, R. J., The classic Greek ladder and Newton’s method, Loci: Convergence (2009), DOI: 10.4169/loci003330

[10] Wisner, R. J., A disquisition on the square root of three, Loci: Convergence (2010), DOI: 10.4169/loci003514

[11] Huffman, Carl, Pythagoras, The Stanford Encyclopedia of Philosophy (Fall 2011 Edition), Edward N. Zalta (ed.),
URL = http://plato.stanford.edu/archives/fall2011/entries/pythagoras/
Accessed Jan. 2014 via http://plato.stanford.edu/entries/pythagoras/

[12] Huffman, Carl, Pythagoreanism, The Stanford Encyclopedia of Philosophy (Summer 2010 Edition), Edward N. Zalta (ed.),
URL = http://plato.stanford.edu/archives/sum2010/entries/pythagoreanism/
Accessed Jan. 2014 via http://plato.stanford.edu/entries/pythagoreanism

Acknowledgment

The authors extend sincere thanks to David Pengelley for his valuable comments and advice concerning this paper.

About the Authors

Kurt Herzinger is a member of the Department of Mathematical Sciences at the United States Air Force Academy in Colorado Springs, Colorado.  He earned his Ph.D. in mathematics from the University of Nebraska-Lincoln in 1996. His research program primarily focuses on problems in numerical semigroups motivated by topics in commutative algebra. Recently, Kurt has taken an interest in problems involving Greek ladders thanks to meeting Prof. Robert Wisner at a MAA regional meeting in 2009.

Robert "Bob" Wisner is Professor Emeritus of Mathematics at New Mexico State University. He was founding editor of SIAM Review, a publication of the Society for Industrial and Applied Mathematics. He was the first full-time Executive Director of the MAA's Committee on the Undergraduate Program in Mathematics (CUPM), 1960-1963. Bob also authored or coauthored numerous K-12 textbooks for Scott, Foresman; was Consulting Editor in Mathematics for Brooks/Cole for over 25 years; coauthored a liberal arts mathematics textbook; and recently coauthored a series of interactive calculus, business calculus, pre-calculus, and AP calculus textbooks, available on CD from Hardy Calculus.