International Journal of Mathematical Education in

Science and Technology, Vol. 36, No. 4, 2005, 389398

Theons ladder for any root
THOMAS J. OSLER*, MARCUS WRIGHT and MICHAEL ORCHARD
Mathematics Department, Rowan University, Glassboro NJ 08028, USA
(Received 2 February 2004 )
Theons ladder is an ancient algorithm for calculating rational approxima-
tions for

2
p
. It features two columns of integers (called a ladder), in which
the ratio of the two numbers in each row is an approximation to

2
p
.
It is remarkable for its simplicity. This algorithm can easily be generalized
to nd rational approximations to any square root. In this paper we show
how Theons original method is naturally generalized for the calculation
of any root,

c
n
p
, where 1<c. In the generalization given here we require
n columns of numbers as we generate rational approximations to an nth
root. Several dierent recursion relations for the numbers that appear in the
ladder are given, and a generating function for calculating the nth row of
the ladder is found. Methods of increasing the rate of convergence are given,
and a method of reducing the n-column ladder to a 2-column ladder is
shown.
1. Introduction
Theon of Smyrna (ca AD 140) described a remarkably simple way to calculate
rational approximations to

2
p
. It has become known as Theons ladder and is
shown below.
1 1
2 3
5 7
12 17
29 41
.
.
.
.
.
.
Each rung of the ladder contains two numbers. Call the left-hand number on the
nth rung x
n
and the right-hand number y
n
. We see that x
n
x
n1
y
n1
and
that y
n
x
n
x
n1
. So the next rung of the ladder has x
6
29 41 70,
International Journal of Mathematical Education in Science and Technology
ISSN 0020739X print/ISSN 14645211 online # 2005 Taylor & Francis Group Ltd
http://www.tandf.co.uk/journals
DOI: 10.1080/00207390512331325969
*Corresponding author. Email: [email protected]
and y
6
70 29 99. The ratio of the two numbers on each rung, y
n
/x
n
, gives us
successively better approximations to

2
p
.
1 1 1=1 1:00000
2 3 3=2 1:50000
5 7 7=5 1:40000
12 17 17=12 1:41666
29 41 41=29 1:41379
70 99 99=70 1:41428
169 239 239=169 1:41420
In [1] this ladder was generalized to obtain

c
p
, where 1 4c, by using the recursion
relations x
n
x
n1
y
n1
, and y
n
x
n
(c 1)x
n1
. In this paper we show how to
extend the ladder to obtain any root

c
N
p
. We will see that a three-column ladder
produces cube roots, a four-column ladder produces fourth roots, etc. For example,
to obtain

2
3
p
we use the ladder
x
n
y
n
z
n
z
n
=y
n
1 1 1 1=1 1:00000000
3 4 5 5=4 1:25000000
12 15 19 19=15 1:26666667
46 58 73 73=58 1:25862069
177 223 281 281=223 1:260089686
Here the elements of the ladder are calculated from x
n1
x
n
y
n
z
n
, y
n 1

x
n 1
(c 1)x
n
and z
n 1
y
n 1
(c 1)y
n
, with c 2. We see that the ratio z
n
/y
n
approaches

c
3
p

2
3
p
1.25992105.
The numerical calculation of roots using this ladder is extremely simple for
students to understand. The theory behind the ladder requires only a knowledge of
linear algebra.
2. The ladder for any root
Let the elements of a general ladder with N columns be denoted in the following way:
x
1
1 x
1
2 x
1
N
x
2
1 x
2
2 x
2
N

x
n
1 x
n
2 x
n
N

Let the recursion relations for calculating the elements of rung n 1 from previously
calculated elements on that rung and the previous rung be
x
n1
1 x
n
1 x
n
2 x
n
N
x
n1
2 x
n1
1 c 1x
n
1
x
n1
3 x
n1
2 c 1x
n
2
.
.
.
x
n1
N x
n1
N 1 c 1x
n
N 1
390 T. J. Osler et al.
For the moment, we assume that the following two limits exist:
lim
n!1
x
n
k
x
n
k 1
k for k 2, 3, . . . , N 2:1
lim
n!1
x
n1
k
x
n
k
k for k 1, 2, . . . , N 2:2
Later, in section 6, we will prove the existence of these limits.
Theorem 2.1. If the limits (2.1) and (2.2) exist, then 1 2 3 N
and 2 3 4 N.
Proof. Starting with x
n1
k x
n1
k 1 c 1x
n
k 1, (valid for
k 2, 3, . . . , N ), we divide by x
n1
k 1 to get
x
n1
k
x
n1
k 1
1 c 1
x
n
k 1
x
n1
k 1
Passing to the limit we get
k 1
c 1
k 1
or
kk 1 k 1 c 1, for k 2, 3, . . . , N 2:3
Next divide x
n1
k x
n1
k 1 c 1x
n
k 1 by x
n
k to get
x
n1
k
x
n
k

x
n1
k 1
x
n
k 1
x
n
k 1
x
n
k
c 1
x
n
k 1
x
n
k
Passing to the limit we get
k
k 1
k

c 1
k
or
kk k 1 c 1, true for k 2, 3, . . . , N 2:4
From equations (2.3) and (2.4) it is clear that k k 1 for k 2, 3, . . . , N.
Thus 1 2 3 N, and we will call k . Again, from (2.3)
we see that k 1 c 1= for k 2, 3, . . . , N. Thus 2 3 4
N, and we will call k . This proves the theorem.
Now equation (2.3) can be written as
1 c 1 2:5
Notice that
lim
n!1
x
n
4
x
n
2
lim
n!1
x
n
4
x
n
3
x
n
3
x
n
2

2
This simple observation can be extended easily to prove the following theorem.
Theons ladder for any root 391
Theorem 2.2. If the limits (2.1) and (2.2) exist, then
lim
n!1
x
n
k p
x
n
k

p
2:6
lim
n!1
x
nq
k
x
n
k

q
2:7
lim
n!1
x
nq
k p
x
n
k

p

q
2:8
Here k, p and q are integers such that the quantities are dened.
Starting with x
n1
1 x
n
1 x
n
2 x
n
N, we divide by x
n
1 to get
x
n1
1
x
n
1
1
x
n
2
x
n
1

x
n
N
x
n
1
Passing to the limit and using Theorem 2.2 we get
1
2

N1
Multiplying this last relation by 1 and using (2.5) we get
c 1 1
2

N1

1
N
1
Thus
N
c, and we have proved the following theorem.
Theorem 2.3. If the limits (2.1) and (2.2) exist, then
N
c. If in addition, c is
positive, then
lim
n!1
x
n
k 1
x
n
k

c
N
p
, where k 1, 2, . . . , N 1
3. The multinomial connection
In [2], the remarkable binomial connection 1

c
p

n
x
n
2 x
n
1

c
p
was demon-
strated for the case where N2. In this section we show how this binomial relation is
generalized for arbitrary N. First we prove the following lemma, which shows how to
calculate the elements on rung n 1 using only the elements of rung n.
Lemma 3.1. The following recursion relations are true:
x
n1
1 x
n
1 x
n
2 x
n
3 x
n
4 x
n
N
x
n1
2 x
n
1c x
n
2 x
n
3 x
n
4 x
n
N
x
n1
3 x
n
1c x
n
2c x
n
3 x
n
4 x
n
N
x
n1
4 x
n
1c x
n
2c x
n
3c x
n
4 x
n
N
.
.
.
x
n1
N x
n
1c x
n
2c x
n
3c x
n
N 1c x
n
N
392 T. J. Osler et al.
Proof. The rst relation, for x
n1
(1), is the relation we have used to dene it.
The second relation follows from
x
n1
2 x
n1
1 c 1x
n
1 x
n
1 x
n
2 x
n
N c 1x
n
1
x
n
1c x
n
2 x
n
3 x
n
4 x
n
N :
The remaining relations follow in the same way.
Let ! exp2pi=N, where p is any integer, so !
N
1. We will prove the
following:
Theorem 3.1. If x
1
1 x
1
2 x
1
3 x
1
N 1, then
x
n
N x
n
N 1!c
1=N
x
n
N 2!
2
c
2=N
x
n
1!
N1
c
N1=N

1 !c
1=N
!
2
c
2=N
!
N1
c
N1=N

n
: 3:1
Proof. The proof is by induction on n. The case where n 1 is clear. Assume
equation (3.1) is true for rung n. Then 1 !c
1=N
!
2
c
2=N
!
N1
c
N1=N

n1
is equal to the product of
x
n
N x
n
N 1!c
1=N
x
n
N 2!
2
c
2=N
x
n
1!
N1
c
N1=N

and
1 !c
1=N
!
2
c
2=N
!
N1
c
N1=N

:
This product is
x
n
N x
n
N 1 !c
1=N
x
n
N 2 !
2
c
2=N
x
n
1!
N1
c
N1=N
x
n
1 c x
n
N !c
1=N
x
n
N 1 !
2
c
2=N
x
n
2!
N1
c
N1=N
x
n
2 c x
n
1 c!c
1=N
x
n
N !
2
c
2=N
x
n
3!
N1
c
N1=N

x
n
N 1 c x
n
N 2 c!c
1=N
x
n
N 3 c!
2
c
2=N
x
n
N!
N1
c
N1=N
Summing by columns we get
x
n
N x
n
N 1c x
n
N 2c x
n
N 3c x
n
1c
x
n
N x
n
N 1 x
n
N 2c x
n
N 3c x
n
1c !c
1=N
x
n
N x
n
N 1 x
n
N 2 x
n
N 3c x
n
1c !
2
c
2=N

x
n
N x
n
N 1 x
n
N 2 x
n
N 3 x
n
1 !
N1
c
N1=N
The result now follows at once from Lemma 3.1.
Notice that equation (3.1) states that the expression 1 !c
1=N
!
2
c
2=N

!
N1
c
N1=N

n
is a generating function for the elements of the nth rung.
4. The matrix connection
The results of Lemma 3.1 show that we should consider introducing the following
vectors and matrices. Let x
n
x
n
1, x
n
2, x
n
3, . . . , x
n
N . We will use vectors
Theons ladder for any root 393
as rows and as columns as the need arises without changing the vector notation.
Let the important matrix implied by Lemma 3.1 with N rows and columns be
denoted by
MN
1 1 1 1 1
c 1 1 1 1
c c 1 1 1
c c c 1 1

c c c c 1

From Lemma 3.1 we then have

x
n1
MN x
n
4:1
First we prove a lemma which will show that M(N) is not singular when c 6 1.
Lemma 4.1. The determinant of the matrix M(N) is given by det(M(N)) (1c)
N1
.
Proof. In M(N), subtract column 1 from each column. The rst row becomes
1 0 0 0 . . . 0. Expand by the rst row. The rst (n 1) (n 1) minor has (1 c)
along its major diagonal and zeroes everywhere beneath. Thus det(M(N))
(1c)
N1
.
Theorem 4.1. Let 1<c and ! e
2i=N
. Then the eigenvalues and corresponding
eigenvectors for the matrix M(N) are
l
k
1 !
k1
c
1=N
!
2k1
c
2=N
!
N1k1
c
N1=N
4:2
v
k

1, !
k1
c
1=N
, !
2k1
c
2=N
, . . . , !
N1k1
c
N1=N

, 4:3
for k 1, 2, 3, . . . , N. Also, the eigenvectors are linearly independent.
Proof. Direct substitution of the eigenvalues and eigenvectors shows that the
relations MNv
k
l
k
v
k
are true for k 1, 2, 3, . . . , N.
It remains to show that the eigenvectors are linearly independent. We must
show that if

1
v
1

2
v
2

N
v
N
0
then numbers
1
,
2
, . . . ,
N
, are all zero. This means that we examine the system of N
equations

3

N
0

2
!
3
!
2

4
!
3

N
!
N1
0

2
!
2

3
!
4

4
!
6

N
!
2N1
0

2
!
3

3
!
6

4
!
9

N
!
3N1
0
.
.
.

2
!
N1

3
!
2N1

4
!
3N1

N
!
N1N1
0
and show that the only solution is
1

2

N
0. The equation

2
z
3
z
2

4
z
3

N
z
N1
0 can have at most N1 distinct roots
if all the coecients are not zero. But the above equations show that we have
394 T. J. Osler et al.
N roots z 1, !, !
2
, . . . , !
N1
. Thus all the coecients
k
0 for k 1, 2, 3, . . . , N,
and the theorem is proved.
The rst rung of the ladder is given in our vector notation by x
1
and by the
previous theorem, can be expanded in terms of the eigenvectors as
x
1
a
1
v
1
a
2
v
2
a
N
v
N
where a
1
, a
2
, a
3
, . . . , a
N
are appropriately chosen constants. Then
x
n1
M
n
Nx
1
M
n
N a
1
v
1
a
2
v
2
a
N
v
N

a
1
l
n
1
v
1
a
2
l
n
2
v
2
a
N
l
n
N
v
N
:
Writing out the components of x
n1
from the above relation and using expression
(4.3) we can calculate the numbers on any rung from the eigenvalues.
x
n1
1 a
1
l
n
1
a
2
l
n
2
a
3
l
n
3
a
N
l
n
N
x
n1
2 a
1
l
n
1
a
2
l
n
2
! a
3
l
n
3
!
2
a
N
l
n
N
!
N1

c
1=N
x
n1
3 a
1
l
n
1
a
2
l
n
2
!
2
a
3
l
n
3
!
22
c
2=N
a
N
l
n
N
!
2N1

c
2=N
4:4
.
.
.
x
n1
N a
1
l
n
1
a
2
l
n
2
!
N1
a
3
l
n
3
!
N12
a
N
l
n
N
!
N1N1

c
N1=N
5. Proof that the limits exist
It is now possible to prove that the limits considered above exist.
Theorem 5.1. Let the rst rung of the ladder be x
1
a
1
v
1
a
2
v
2
a
N
v
N
, and
let v
1
, v
2
, . . . , v
N
be the eigenvectors given by (4.3). If 1 < c and a
1
6 0, then the limits
k lim
n!1
x
n
k
x
n
k 1
for k 2, 3, . . . , N 5:1

k lim
n!1
x
n1
k
x
n
k
, for k 1, 2, . . . , N 5:2
exist.
Proof. From equation (4.4) we have
x
n1
k
x
n
k

a
1
l
n
1
a
2
l
n
2
!
k1
c
1=N
a
3
l
n
3
!
k12
c
2=N
a
N
l
n
N
!
k1N1
c
N1=N
a
1
l
n1
1
a
2
l
n1
2
!
k1
c
1=N
a
3
l
n1
3
!
k12
c
2=N
a
N
l
n1
N
!
k1N1
c
N1=N
Dividing numerator and denominator by l
n1
1
we have
x
n1
k
x
n
k

a
1
l
1
a
2
l
2
l
n1
2
=l
n1
1
!
k1
c
1=N
a
3
l
3
l
n1
3
=l
n1
1
!
k12
c
2=N

a
N
l
N
l
n1
N
=l
n1
1
!
k1N1
c
N1=N

a
1
a
2
l
n1
2
=l
n1
1
!
k1
c
1=N
a
3
l
n1
3
=l
n1
1
!
k12
c
2=N

a
N
l
n1
N
=l
n1
1
!
k1N1
c
N1=N

Theons ladder for any root 395
Since
l
h
l
1

<1 for h 2, 3, . . . , N
we see that
lim
n!1
l
n
h
l
n
1
0
Thus
lim
n!1
x
n1
k
x
n
k
l
1
, for k 1, 2, . . . , N
and we have shown that the limits (5.2) exist. Notice that
l
1
1 c
1=N
c
2=N
c
N1=N

c 1
c
1=N
1
which agrees with Theorem 2.3 and equation (2.5). From equation (2.3) it follows
that the limits (5.1) exist and the theorem is proved.
6. Skipping rungs of the ladder
The convergence of the ladder is slow, and we can improve the convergence in a
simple way. Let ! 1 in equation (3.1) and square to obtain
x
n
N x
n
N 1c
1=N
x
n
N 2c
2=N
x
n
1c
N1=N

2
1 c
1=N
c
2=N
c
N1=N

2n
x
2n
N x
2n
N 1c
1=N
x
2n
N 2c
2=N
x
2n
1c
N1=N

: 6:1
It is instructive to study a few special cases of the above relations. If N2 we get
x
n
2 x
n
1c
1=2

2
x
n
2
2
x
n
1
2
c

2x
n
1x
n
2c
1=2
x
2n
2 x
2n
1c
1=2
Thus we have
x
2n
1 2x
n
1x
n
2
x
2n
2 x
n
2
2
x
n
1
2
c 6:2
Again, if N3 in equation (6.2) we get
x
n
3 x
n
2c
1=3
x
n
1c
2=3

2
x
2
n
3 2x
n
1x
n
2c

x
2
n
1c 2x
n
2x
n
3

c
1=3
x
2
n
2 2x
n
1x
n
3

c
2=3
x
2n
3 x
2n
2c
1=3
x
2n
1c
2=3
396 T. J. Osler et al.
Thus we conclude that
x
2n
1 x
2
n
2 2x
n
1x
n
3
x
2n
2 x
2
n
1c 2x
n
2x
n
3
x
2n
3 x
2
n
3 2x
n
1x
n
2c
6:3
For general N and 1 4m4N, we have
x
2n
m c

m1
k1
x
n
kx
n
mk

N
km
x
n
kx
n
N mk 6:4
Using equation (6.4), the elements in rung 2n can be calculated from the elements
on rung n. The resulting limit of the ratio
x
2n
m1
x
2n
m
converges quadratically to c
1=N
for 1<c. (We will not demonstrate this quadratic
convergence.)
7. N columns reduced to two columns
We will now show how to reduce our N column ladder to a two-column ladder. We
begin by considering the case where N3. The fundamental recursion relations are
x
n1
1 x
n
1 x
n
2 x
n
3 7:1
x
n1
2 x
n1
1 c 1x
n
1 7:2
x
n1
3 x
n1
2 c 1x
n
2 7:3
Using equation (7.2) to eliminate x
n
2 and x
n1
2 from equation (7.3) we get
x
n1
3 x
n1
1 c 1x
n
1 c 1 x
n
1 c 1x
n1
1
x
n1
1 2c 1x
n
1 c 1
2
x
n1
1
Using this last result and equation (7.2) with (7.1) we get
x
n1
1 3x
n
1 3c 1x
n1
1 c 1
2
x
n2
1
This last relation combined with equation (7.2) allows us to calculate a two-column
ladder to estimate c
1=3
. The resulting ladder contains the rst two columns of the
original three-column ladder for c
1=3
.
In the same way, we can reduce our general N-column ladder to a two-column
ladder using
x
n1
1

N
m1
N
m

c 1
m1
x
nm1
1
x
n1
2 x
n1
1 c 1x
n
1
7:4
Equation (7.4) is not only true for the rst column, but it is true for all columns as
shown in the following theorem.
Theons ladder for any root 397
Theorem 7.1. For 1 4k 4N we have
x
n1
k

N
m1
N
m

c 1
m1
x
nm1
k 7:5
Proof. Our proof is by induction on k. By equation (7.4), the result is true for
k 1. Assume equation (7.5) is true for a specic k, with k<N. We investigate
x
n1
k 1. We have
x
n1
k 1 x
n1
k c 1x
n
k
From the induction hypothesis we have
x
n1
k 1

N
m1
N
m

c 1
m1
x
nm1
k c 1

N
m1
N
m

c 1
m1
x
nm
k

N
m1
N
m

c 1
m1
x
nm1
k c 1x
nm
k

N
m1
N
m

c 1
m1
x
nm1
k 1
The theorem is proved.
8. Final remarks
In [2], Eisenberg gave another discussion of an algorithm for the square root
identical to the one used in Theons ladder. In his excellent book [3], Young
describes Theons ladder for the square root and gives several interesting problems
related to it on pages 1011, 3841 and 9697. Gould gave several interesting
algorithms related to this work in [4].
References
[1] Giberson, S., and Osler, T.J., 2004, Extending Theons ladder to any square root. To
appear in The College Mathematics Journal, 35, 222226.
[2] Eisenberg, T., 2003, On an unknown algorithm for computing square roots. International
Journal of Mathematical Education in Science and Technology, 34, 153158.
[3] Young, R.M., 1992, Excursions in Calculus, An Interplay of the Continuous and the Discrete
(Reston, VA: The Mathematical Association of America).
[4] Gould, H.W., 1959, An iterative approximation for nding the n-th root of a number.
Mathematics Magazine, 33(2), 6169.
398 T. J. Osler et al.