Search

## Search Loci: Convergence:

Keyword

Random Quotation

Look somewhere else for someone who can follow you in your researches about numbers. For my part, I confess that they are far beyond me, and I am competent only to admire them.
[Written to Fermat]

In G. Simmons Calculus Gems, New York: McGraw Hill Inc., 1992.

See more quotations

# The Classic Greek Ladder and Newton's Method

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

Pages: | 1 |  2 |  3 |  4 |  5 |  6 |

Wisner, Robert J., "The Classic Greek Ladder and Newton's Method," Loci (August 2009), DOI: 10.4169/loci003330

I read with big interest this article of Dr. Robert J. Wisner (also the article on the same subject ÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬Ãƒâ€¦Ã¢â‚¬Å“A disquisition of the square root of threeÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬ÃƒÂ¯Ã‚Â¿Ã‚Â½). It is very rewarding for a lover of mathematics as I am to find in Convergence article always very clear and very appealing. The only point that was not clear to me in this article was relevant to the ÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬Ãƒâ€¦Ã¢â‚¬Å“rating systemÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬ÃƒÂ¯Ã‚Â¿Ã‚Â½. I understand from a personal E-mail interchanged with Prof. Wisner that in Diophantine approximation the goal is to get a good approximation with a minimal denominator, but following this line for sqrt(3) we can have these approximations: 5/3 with a rating of (-2,1) and a value 5/3=1,66666666666667 Or 19/11 with a rating of (-2,2) and a value 19/11 = 1,72727272727273 But the real value of sqrt(3) is 1,732051 therefore 5/3 is far from the value Following the explanation ÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬Ãƒâ€¦Ã¢â‚¬Å“in Diophantine approximation the goal is to get a good approximation with a minimal denominatorÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬ÃƒÂ¯Ã‚Â¿Ã‚Â½ there is no need for proceed along the ÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬Ãƒâ€¦Ã¢â‚¬Å“greek ladderÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬ÃƒÂ¯Ã‚Â¿Ã‚Â½ because the approximation with a minimal denominator is always the first rung I like to share also a my explanation of the formula reported for the ÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬Ãƒâ€¦Ã¢â‚¬Å“greek ladderÃƒÆ’Ã‚Â¢ÃƒÂ¢Ã¢â‚¬Å¡Ã‚Â¬ÃƒÂ¯Ã‚Â¿Ã‚Â½, always said that is not known how was found For me this was the way If we say that b/a = sqrt(N) we have b^2/a^2 = N if we add to both said b/a we have b/a + b^2/a^2 = N + b/a b/a ( 1+b/a) = N + b/a b/a = [N+ b/a] / (1+b/a) and with some manipulation b/a = (a *N +b) /(a+b) from which bn = an-1 * N + bn-1 an = an-1 + bn-1 Best reagards Luigi Rivara