\magnification=1200
\input graphicx.tex %
%\includegraphics{<filename>}
\def\dessin#1#2#3{\vbox to #2%
  {\vfill\special{picture #3}\hrule width#1 height 0pt depth 0pt}}

\def\Diag{\def\normalbaselines{\baselineskip25pt\lineskip3pt\lineskiplimit3pt}%
        \matrix}
\def\hfleche#1#2{\smash{\mathop{\vbox{\hbox to 8.5mm{{#1}}}}\limits^{#2}}}
\def\vfleche#1#2{\bigg #1 \rlap{$\vcenter{\hbox{$\scriptstyle#2$}}$}}
\newcount\largeur
\newcount\hauteur
\newcount\interligne
\newdimen\Largeur
\newskip\pd


\def\insertion#1#2#3#4{ 
\largeur=#1 
\ifnum\largeur>0 
				\Largeur=\largeur mm\advance\largeur by 5 
    \else \Largeur=-\largeur mm\advance\largeur by -5 \fi 
\hauteur=#3 
\multiply\hauteur by 186467 
\interligne=\baselineskip 
\divide\hauteur by \interligne 
\advance\hauteur by 1 
\smallbreak 
\vskip-\baselineskip \vskip\prevdepth \pd=-\prevdepth 
\ifnum\largeur>0 
     \leftline{\vbox to 0pt{\dessin {\Largeur}{#2mm}{#4} \vss}} 
     \else\rightline{\vbox to 0pt{\dessin {\Largeur}{#2mm}{#4} \vss}}\fi 
\vskip\pd 
\hangindent=\largeur mm 
\hangafter=-\hauteur 

 \hfil\vbox to #2 mm{\hsize\hauteur mm
\vfill#4\vfill}}

\long\def\Insertion#1#2#3#4{\smallbreak 
\largeur=#1 
\hauteur=141%%%%%%%%%%%%%%   mm pour \hsize=170 truemm
\ifnum\largeur>0 
				\advance\hauteur by -\largeur 
    \else \advance\hauteur by\largeur\fi 
\advance\hauteur by -5 
\line{%
\ifnum\largeur<0 
    \vbox to #2 mm{\hsize\hauteur mm \vfill#4\vfill} 
        \hfil\dessin{-\largeur mm}{#2 mm}{#3} 
	   \else\dessin{\largeur mm}{#2 mm}{#3} 
        \hfil\vbox to #2 mm{\hsize\hauteur mm
\vfill#4\vfill}\fi  }}

\def\Par{\hfil\vadjust{\vskip\parskip}\break\indent}

% Dessin au milieu: avec \insertion, et justifi\'e \`a gauche avec \Insertion
% les arguments sont les dimensions du cadre en mm, \'echelle 800=80%
%le texte vient en derni\`ere accolade.
\def\Par{\par\noindent}
\centerline{CONTINUED FRACTIONS}\vskip.3cm
\centerline{Lecture at the August 1993 JAMS Seminar at Yamaguchi}\vskip.3cm
\centerline{Bernard Teissier}
\vskip.4cm\noindent

\Par\vskip.5cm\noindent
\S 1 Anthyphairesis: how the Greeks compared lengths.\vskip.2truecm\Par
The method we learn at school to compare two lengths is to
measure them in centimeters or some other unit, and compute the ratio
of the two resulting numbers. The Greek Mathematicians 2.500
years ago used a completely different method, which requires no unit: given two straight
segments, they measured how many times the smaller one goes into the bigger one, thus
obtaining an integer $u_0$ and possibly a rest, smaller than the
smaller length. Then they measured how many times this rest or
remainder goes into the smaller length, thus getting a second integer
$u_1$ and a second remainder smaller than the first, computed how many times this
second remainder went into the first, and they continued like that, so that for them a ratio was
a sequence, finite or not, of integers. This procedure, which you can physically begin to
perform on two rods, was called
 \it Anthyphairesis \rm ($\alpha\nu\theta\upsilon\phi\alpha\iota\rho\epsilon\sigma\iota
s$)\par It looks very much like the division algorithm of Euclid, but I insist that
it is also a physical manipulation, is not primarily concerned with finding the greatest
common divisor of two integers, and as we shall see has a much larger scope. \Par
The mathematical model of this operation is as follows: let $L>l$ be the lengths
of the two rods. The integer $u_0$ is the greatest integer less than $L\over
l$, denoted by $[{L\over l}]$, so that 
$${L\over l}=u_0+ {L-u_0l\over
l}, \ \hbox{with}\ u_0\geq 1\ \hbox{and}\ \ 0\leq {L-u_0l\over
l}<1.$$  If this remainder is $0$, we stop and write ${L\over l}=u_0$. Otherwise
we repeat the operation with ${l\over L-u_0l}>1$; set $$ u_1= [{l\over L-u_0l}] ,$$ and so on.
Finally we write

$${L\over l}=u_0+{1\over\displaystyle u_1+{\strut 1
\over\displaystyle u_2 +{\strut 1
\over\ldots \displaystyle u_k+{\strut 1
\over\displaystyle { \ldots}}}}}$$
The right hand side is symbolized by $[u_0,u_1,\ldots ,u_k,\ldots]$
and called the continued fraction expansion of the ratio $L\over l$.\vskip.3cm
  \Par \S 2  Computations on
continued fractions.\vskip.3cm\Par Let $[u_0,\ldots, u_k, \ldots]$ be a continued
fraction, finite or infinite. For any integer $k$ such that $u_k$ is
defined, the continued fraction $[u_0,\ldots, u_k]$ represents a
rational number $p_k\over q_k$, called the $k-th$ convergent, or approximant.
The first problem we face is to compute $p_k$ and $q_k$. A little
experimentation gives: $$p_0=u_0, q_0=1;\
p_1=u_0u_1+1,q_1=u_1, \ p_2= u_0+u_2(u_0u_1+1), q_2=
1+u_2u_1$$ so that we are led to \it conjecture \rm the general
rule of formation $$ (1) \ \ \ \ \ \ \ \ \ \ \ \ \  \eqalign{ p_{k+1}=&p_{k-1}+u_{k+1}p_k,\cr
q_{k+1}=&q_{k-1}+u_{k+1}q_k}$$ with the initial conditions
$p_0=u_0,\ q_0=1$. \Par Let us prove these formulas \it by
induction \rm on the integer $k$. Assume that they hold until the
computation of $p_k$; for $q_k$ it is the same proof. \Par 
The main idea is to think of $p_k$ or $q_k$ as a function of $u_0,\ldots ,u_k$. Then we get
$p_{k+1}$ or $q_{k+1}$ by substituting $u_k+{1\over u_{k+1}}$ for $u_k$ in this
expression. In fact $p_k$ and $q_k$ are \it polynomials \rm in $u_0,\ldots ,u_k$. If we
assume that we know that $p_k=p_{k-2}+u_kp_{k_1}$ this gives 
$$\eqalign{& p_{k+1}=p_{k-2}+(u_k+{1\over u_{k+1}})p_{k-1} = {1\over
u_{k+1}}(p_{k-1}+u_{k+1}(p_{k-2}+u_kp_{k-1}))=\cr & {1\over
u_{k+1}}(p_{k-1}+u_{k+1}p_k)}$$ and so as we have the same computation for $q_{k+1}$,
we may multiply numerator and denominator by $u_{k+1}$ and get $$\eqalign
{&p_{k+1}=p_{k-1}+u_{k+1}p_k\cr &q_{k+1}=q_{k-1}+u_{k+1}q_k}.$$ This proves that if
our formula is true for an integer $k$ it is true for $k+1$. Since it is true for $0$ it is true
for all integers.\par This will allow us to compute all the $p_k,q_k$ easily if we know the
integers $u_k$, but of course in practice the difficulty is to compute these integers from
a given ratio problem. However we shall see that the expression we just proved has
many consequences.\Par
The first one is \par\vskip.3truecm\noindent
Theorem 1: For all integers $k$, we have $$(2)\ \ \ \ \ \ \ \ \ \ \ 
p_{k+1}q_k-p_kq_{k+1}=(-1)^k$$ This implies in particular that $p_k, q_k$ have no common
divisor. \Par
Proof: look at the two formulas proved by induction; multiply the first by $q_k$, the
second by $p_k$ and compute the difference of the results: it gives
$p_{k+1}q_k-p_kq_{k+1}=-(p_kq_{k-1}-p_{k-1}q_k)$, and we have
$p_0=u_0,q_0=1,p_1=u_0u_1+1 ,q_1=u_1$, so we get the result by induction.


\Par Let us now see how to compute the
$u_k$.\Par

\vskip.2truecm\noindent
Proposition 2: Let us start from a rational number $L\over l$ with $L,\ l\ >0$. Then the
Euclidean division algorithm coincides with the Anthyphairesis of the ratio $L\over l$.\Par
We divide $L$ by $l$:\Par
$L=u_0l+r_0$ with $r_0<l$\Par
$l=u_1r_0+r_1$ with $r_1<r_0$\Par
etc.....\Par
Since at each step the remainder decreases, after a finite number of steps (at most $l-1$) we
get $0$ and this means that the last step is \Par
$r_{k-2}=u_kr_{k-1}$\Par
Comparison with the Anthyphairesis shows that we have exactly computed the continued
fraction expansion of $L\over l$: $${L\over l}=[u_0,\ldots ,u_k]$$
Note that the greatest common divisor of the integers $L$ and $l$ is $r_{k-1}$. Nowadays
the Euclidean algorithm is often presented as only a means of computing this g.c.d.\Par
Conversely, any finite continued fraction $[u_0,\ldots ,u_k]$ represents a rational number,
namely $p_k\over q_k$.\Par On the other hand given any positive real number $a$ we can
associate to it a sequence of integers by modelling the Anthyphairesis
construction (we repeat the construction of \S 1 in a slightly more abstract
setting):\Par Let $u_0=[a]$, the integral part of $a$, i.e the greatest integer
less than $a$. (note that the use of $[]$ here is different from above where we use brackets to
denote a continued fraction, but in the continued fraction writing there are only integers
between the $[]$, and in the integral part there is only one number. When $a$ is a positive
integer the two notations five the same result!). Note also that here $u_0$ may be $0$, if
$a<1$.\Par Anyway we have $a=u_0+s_0$ with $0\leq s_0<1$. If $s_0=0$, we have $a=u_0$ and
we are finished. If not, set $a_1={1\over s_0}>1$ and let $u_1$ be the integral part of $a_1$; we
repeat the procedure and thus obtain a possibly infinite but uniquely
determined sequence of integers, $[u_0,\ldots u_k,\ldots ]$ corresponding to
the number $a$.\par Note that if this sequence end after finitely many steps,
 it cannot end with 1, and no integer except possibly the first ($u_0$)
may be zero.\Par Recall that $\vert x\vert $ denotes the absolute value of the
number $x$, and therefore $\vert a-b\vert$ is the distance from $a$ to $b$.
Then we have:\par\vskip.3truecm\noindent Theorem 3: To any such sequence
of integers $u_0,\ldots u_k,\ldots $ is associated a unique positive real
number $a$ denoted by $[u_0,\ldots u_k,\ldots ] $ and characterized by the
property that for all integers $k$ we have with the notations introduced
above: $$\vert a-{p_k\over q_k}\vert <{1\over q_kq_{k+1}}.$$ In particular
$a$ is the \it limit \rm of the sequence of rational numbers $p_k\over
q_k$.\Par Proof: Using Theorem 2, we have  $${p_{k+1}\over
q_{k+1}}-{p_k\over q_k} ={(-1)^k\over q_kq_{k+1}}$$  and this implies that
the sequence or rational numbers $p_k\over q_k$ is convergent, that is there
is a real number $a$ such that for an arbitrarily small $e$ the distance from
$p_k\over q_k$ to $a$ is less than $e$ as soon as $k$ is large enough
(depending on $e$ of course). For each integer $k$ we have by the same
computation we did in the beginning (think about this!)
$$(3)\ \ \ \ \
\ \ \ \ \ \  a={p_k+a_{k+2}p_{k+1}\over q_k+a_{k+2}q_{k+1}}\ \hbox{  where}\
a_{k+2}=[u_{k+2}, u_{k+3},\ldots ]$$ so using theorem 2 we get $$(4)\ \ \ \ \
\ \ \ \ \ \   a-{p_k\over q_k}={(-1)^ka_{k+2}\over
q_k(q_k+a_{k+2}q_{k+1})}$$ and since $q_{k+1}>q_k$ we get the result.\Par
Note that in fact this shows with a little work (given as an exercise) a better
approximation: $$(5)\ \ \ \ \ \ \ \ \ \ \   {1\over (u_{k+1}+2)q_k^2 }<\vert a-
{p_k\over q_k}\vert <{1\over u_{k+1}q_k^2}.$$  Since the $q_k$ tend to
infinity with $k$, this says that the sequence of rational numbers $p_k\over
q_k$ \it converges \rm to the real number $a$, and also that the greater
$u_{k+1} $ is the better the approximation. And the reader should check that
the continued fraction expansion of the number $a$ is $[u_0,\ldots ,u_k,\ldots
]$. Note that this correspondance has only one possible ambiguity:  if the
sequence is finite, then $[u_0,\ldots ,u_k,1]= [u_0,\ldots ,u_k+1]$. This is
different from what happens for the decimal expansion where the ambiguity
is greater. For example $0,999\ldots =1,000\ldots$ .\vskip.3truecm\Par
Theorem 4: The continued fraction expansion $a=[u_0,\ldots ,u_k,\ldots ]$
establishes a bijection between positive real numbers and sequences of
integers such that the last one is $\neq 1$. In this bijection rational numbers
correspond to finite sequences.\Par Remark that while the continued fraction
expansion of $p_k\over q_k$ is $[u_0,\ldots ,u_k]$, the continued fraction
expansion of $p_{k+1}\over p_k$ is $[u_{k+1},\ldots ,u_0]$ and the continued
fraction expansion of $q_{k+1}\over q_k$ is $[u_{k+1},\ldots ,u_1]$. This
follows immediately from $(1)$.\vskip.3truecm\noindent

\noindent
\S 3 Computations of continued fractions. The irrationality of
$\sqrt 2$.\Par\vskip.2truecm
In the time of the Greeks (Archimedes) it was known
that a good approximation of the number $\pi$ is $22\over 7$;  the error is less than
$1\over 100$ ; this can be seen by measuring with strings the perimeter of a circle and its
radius and performing the Anthyphairesis of these two lengths: you get $3+ {1\over 7}$. If you do
it very carefully with a large circle you might even get the next approximants $333\over 106$, 
$355\over 113$ which were apparently known to ancient mathematicians, and certainly to the 
Europeans and the Japanese in the 17$^{th}$ century. The continued fraction expansion of $\pi$
begins by $[3,7,15,1,292,1,1,\ldots]$. You should compute how much more information you store
by remembering the first five numbers than by remembering $3,1416$.  \Par In general you can
compute the first few terms of a continued fraction expansions either
 ``physically'' as in this case, or ``mathematically'' by getting a decimal
expansion from theorems in analysis or by ``seeing'' what the continued
fraction expansion has to be, as the famous Indian mathematician
Ramanujan did, or by some geometric method. In one series
 of cases at least one can compute geometrically a whole infinite continued
fraction expansion:\par

It an old story that the Greeks discovered that $\sqrt 2$ is not a rational number.
Today we say that they proved it in the following way: assume that $\sqrt 2={p\over q}$
where we may assume that $p,q$ have no common divisor. Then $p^2=2q^2$ so $p$ is
even, say $p=2p'$. But then $q^2=2p'^2$ so $q$ is also even which is a contradiction!.
This proof is in fact (relatively) quite ''recent '' and it is a reasonable conjecture that the
proof of the ancient Greek mathematicians (before 5 centuries B.C.) was much more clever
and in fact computed $\sqrt 2$, as follows: we know by Pythagoras that $\sqrt 2$ is the
length of the diagonal of a square of side 1. So we want to do the Anthyphairesis of the
diagonal and the side. It will be more convenient to do the Anthyphairesis of (diagonal+side)
and side, which only adds 1 to $u_0$. Notice that this is independant of the size of the
square! We consider the following picture, where we put our square so that its diagonal is
vertical, and construct a larger square with side $S= s+d $. \par\medskip\noindent
\includegraphics{picture1.pdf}
\par\medskip
It is easy to
see on the picture that the diagonal of the big square is
$D=2s+d$. Notice also that $d<2s$ because the diagonal is the
shortest path between two vertices of the square. So let us do
the Anthyphairesis of $S+D= 3s+2d$ and $S=s+d$: we have
$S+D=2S + s$ so $u_0=2$ and now ${S+D\over S}=2+{s\over
d+s}=2+{1\over {d+s\over s}}$ so the next step in the
Anthyphairesis of $S+D \over S$ is the Anthyphairesis of $s+d\over
s$ which is the same! \Par
This proves that the sequence of integers is $[2,2,\ldots ,2, 
\ldots ]$ so we have proved
$$1+\sqrt 2=[2,2,\ldots ,2, 
\ldots ]$$
and this is an infinite continued fraction: this shows that $\sqrt 2 $ is irrational, and in addition
we can compute it with arbitrary approximation. \Par From an
algebraic viewpoint, this `` Greek'' computation is a proof of the identity
$$1+\sqrt 2= 2+{1\over 1+\sqrt 2}.$$
Now it is true in general that if a positive real number $a$ is a root of a second degree 
equation with integral coefficients, the
continued fraction expansion of $a$ will become periodic after a finite initial part, that is, if 
$$Aa^2 +Ba+C=0,\ \ A,B,C\ \ 
\hbox{integers, }$$ the continued fraction expansion of $a$ is of the form
$$a=[u_0,\ldots u_j,\overline{u_{j+1},\ldots ,u_{j+l}}]$$ where the bar means that the same
sequence of integers is repeated indefinitely. This is called an \it eventually periodic \rm
continued fraction expansion. \par This result is due to Lagrange, and is a bit delicate (but you
should try to prove it!). The converse
 is much simpler: \Par
If a positive real number has an eventually periodic continued fraction expansion, it is a root of a second degree
equation with integral coefficients. You can do this as an exercise, with the hint that if $${qa+p\over ra+s}, p,q,r,s
\ \ \hbox {integers},\ qs-pr=\pm 1,$$ is a solution of such a quadratic equation, so is $a$. \Par

Now these numbers with eventually periodic continued fraction expansion are determined by
finite data: the numbers $u_k$ before the period starts, and then the period. I believe in
Fowler's idea in [F] that these numbers were considered as ''tame'' by Greek mathematicians,
and that their first serious problems came with numbers like the cubic root of 2, because they
could say nothing about its continued fraction expansion not even decide whether the $u_k$
are bounded or not (most people think they are not). And today we have made essentially no
progress on this problem. I like to think that it is the oldest unsolved problem in Mathematics:
\Par \it say something about the continued fraction expansion of the cubic root of an integer
which is not the cube of another integer.\rm\Par Of course we cannot deduce much from a
beginning like this: $$2^{1/3}=[1,3,1,5,1,1,4,1,1,8,1,14,1,10,2,1,4,12,2,3,2,\ldots ]$$ but a
million terms have now been computed and still no regularity appears, and we have no
theorem. It seems the regularity due to the fact that we have a cubic root manifests itself in a
very subtle manner.\vskip.3truecm
 \Par \S 4
 Continued
fractions and approximation.\par\vskip.3truecm\noindent Now we come to the fact that the
convergents of the continued fraction expansion of a real number give ``best possible
approximation'' of this number by rational numbers, in the sense that the difference $a-{p\over
q}$ is as small as possible among all rational number with denominator less than $q$.\par  The
inequalities $(5)$ show that the approximation of $a$ by $p_k\over q_k$ depends on the size of
$u_{k+1}$ and, through the size of $q_k$, also on all the preceding $u_j$, so that in a way it is a
mixture between the average size of the $u_j$ for $j\leq k+1$ and the size of the individual
$u_{k+1}$. If all the $u_j$ are small, we expect relatively poor approximation, and we shall
make this precise below, but if from time to time there is a very large $u_k$, then we will have
good approximation, which depends both on how large these $u_k$ are, and how often large
$u_k$ appear. \Par 

Let $a$ be a positive real number and let us consider in the plane with coordinates
$(p,q)$ the line $p=aq$ in the quadrant $p\geq 0,\ q\geq 0$. Let us remark first that
because of the computations we have made earlier, the convergents of even order of
the continued fraction expansion of $a$ form an increasing sequence converging to $a$ and the
convergents of odd order form a decreasing sequence converging to $a$. Consider the
line in the plane passing through the points with coordinates $(q_k,p_k)$ and
$(q_{k+2},p_{k+2})$. Again because of our calculations it is the line with equation
$$q_{k+1}p-p_{k+1}q=(-1)^{k+1}$$ I claim that if $k$ is even any point $(\overline q,\overline p)$
such that ${\overline p\over \overline q} <a$ is ``below '' that line, which means that
$q_{k+1}\overline p-p_{k+1}\overline q<(-1)^{k+1}$. Now always by the same computation we
have $$ q_{k+1}a-p_{k+1}={(-1)^{k+1}a_{k+3}\over
q_{k+1}(q_{k+1}+a_{k+3}q_{k+2})}>q_{k+1}{\overline p\over \overline q}-p_{k+1}.$$
Since $k$ is even this implies $q_{k+1}\overline p-p_{k+1}\overline q<0$, but this number
is an integer, so this means $q_{k+1}\overline p-p_{k+1}\overline q\leq -1=(-1)^{k+1}$
which is what we had to prove. \Par
This shows that the set of points with positive integral coordinates below the line
$aq-p=0$ is the intersection of the half planes made of the points lying below the lines
$q_{k+1}p-p_{k+1}q=(-1)^{k+1}$ joining the points $(q_k,p_k)$ and
$(q_{k+2},p_{k+2})$. In other words, in view of the fact that the slopes of these lines are all
differerent, the points $(q_k,p_k)$ with $k$ even (odd) are the \it extreme points \rm of
the \it convex hull \rm of the set of points in the first quadrant with integral coordinates
lying below (above) the line $aq-p=0$. Recall that a subset of Euclidean space (here the
plane) is \it convex \rm if whenever it contains two points, it contains the line segment joining
them. The intersection of two convex sets is convex, and the \it convex hull \rm of a set is the
smallest convex set containing it; it is also the intersection of all convex sets containing it, and
the intersection of all \it half spaces \rm containing it, where a half space (here a half plane) is
the set of points lying on one side of a hyperplane (here a line). Extreme points are points on the
boundary on a convex set which actually determine this convex set.\Par The idea of
this graphic description of the continued fraction expansion is due to
H.J.S. Smith. It was apparently rediscovered by Felix Klein some years later.\par\noindent
%\vskip.2truecm\noindent
\includegraphics{picture2.pdf}\par
It now becomes apparent on the picture, and can be checked by computation, that among
all rational numbers with denominator bounded by some number the convergents provide
the best approximation to $a$.\Par
Let us be more precise: first, I leave as an exercise to prove the following:\Par
Given an integer $k$, with the usual notations, if $a=[u_0,\ldots , u_k,\ldots ]$,
at least one of the following inequalities is true:
$$\vert a-{p_k\over q_k}\vert <{1\over 2q_k^2},\ 
\ \ \ \vert a-{p_{k+1}\over q_{k+1}}\vert <{1\over 2q_{k+1}^2}.$$
Hint: use $(2)$.\Par
It is more difficult to prove the following (see [S]): \Par
Let a positive real number $a$ be given, at let $[u_0,\ldots , u_k,\ldots ]$ be its
continued fraction expansion. If a rational number $p\over q$ satisfies the
inequality 
$$\vert a-{p\over q}\vert <{1\over 2q^2},$$ then ${p\over q}={p_k\over q_k}$ where $k$
is the integer such that $q_k\leq q<q_{k+1}$. So any rational number which
approximates well the number $a$, for a given size of denominator, has to be a
convergent. For example, if $p\over q$ is a rational number different from
$22\over 7$ and $0<q\leq 50$, then 
$$\vert \pi -{22\over 7}\vert <\vert \pi -{p\over q}\vert.$$
The geometric result above is very striking and synthetic, but it does not suffice by far to prove
all results on approximation. Let us first give a quantitative meaning to the intuitive fact that
if all the $u_k$ are small, the number $a$ cannot be well approximated.\Par
So we are going to study the numbers having a continued fraction expansion with $1\leq
u_k\leq M$ for some integer $M$ and all $k\geq 0$.  I claim that :\par\vskip.3truecm\Par
Theorem 5: If $a$ is a number such that $u_k\leq M$ for $k\geq 0$, an inequality
$$\vert a-{p\over q}\vert <{1\over cq^2}$$
cannot hold for infinitely many values of $q$ if $c>{{\sqrt{4+M^2}+\sqrt{4M+M^2}}\over 2}$.
It means that in approximation results $\vert a-{p\over q}\vert <{1\over cq^2}$, not only the
exponent $2$ cannot be improved, but even the constant $c$ cannot be too large.\par
The proof begins by remarking that we may restrict our consideration to convergents since
the critical value of $c$ is $>2$, and relies on the formula $(4)$, which we transform
to: $$\vert a-{p_k\over q_k}\vert = {1\over q_k^2({q_{k+1}\over
q_k}+{1\over a_{k+2}})}$$ so that the constant $c$ has to be larger that
${q_{k+1}\over q_k}+{1\over a_{k+2}}$ for sufficiently large $k$. Now we
have by formula $(1)$ the equality $${q_{k+1}\over q_k}=u_{k+2}+{1\over
{q_k\over q_{k-1}}}\ <\ M+1$$ So that that the sequence ${q_{k+1}\over
q_k}$ has an upper limit (smallest upper bound), which we may denote
by $b$. From the equality above it follows that  $$b-{1\over b}\leq M.$$
Therefore $b$ is smaller that the largest root of the second degree equation
$$X^2-MX-1=0,$$ which is equal to $$M+\sqrt{4+M^2}\over 2$$
It remains to bound the other term of the sum, that is to find a lower bound for the terms
$$a_{k+2}=[u_{k+2},\ldots ,]$$ that is, in effect, a lower bound for all continued fractions having
terms bounded by $M$, which means $1\leq u_k\leq M$. Here we use formula $(2)$ which
has the following consequence: \Par
For some integer $k$, let $$f(X)={p_k+Xp_{k+1}\over q_k+Xq_{k+1}}$$
Then the derivative is $$f'(X)={(-1)^{k+1}\over (q_k+Xq_{k+1})^2}$$
In particular for $k$ even one must decrease $X$ to increase $f(X)$, and the opposite for $k$
odd. From this it easily follows by induction that:\Par
All infinite continued fractions with $u_0\geq 1$ and $u_k\leq M$ for all $k$ are greater than
the continued fraction $$[\overline {1,M}].$$
Now we know how to compute the value of this periodic continued fraction: call it $d$; we
compute $p_0=1, p_1=1+M, q_0=1, q_1=M$ and we have by the periodicity
and formula $(3)$: $$d={1+d(1+M)\over 1+dM},$$ so that $d$ is the positive
root of the equation $$MX^2-MX-1=0$$
This root is equal to $$d={{M+\sqrt{M^2+4M}}\over 2M},$$ and since the product of the roots of
this equation is equal to $-1\over M$, we find that we have the inequality:
$${1\over a_{k+2}}\leq {\sqrt{4M+M^2}-M\over 2}$$ so that finally, for any $\epsilon >0$, for
large enough $k$ we have

$${q_{k+1}\over q_k}+{1\over a_{k+2}}< {\sqrt{4+M^2}+\sqrt{4M+M^2}\over 2}+\epsilon$$
which implies that for any $c'>{{\sqrt{4+M^2}+\sqrt{4M+M^2}}\over 2}$, we have 
$$\vert a-{p_k\over q_k}\vert > {1\over c'q_k^2}$$ for large $k$, and the
result.\par\vskip.3truecm \noindent
As exercises you may show that:\par\noindent 1)  If we write
$$ a-{p_k\over q_k} ={(-1)^k\delta_k\over
q_k^2},$$ as definition of the real number $\delta_k$, then $0\leq \delta_k <1$, and the
asymptotic lower bound $\underline{\rm lim}_k\delta_k$ is positive
if and only if the $u_k$ are bounded by some $M$ as
above.\par\noindent 2)
There is a variant of the proof given above, using  the equality (which is also a consequence of
formula  (4)) $$ a-{p_k\over q_k} ={(-1)^k\over
q_k(q_{k-1}+a_{k+1}q_k)}\ \ ;$$
the aim is now to find a lower bound for $a_{k+1}+{q_{k-1}\over
q_k}$ and show that it is attained when all $u_k=1$. \par\vskip.2truecm\noindent Remarks:  of
course, the essentially periodic continued fraction expansions of the roots of equations of degree
two with integral coefficients, which we saw above, satisfy the condition $u_k\leq M$ for some
$M$, and therefore they satisfy the conclusion of the Theorem.\Par  There is a generalization,
which is a deep theorem of number theory, called the Thue-Siegel-Roth Theorem, which implies
that if $a$ is an irrational number which is a root of a polynomial equation 
$$a_nX^n+a_{n-1}X^{n-1}+\cdots +a_0=0$$ with integer coefficients (in short, $a$ is an irrational
algebraic number) then for any $\theta>2$ there exists a positive number $\delta$ depending
on $a$ and $\theta$ such that for all rational numbers $p\over q$ we have $$\vert a-{p\over
q}\vert >{\delta\over q^\theta}.$$ This implies that for an algebraic number the $u_k$'s cannot
grow too fast and is the best result we know about the continued fraction expansions of
irrational non \break quadratic algebraic numbers such as
$2^{1/3}$.\vskip.3truecm\vskip.3truecm\noindent  \S 5 Golden ratio, etc..
\par\vskip.3truecm\noindent If we consider the result on approximation of bounded continued
fractions, we see that a number which should have the worst approximation by rationals is the
number corresponding to $M=1$, that is, the number $$\tau=[1,1,\ldots , 1, \ldots]$$ This
number is called the \it golden ratio \rm and it was well known to the Greeks; if you try to find
the ratio of the sides of a rectangle such that if you remove from this rectangle the largest
possible square contained in it the remaining rectangle has the same ratio of sides, you find that
this ratio is the golden section. By now this should be obvious to you by Anthyphairesis of the
sides of the rectangle. It should also be easy for you to compute  $$\tau={{1+\sqrt 5}\over 2}.$$
In any case this number indeed has the worst possible approximation by rational numbers: the
critical constant is $\sqrt 5$ as we see by taking $M=1$ in the formula proved above. One can
prove that for any positive number the inequality  $$\vert a -{p\over q}\vert \leq {1\over
\sqrt 5 q^2}$$ has infinitely many solutions; in fact given any three successive convergents of
$a$, at least one of them satisfies $$\vert a-{p_k\over q_k}\vert <{1\over \sqrt 5 q_k^2}$$  but
if $a$ is the golden ratio you cannot replace $\sqrt 5$ by any larger number and keep an
infinite number of solutions for this inequality (this result is due to Hurwitz) .  For the golden
ratio the sequence of $p_k$ is given by $p_{k+1}=p_{k-1}+p_k$, and the same holds for the
$q_k$, with the initial conditions $p_0=1, p_1=2, q_0=q_1=1$. Thus $p_k$ and $q_k$ are
consecutive \it Fibonacci numbers \rm, that is, elements of the sequence
$1,1,2,3,5,8,13,21,34,55,89,144,233,\ldots$ where each number is the sum of the two which
precede.\Par If you observe pine cones, or sunflowers, pineapples, and the leaves of many
plants, etc.. you will see that the stems are arranged along spirals, and if you count the spirals
turning in one direction and those turning in the other, you will most of the time find two
consecutive Fibonacci numbers. This phenomenon can be related to the property of bad rational
approximation of the golden ratio. So you can observe a mathematical phenomenon in the
growth of plants.\vskip.4truecm\Par Until recently, there was no way to add or multiply two
numbers given by their continued fraction expansion. Perhaps this led to abandon this perfect
representation of real numbers for imperfect ones, such that decimal expansion, which admit
very simple algorithms for sum, difference, product, etc, which can be easily taught. 20 years
ago or so the computer scientist Gosper found an algorithm for adding, multiplying, dividing,
etc.. continued fractions. I refer you to the excellent book [F] which describes this algorithm. I
was largely inspired by that book, which I highly recommend. Below I give other recommended
reading on continued fractions. The theory goes much further. In particular, there are more
general definitions of continued fractions (see [P]). 

\vskip.3truecm
\noindent\S 5 Examples\Par\vskip.3truecm
\noindent
A bar above a sequence of numbers means that it is repeated indefinitely.\Par
$$\sqrt 2=[1,\overline 2]$$
$$\sqrt 3=[1,\overline{1,2}]$$
$${\sqrt 3\over \sqrt 2}=[1,\overline{4,2}]$$
$${\sqrt 4\over \sqrt 3}=[1,\overline{6,2}]$$
$$\sqrt {(n^2-1)}=[n-1,\overline{1,2(n-1)}]$$
$$\sqrt{(n^2+1)}=[n,\overline{2n}]$$
$$\sqrt{(n^2+2)}=[n,\overline{n,2n}]$$
$${e-1\over 2}=[1,6,10,14,18,22,\ldots ,4k+2,\ldots ]$$ 
$$ e-1=[1,1,2,1,1,4,1,\ldots ,1,2k,1,\ldots],$$ where $e=2,7182818...$ is the basis of
logarithms, a transcendental number.  \vfill\eject
\centerline{Bibliography}\vskip.4truecm\noindent
[F] David Fowler, \it The Mathematics of Plato's Academy \rm , Oxford Science publications,
Clarendon Press, Oxford, 1987.\Par
[H-W] G. H. Hardy and R. M. Wright, \it An introduction to the theory of numbers \rm Oxford
University Press fourth Edition, 1960.\Par
[P] O. Perron, \it Die Lehre von den Kettenbr\"uchen \rm Teubner 1934 (?).\Par
 [S] Harold M. Stark, \it An introduction to number theory \rm ,
Paperback edition MIT Press, 1978.\Par
[W] Wall, \it Continued fractions \rm Chelsea reprint Company, New York.
\end