Connecting Greek Ladders and Continued Fractions - Greek Ladders

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

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

\(x_n\) = \(x_{n-1} + y_{n-1}\)
\(y_n\) = \(kx_{n-1} + y_{n-1}\)

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:

  \(x_n\) \(y_n\) \({y_n}/{x_n}\)    
\(n=1\) \(1\) \(1\) \(1/1\) = \(1\)
\(n=2\) \(2\) \(3\) \(3/2\) = \(1.5\)
\(n=3\) \(5\) \(7\) \(7/5\) = \(1.4\)
\(n=4\) \(12\) \(17\) \(17/12\) = \(1.4167\)
\(n=5\) \(29\) \(41\) \(41/29\) = \(1.4137\)
\(\vdots\) \(\vdots\) \(\vdots\)   \(\vdots\)  

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.