\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

\begin{center}

CONTINUED FRACTIONS

\end{center}

%page 1

Continued functions are related to the Euclidean algorithm. For
example $\frac{10}{7}$

\begin{eqnarray*}
10&=&1.7+3\\ 7&=&2.3+1\\ 3&=&3.1
\end{eqnarray*}

can be written as

$$\frac{10}{7}=1+\frac{3}{7}\hspace{1.5cm}
\frac{7}{3}=2+\frac{1}{3}$$

so

$$\frac{10}{7}=1+\frac{1}{2+\frac{1}{3}}$$

We can generalise steps like this, so that instead of taking a
rational number like $\frac{10}{7}$ we could take an irrational
number $\alpha$, and write

$$\alpha=a_0+\frac{1}{\alpha_1},\hspace{1.5cm}a_0=[\alpha],\
\alpha_1>1$$

$$\alpha_1=a_1+\frac{1}{\alpha_2}$$

etc.

For example

\begin{eqnarray*}
\sqrt{6}&=&2+\left(\sqrt{6}-2\right)\\
\frac{1}{\sqrt{6}-2}=\frac{\sqrt{6}+2}{2}=2+\frac{\sqrt{6}-2}{2}\\
\frac{2}{\sqrt{6}-2}=2.\frac{\sqrt{6}+2}{2}=\sqrt{6}+2=4+\left(\sqrt{6}-2\right)
\end{eqnarray*}

the process then repeats.

So

$$\sqrt{6}=2+\frac{1}{2+\frac{1}{4+\frac{1}{2+\frac{1}{4+\frac{1}{}}}}}$$

Periodic from the first step onwards.

%page 2

We clearly nee a better notation. Several have been in use over
the years.

\begin{eqnarray*}
\sqrt{6}&=&2.\&\frac{1}{2.}\&\frac{1}{4.}\&\frac{1}{2.}\&\frac{1}{4.}\&\ldots\\
&=&2+\frac{1}{2+}\frac{1}{4+}\frac{1}{2+}\ldots\\
&=&[2;2,4,2,4\ldots]\\ &=&[2;\overline{2,4}]
\end{eqnarray*}

To work with continued functions I need to establish some
fundamental formulae.

Consider the continued function

$$a_0+\frac{1}{a_1+}\frac{1}{a_2+}\ldots$$

where the $a_i$ for the present could be thought of as variables
(real, complex\ldots). If we consider the finite fraction

$$a_0+\frac{1}{a_1+}\frac{1}{a_2}\ldots\frac{1}{a_n}$$

this will be a rational function in the variables, which we shall
write as $\frac{p_n}{q_n}$. Evaluating the first few values

$a_0=\frac{p_0}{q_0}$ so $p_0=a_0,\ q_0=1$

$a_0+\frac{1}{a_1}=\frac{a_0a_1+1}{a_1}$ so $p_1=a_0a_1+1\
q_1=a_1$

$$a_0+\frac{1}{a_1+}\frac{1}{a_2}=
\frac{a_0a_1a_2+a_0+a_2}{a_1a_2+1}=\frac{p_2}{q_2}$$
%page 2

\begin{eqnarray*}
a_0+\frac{1}{a_1+}\frac{1}{a_2+}\frac{1}{a_3}&=&
=\frac{a_0a_1a_2a_3+a_0a_3+a_2a_3+a_0a_1+1}{a_1a_2a_3+a_3+a_1}\\
&=&\frac{a_3(a_0a_1a_2+a_0+a_2)+a_0a_1+1}{a_3(a_1a_2+1)+a_1}
=\frac{p_3}{q_3}
\end{eqnarray*}

so $p_3=a_3p_2+p_1\ q_3=a_3q_2+q_1$

This pattern generalises, and we have

\begin{eqnarray*}
p_{n+1}&=&a_{n+1}p_n+p_{n-1}\\ q_{n+1}&=&a_{n+1}q_n+q_{n-1}
\end{eqnarray*}

Proof By induction

$$\frac{p_n}{q_n}=a_0+\frac{1}{a_1+}\frac{1}{a_2+}
\ldots\frac{1}{a_n}=\frac{a_np_n-1+p_{n-2}}{a_nq_{n-1}+ q_{n-2}}$$

Now if we replace $a_n$ by $a_n+\frac{1}{a_{n+1}}$ we obtain
$\frac{p_{n+1}}{q_{n+1}}$

so

\begin{eqnarray*}
\frac{p_{n+1}}{q_{n+1}}&=&\frac{\left(a_n+\frac{1}{
a_{n+1}}\right)p_{n-1}+p_{n-2}}{\left(a_n+\frac{1}{
a_{n+1}}\right)q_{n-1}+q_{n-2}}\\
&=&\frac{a_np_{n-1}+p_{n-2}+\frac{p_{n-1}}{a_{n+1}}}{
a_nq_{n-1}+q_{n-1}+\frac{q_{n-1}}{a_{n+1}}}\\
&=&\frac{a_{n+1}p_n+p_{n-1}}{a_{n+1}q_n+q_{n-1}}
\end{eqnarray*}

%page 4

The formulae we developed initially gives

$n=2\hspace{1.5cm}p_2=a_2p_1+p_0,\ q_2=a_2q_1+q_0$

$n=1$ would read $p_1=a_1p_0+p_{-1},\ q_1=a_1q_0+q_{-1}$

Now this requires

\begin{eqnarray*}
a_0a_1+1&=&a_1a_0+p_{-1},\ p_{-1}=1\\ a_1&=&a_1.1+q_{-1},\
q_{-1}=0
\end{eqnarray*}

So if we conventionally set $p_{-1}=1\ q_{-1}=0$ then these
formulae are fine for $n=1,2,\ldots$.

If the $a_i$ are positive integers we can use these recurrence
relations to work out $\frac{p_n}{q_n}$ successively, without
having to \lq\lq add up from the back end'' each time.

eg. $3+\frac{1}{7+}\frac{1}{15+}\frac{1}{1+}\frac{1}{292+}
\frac{1}{1+}\ldots$

\begin{tabular}{cccccccc}
$n$&$-1$&0&1&2&3&4&5\\ $a_n$&&3&7&15&1&292&1\\
$p_n$&1&3&22&333&355&103933&104288\\
$q_n$&0&1&7&105&113&33102&33215
\end{tabular}

Now as a decimal $\pi=3.141592653897932\ldots$

\begin{tabular}{ccc}
$\frac{p_n}{q_n}$&$n=1$&3.\\ &$n=2$&3.142857\ldots\\
&$n=3$&3.14150943\ldots\\ &$n=4$&3.14159292\ldots\\
&$n=5$&3.14159265301\ldots
\end{tabular}

%page 4a

Since the $a_i$ are positive integers, we have

$$p_n\geq p_{n-1}+p_{n-2},\ q_n\geq q_{n-1}+q_{n-1}$$

with equality if and only if $a_n=1$

The minimum possible values for $q_n$ and $p_n$ therefore occur if
all the $a_n$'s are 1.

In that case

$p_{-1}=1,\ p_0=1$ and $p_n=p_{n-1}+p_{n-1}$

$q_0=1$ and $q_1=1$ and $q_n=q_{n-1}+q_{n-2}$

So $q_n$ is the $n$ th term in the Fibonacci sequence and $p_n$ is
the $(n+1)$th term in the Fibbonacci sequence.

i.e. for $1+\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\ldots$ we have

\begin{tabular}{cccccccc}
$n$&$-1$&0&1&2&3&4&5\\$a_n$&&1&1&1&1&1&1 \\$p_n$&1&1&2&3&5&8&13
\\$q_n$&0&1&1&2&3&5&8
\end{tabular}

$\frac{p_n}{q_n}\to$ golden ratio.

If $x=1+\frac{1}{1+}\frac{1}{1+}\ldots$ then (without worrying
about convergence) $x=1+\frac{1}{x}$

So $x^2-x-1=0,\ x=\frac{1\pm\sqrt{5}}{2}$ and $x>0$ so
$x=\frac{1+\sqrt{5}}{2}$.

%page 4b

More identities

\begin{enumerate}

\item
$$p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}$$

\item
$$p_nq_{n-1}-p_{n-2}q_n=(-1)^na_n$$

\end{enumerate}

\begin{enumerate}

\item
Again by induction

\begin{eqnarray*}
&&p_{n+1}q_n-p_nq_{n+1}\\&=&(a_np_n+p_{n-1})q_n-p_n(a_nq_n+q_{n-1})\\
&=&-(p_nq_{n-1}-p_{n-1}q_{n})
\end{eqnarray*}

$n=1:p_1q_0-p_0q_1=(a_0a_1+1).1-a_0.a_1=1$

\item

\begin{eqnarray*}
&&p_nq_{n-2}-p_{n-2}q_n\\
&=&(a_np_{n-1}+p_{n-2})q_{n-2}-p_{n-2}(a_nq_{n-1}+q_{n-2})\\
&=&a_n(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=a_n(-1)^n
\end{eqnarray*}

by 1.

\end{enumerate}

These formula can also be written in the form

\begin{enumerate}

\item
$$\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^{n-1}}{
q_nq_{n-1}}$$

\item
$$\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{(-1)^na_n}{
q_nq_{n-2}}$$

\end{enumerate}

Now suppose the $a_n$'s are positive real numbers. For $n$ even,
since the $q$'s are all positive

$$\frac{p_{n-2}}{q_{n-2}}<\frac{p_n}{q_n}<\frac{p_{n-1}}{q_{n-1}}$$

For $n$ odd

$$\frac{p_{n-1}}{q_{n-1}}<\frac{p_n}{q_n}<\frac{p_{n-2}}{q_{n-2}}$$

So this gives

$$\frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\frac{p_6}{q_6}
<\ldots<\frac{p_5}{q_5}<\frac{p_3}{q_3}<\frac{p_1}{q_1}$$


\end{document}