You are here

The Classic Greek Ladder and Newton's Method

Robert J. Wisner (New Mexico State University)

Extending the Connection

What about Newton's Method and the \( \sqrt{3} \) Greek Ladder? From [7], the standard version of this ladder begins with rung \(\langle1\quad1\rangle\), each rung is followed by \(\langle a+b\quad3a+b\rangle\), and each rung is "reduced." It begins \[ \begin{array}{ccc} 1 & 1 & \frac{1}{1}=1.00000\\ 1 & 2 & \frac{2}{1}=2.00000\\ 3 & 5 & \frac{5}{3}\approx1.66667\\ 4 & 7 & \frac{7}{4}=1.75000 \end{array} \qquad \begin{array}{ccc} 11 & 19 & \frac{19}{11}\approx1.72727\\ 15 & 26 & \frac{26}{15}\approx1.73333\\ 41 & 71 & \frac{71}{41}\approx1.73171\\ 56 & 97 & \frac{97}{56}\approx1.73214 \end{array} \] Here is what happens when Newton's Method is applied and iterated. \[ \begin{array}{c} x_{1}=\frac{1}{1}-\frac{\left( \frac{1}{1}\right) ^{2}-3}{2\times\frac{1}{1}}=\frac{2}{1}\quad\text{from Rung 2}\\ x_{2}=\frac{2}{1}-\frac{\left( \frac{2}{1}\right) ^{2}-3}{2\times2}=\frac{7}{4}\quad\text{from Rung 4}\\ x_{3}=\frac{7}{4}-\frac{\left( \frac{7}{4}\right) ^{2}-3}{2\times\frac{7}{4}}=\frac{97}{56}\quad\text{from Rung 8} \end{array} \] So the doubling pattern comports with the case for \(\sqrt{3}\) to this point. Can that pattern be proved? Let us see.

The above version of the \(\sqrt{3}\) ladder is standard, but finding a general term for the sequences \(\{a_{n}\}\) and \(\{b_{n}\}\) from the rungs \(\langle a_{n}\quad b_{n}\rangle\) as presented is not immediate, since the rungs have been reduced when possible. Here is the \(\sqrt{3}\) Greek Ladder without rung reductions: \[ \begin{array}{cc} 1 & 1\\ 2 & 4\\ 6 & 10\\ 16 & 28 \end{array} \qquad \begin{array}{cc} 44 & 76\\ 120 & 208\\ 328 & 568\\ 896 & 1552 \end{array} \] And now, a recursive definition of the rungs \(\langle a_{n}\quad b_{n}\rangle\) of this equivalent version of the \(\sqrt{3}\) Greek Ladder is suggested and given by \[ \begin{align*} a_{1} & =1\text{, }a_{2}=2\text{, and for }n>2\text{, }a_{n}=2a_{n-1} +2a_{n-2};\\ b_{1} & =1\text{, }b_{2}=4\text{, and for }n>2\text{, }b_{n}=2b_{n-1}+2b_{n-2} \end{align*} \] (It is left to the reader to show that this is equivalent to the standard definition given earlier for the \(\sqrt{3}\) ladder.) Using the same method of [4] again, the \(n\)-th rung \(\langle a_{n}\quad b_{n}\rangle\) is \[ \left\langle \frac{\left( 1+\sqrt{3}\right) ^{n}-\left( 1-\sqrt{3}\right)^{n}}{2\sqrt{3}}\qquad\frac{\left( 1+\sqrt{3}\right) ^{n}+\left( 1-\sqrt{3}\right) ^{n}}{2}\right\rangle\]

So let us see what happens when \(\frac{b_{n}}{a_{n}}\) is chosen as an estimate in Newton's Method. The corresponding approximation for \(\sqrt{3}\) deriving from the \(n\)-th rung simplifies to \[ \frac{b_{n}}{a_{n}} = \frac{\sqrt{3}\left( \sqrt{3}+1\right) ^{n}+\sqrt{3}\left( 1-\sqrt{3}\right) ^{n}}{\left( \sqrt{3}+1\right) ^{n}-\left( 1-\sqrt{3}\right) ^{n}} \] When this fraction is subjected to Newton's Method for \(\sqrt{3}\), you can check that the result is \[ \frac{\sqrt{3}\left[ \left( 1+\sqrt{3}\right) ^{2n}+\left( 1-\sqrt{3}\right) ^{2n}\right] }{\left(1+\sqrt{3}\right) ^{2n}-\left(1-\sqrt{3}\right) ^{2n}} \] which is the reduced form of the fraction \(\frac{b_{2n}}{a_{2n}}\) from the \(2n\)-th rung of the ladder, so the doubling is established for the \(\sqrt{3}\) ladder.

Since the doubling pattern holds for the ladders of \(\sqrt{2}\) and \(\sqrt{3}\), it is natural to ask if it holds for the \(\sqrt{k}\) Greek Ladder, in which each rung \(\langle a\quad b\rangle\) is followed by the rung \(\langle a+b\quad ka+b\rangle\) That ladder begins \[ \begin{array}{ccc} 1 & 1 & \frac{1}{1}\\ 2 & k+1 & \frac{k+1}{2}\\ k+3 & 3k+1 & \frac{3k+1}{k+3}\\ 4k+4 & k^{2}+6k+1 & \frac{k^{2}+6k+1}{4k+4}\\ k^{2}+10k+5 & 5k^{2}+10k+1 & \frac{5k^{2}+10k+1}{k^{2}+10k+5}\end{array} \] giving rise to the recursive definition \[ \begin{align*} a_{1} & =1\text{, }a_{2}=2\text{, and for }n>2\text{, }a_{n}=2a_{n-1}+\left( k-1\right) a_{n-2};\\ b_{1} & =1\text{, }b_{2}=k+1\text{, and for }n>2\text{, }b_{n} =2b_{n-1}+\left( k-1\right) b_{n-2} \end{align*} \] It is again left to the reader to show equivalence in definitions. Working from [4] again leads to \[ a_{n}=\frac{\left( 1+\sqrt{k}\right)^{n}-\left( 1-\sqrt{k}\right)^{n}}{2\sqrt{k}}\text{ and }b_{n}=\frac{\left( 1+\sqrt{k}\right)^{n}+\left( 1-\sqrt{k}\right)^{n}}{2} \] So the corresponding Greek Ladder approximation to \(\sqrt{k}\) is \[ \frac{b_{n}}{a_{n}}=\frac{\sqrt{k}\left( 1-\sqrt{k}\right)^{n}+\sqrt{k}\left( \sqrt{k}+1\right)^{n}}{\left( \sqrt{k}+1\right)^{n}-\left( 1-\sqrt{k}\right)^{n}} \] and the Newton formula yields \[ \begin{align*} & \frac{\sqrt{k}\left( 1-\sqrt{k}\right) ^{n}+\sqrt{k}\left( \sqrt{k}+1\right)^{n}}{\left( \sqrt{k}+1\right)^{n}-\left( 1-\sqrt{k}\right)^{n}}-\frac{\left( \frac{\sqrt{k}\left( 1-\sqrt{k}\right)^{n}+\sqrt
{k}\left( \sqrt{k}+1\right)^{n}}{\left( \sqrt{k}+1\right)^{n}-\left(
1-\sqrt{k}\right)^{n}}\right)^{2}-k}{2\times\frac{\sqrt{k}\left(1-\sqrt{k}\right)^{n}+\sqrt{k}\left( \sqrt{k}+1\right)^{n}}{\left(\sqrt{k}+1\right)^{n}-\left( 1-\sqrt{k}\right)^{n}}}\\ & =\frac{\sqrt{k}\left( \sqrt{k}+1\right)^{2n}+\sqrt{k}\left( 1-\sqrt{k}\right)^{2n}}{\left( \sqrt{k}+1\right)^{2n}-\left( 1-\sqrt{k}\right)^{2n}} \end{align*} \] But is this the fraction from the \(2n\)-th rung of the ladder? That rung is \[ \left\langle \frac{\left( 1+\sqrt{k}\right)^{2n}-\left( 1-\sqrt{k}\right)^{2n}}{2\sqrt{k}}\qquad\frac{\left( 1+\sqrt{k}\right)^{2n}+\left(1-\sqrt{k}\right)^{2n}}{2}\right\rangle \] which gives the approximation \[ \frac{\frac{\left( 1+\sqrt{k}\right)^{2n}+\left( 1-\sqrt{k}\right)^{2n}}{2}}{\frac{\left( 1+\sqrt{k}\right)^{2n}-\left( 1-\sqrt{k}\right)^{2n}}{2\sqrt{k}}}=\frac{\sqrt{k}\left( \sqrt{k}+1\right) ^{2n}+\sqrt{k}\left(
1-\sqrt{k}\right)^{2n}}{\left( \sqrt{k}+1\right)^{2n}-\left( 1-\sqrt{k}\right)^{2n}} \] as it should.

Robert J. Wisner (New Mexico State University), "The Classic Greek Ladder and Newton's Method," Convergence (April 2010), DOI:10.4169/loci003330