The Classic Greek Ladder and Newton's Method

Classic Greek Ladders

Recall that the classic Greek Ladder starts with first rung \( \langle 1 \quad 1 \rangle \), each rung \( \langle a \quad b \rangle \) is followed by \( \langle a+b \quad 2a+b \rangle \), and the approximations to \( \sqrt{2} \) are the fractions \( b/a \).

I first learned about the classic Greek Ladder in [5]. This Greek Ladder is old, its introduction (invention?) often accredited to the mathematician Theon of Smyrna (circa 70-135 AD) [6], but there is reason to believe that it --- or equivalent constructs --- may well have been known much earlier, for on the first page of [1, Chap. XII], we find, "There appeared in India and Greece as early as 400 B.C. approximations \( a/b \) to \( {\sqrt{2}} \) . . ." and that "Baudhâyana, the Hindu author of the oldest of the works, Sulva-sutras, gave the approximations \( 17/12 \) and \( 577/408 \) to \( \sqrt{2} \) ." The first of these is from rung four of the above ladder, the second from rung eight, as you will see by extending that ladder another three rungs. (The Greek Ladder for \( \sqrt{2} \) can begin with any two numbers, not both zero, for the first rung, but the classic ladder begins as shown.)

This ladder also arises from a "vertical" recursive definition: \[ \begin{align*} a_{1} & =1\text{, }a_{2}=2\text{, and for }n>2\text{, }a_{n}=2a_{n-1}+a_{n-2}\\b_{1} & =1\text{, }b_{2}=3\text{, and for }n>2\text{, }b_{n}=2b_{n-1}+b_{n-2}.\end{align*} \] You can check that this definition arises simply by examining an arbitrary rung \( \langle a\quad b\rangle \) and its two successors, using the first definition: \[ \begin{array}{cc} a & b\\ a+b & 2a+b\\ 3a+2b & 4a+3b \end{array} \] The second definition will be used later to construct a general term of the classic ladder.

To see that \( \sqrt{2} \) is in fact the limit of the sequence \[ \frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\frac{99}{70},\dots \] look instead at the sequence of their squares: \[ \frac{1}{1},\frac{9}{4},\frac{49}{25},\frac{289}{144},\frac{1681}{841},\frac{9801}{4900},\dots \] which can also be written as \[ 2-\frac{1}{1^{2}},2+\frac{1}{2^{2}},2-\frac{1}{5^{2}},2+\frac{1}{12^{2}},2-\frac{1}{29^{2}},2+\frac{1}{70^{2}},\dots \] Now the limit of the sequence \[ -\frac{1}{1^{2}},\frac{1}{2^{2}},-\frac{1}{5^{2}},\frac{1}{12^{2}},-\frac{1}{29^{2}},\frac{1}{70^{2}},\dots \] is clearly zero since the denominators are --- by the "vertical" definition for the numbers \( a_{n} \) -- increasing without bound. Thus, the sequence of squares has limit \( 2 \), so the original sequence of fractions from the Greek Ladder has limit \( \sqrt{2} \).

To assess Diophantine approximations of quadratic surds, I devised a "rating" system using the symbol \( (P,n)\) to mean that the reduced fraction \(\frac{b}{a}\) satisfies \(b^{2}=Da^{2}+P\), where \(\frac{b}{a}\) with an \(n\)-digit denominator approximates \(\sqrt{D}\). For a given \(D\), \({\left(\pm1,n\right)}\) is a "best approximation." (The letter \(P\) is a nod to John Pell [1, Chap. XII] and [2].) You can see how "good" the classic \(\sqrt{2}\) ladder is, in that each of its approximations is a best approximation. In [7], you learn that the Greek Ladder for \({\sqrt{k}}\) is constructed by following each rung \(\langle a\quad b\rangle\) by the rung \(\langle a+b\quad ka+b\rangle\). Using this fact, here are some Greek Ladder approximations and their ratings that you can verify: \[\begin{array}{ccccc} \sqrt{3}\approx\frac{19}{11} & & \sqrt{5}\approx\frac{11}{5} & & \sqrt{6}\approx\frac{73}{28}\\ \text{rating }\left(-2,2\right) & & \text{rating }\left(-4,1\right) & & \text{rating }\left(625,2\right) \end{array} \] What is the rating of \(1.414\) as an approximation for \({\sqrt{2}}\)? What about the rating of \(1.732\) as an approximation for \(\sqrt{3}\)?

This rating system is easily extended to cubic and higher surds. Also, [7] shows that approximations can frequently be improved by use of the Farey mean \(\frac{a+c}{b+d}\) of the two common fractions \(\frac{a}{b}\) and \(\frac{c}{d}\). For example, the Farey mean of \(\frac{7}{5}\) and \(\frac{17}{12}\) is \(\frac{24}{17}
\approx1.411765\).