Comparison with Newton's Method

For this section, we need, for reference, to repeat and extend the classic ladder, this time with rungs numbered in bold:  \[  \begin{array}{ccccccccccccccc} \mathbf{1} & 1 & 1 &  & \mathbf{5} & 29 & 41 &  & \mathbf{9} & 985 & 1393 &  & \mathbf{13} & 33461 & 47321\\ \mathbf{2} & 2 & 3 &  & \mathbf{6} & 70 & 99 &  & \mathbf{10} & 2378 & 3363 & & \mathbf{14} & 80782 & 114243\\ \mathbf{3} & 5 & 7 &  & \mathbf{7} & 169 & 239 &  & \mathbf{11} & 5741 & 8119 &  & \mathbf{15} & 195025 & 275807\\ \mathbf{4} & 12 & 17 &  & \mathbf{8} & 408 & 577 &  & \mathbf{12} & 13860 & 19601 &  & \mathbf{16} & 470832 & 665857
\end{array} \]

A standard topic in calculus is Newton's Method for approximating roots, so it is natural to ask how the classic Greek Ladder compares with Newton's Method for approximating \( \sqrt{2} \). To that end, we let \(s\left(  x\right) =x^{2}-2\), so then \(s^{\prime}\left(  x\right)  =2x\), and the Newton scheme is to start with an estimate \(x_{0}\) and compute for each \(x_{n}\) the next estimate \(x_{n+1}\), where \[ x_{n+1}=x_{n}-\frac{s\left(  x_{n}\right)  }{s^{\prime}\left(  x_{n}\right) } \] The classic Greek Ladder begins with the first estimate of \(\frac{1}{1}\), so
for comparison, we choose the corresponding Newton estimate as \(x_{0}=\frac {1}{1}\), and this is what ensues:  \[  \begin{array}{lll} x_{1}=\frac{1}{1}-\frac{\left(  \frac{1}{1}\right)  ^{2}-2}{2\times\frac{1}{1}}=\frac{3}{2}\quad\text{from Rung 2} &  & x_{3}=\frac{17}{12}-\frac{\left(  \frac{17}{12}\right)  ^{2}-2}{2\times\frac{17}{12}}=\frac{577}{408}\quad\text{from Rung 8}\\x_{2}=\frac{3}{2}-\frac{\left(  \frac{3}{2}\right)  ^{2}-2}{2\times\frac{3}{2}}=\frac{17}{12}\quad\text{from Rung 4} &  & x_{4}=\frac{577}{408} -\frac{\left(  \frac{577}{408}\right)  ^{2}-2}{2\times\frac{577}{408}} =\frac{665857}{470832}\quad\text{from Rung 16}\end{array}\] So the \(n\)-th Newton iterate equals the \(2^{n}\)-th Greek Ladder approximation for \(n=1\) to \(n=4\). The next Newton iterates comport with the approximations from rung \(32\) of the ladder, which is \(\langle627013566048\quad 886731088897\rangle\); the \(64\)-th rung; and on up to rungs too wide for a page here. (These computations were obtained by the software Scientific WorkPlace, and if you ask it to "Evaluate" an expression involving fractions, it gives fractional output. "Evaluate Numerically" gives decimal estimates as output.) In any case, it seems that more than a sufficiency of such calculations have now been made so as to provoke the statement of this

Theorem. The classical \(\sqrt{2}\) Greek Ladder has the property that its rungs numbered \(2^{n}\) yield fractions equal to the \(n^{th}\) Newton's Method iterates \(x_{n}\) approximating \(\sqrt{2}\), with \(x_{0}=\frac{1}{1}\).

Proof. From the recursive definition of the columns of the classical Greek Ladder, which is \[ \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*} \]
we fix on the sequences \(\left\{  a_{i}\right\}\) and \(\left\{b_{i}\right\}\). But first, it needs to be shown that this recursive definition is equivalent to the original. To this end, look at the rungs beginning with \(\langle a_{n-2}\quad b_{n-2}\rangle\) and use the original system progressing therefrom: \[ \begin{array}{cc} a_{n-2} & b_{n-2}\\ a_{n-1}=a_{n-2}+b_{n-2} & b_{n-1}=2a_{n-2}+b_{n-2}\\ a_{n}=3a_{n-2}+2b_{n-2} & b_{n}=4a_{n-2}+3b_{n-2} \end{array} \] We can see from this that \[a_{n}=3a_{n-2}+2b_{n-2}=2\left(  a_{n-2} +b_{n-2}\right)  +a_{n-2}=2a_{n-1}+a_{n-2}\] which is the relationship in the recursive definition of \(a_{n}\). A similar analysis gives \(b_{n}\) in terms of \(b_{n-1}\) and \(b_{n-2}\).

The splendid paper by Hendel [4] gives various methods for deriving general terms of such recursive sequences. The section of that paper titled "Number Theory" seems most direct for the purposes at hand and gives \[ a_{n}=\frac{\left(  1+\sqrt{2}\right)  ^{n}-\left(  1-\sqrt{2}\right)  ^{n} }{2\sqrt{2}}\text{ and }b_{n}=\frac{\left(  1+\sqrt{2}\right)  ^{n}+\left(1-\sqrt{2}\right)  ^{n}}{2}. \] So the \(n\)-th rung of the classical Greek Ladder is \[ {\left\langle \frac{\left(  1+\sqrt{2}\right)  ^{n}-\left(  1-\sqrt{2}\right)^{n}}{2\sqrt{2}}\qquad\frac{\left(  1+\sqrt{2}\right)  ^{n}+\left(  1-\sqrt{2}\right)  ^{n}}{2}\right\rangle}.\] The corresponding approximation for \(\sqrt{2}\) deriving from the \(n\)-th rung is thus \[ \frac{\frac{\left(  1+\sqrt{2}\right)  ^{n}+\left(  1-\sqrt{2}\right)  ^{n}}{2}}{\frac{\left(  1+\sqrt{2}\right)  ^{n}-\left(  1-\sqrt{2}\right)  ^{n}}{2\sqrt{2}}}=\frac{\sqrt{2}\left(  \sqrt{2}+1\right)  ^{n}+\sqrt{2}\left(1-\sqrt{2}\right)  ^{n}}{\left(  \sqrt{2}+1\right)  ^{n}-\left(  1-\sqrt{2}\right)  ^{n}} \] and we want to see what happens when this fraction from the \(n\)-th rung is subjected to Newton's Method. Here it is: \[\begin{align*} &  \frac{\sqrt{2}\left(  \sqrt{2}+1\right)  ^{n}+\sqrt{2}\left(  1-\sqrt {2}\right)  ^{n}}{\left(  \sqrt{2}+1\right) ^{n}-\left(  1-\sqrt{2}\right)^{n}}-\frac{\left(  \frac{\sqrt{2}\left(  \sqrt{2}+1\right)  ^{n}+\sqrt{2}\left(  1-\sqrt{2}\right)  ^{n}}{\left(  \sqrt{2}+1\right)^{n}-\left(1-\sqrt{2}\right)  ^{n}}\right)  ^{2}-2}{2\times\frac{\sqrt{2}\left(  \sqrt{2}+1\right)  ^{n}+\sqrt{2}\left(  1-\sqrt{2}\right)  ^{n}}{\left(  \sqrt{2}+1\right) ^{n}-\left(  1-\sqrt{2}\right)  ^{n}}}\\ &  =\frac{\sqrt{2}\left[  \left(  1+\sqrt{2}\right)  ^{2n}+\left(  1-\sqrt{2}\right)  ^{2n}\right]  }{\left(  1+\sqrt{2}\right) ^{2n}-\left(1-\sqrt{2}\right)  ^{2n}}\end{align*}\] which comes from the \(2n\)-th rung, \[ \left\langle \frac{\left(  1+\sqrt{2}\right)  ^{2n}-\left(  1-\sqrt{2}\right)^{2n}}{2\sqrt{2}}\qquad\frac{\left(  1+\sqrt{2}\right)  ^{2n}+\left(1-\sqrt{2}\right)  ^{2n}}{2}\right\rangle,\] whence the doubling pattern of the theorem is established.

It is implicit in this proof that the doubling takes place for any rung, so the process can begin by starting not just with \(\langle1\quad1\rangle\) but with any rung whatsoever.