\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{framed}

\pagestyle{plain}
\topmargin -.9in
\oddsidemargin -0.2in
\evensidemargin -0.2in
\textheight 9.5in
\textwidth 7in



\newtheorem{theorem}{Theorem}[section]
\newtheorem{define}[theorem]{Definition}
\newtheorem{ex}[theorem]{Example}

\newcommand{\dsty}{\displaystyle}
\newcommand{\nin}{\noindent}
\newcommand{\ans}{ {\bf Answer: }}
\newcommand{\sols}{\nin {\bf Solution: }} 
\newcommand{\solsFin}{ \hfill $\Box$}
\newcommand{\pf}{\nin {\bf Proof: }}


\newcommand{\ls}{\vspace{.15in}}
\newcommand{\vs}{\vspace{.25in}}
\newcommand{\ms}{\vspace{.5in}}
\newcommand{\bs}{\vspace{1in}}

\begin{document}

\centerline{{\Large {\bf {\em From Music to Mathematics: Exploring the Connections}}}}

\ls

\centerline{{\large {\bf Gareth E. Roberts}}}

\vs

\centerline{\Large {\bf Continued Fractions}}

\ls

\centerline{\large {\bf Handout (with Exercises) for Section 4.5.2}}


%%%%%%%%%%%%%%%%%%%%
\section{Playing around with $\pi$}
%%%%%%%%%%%%%%%%%%%%

The famous mathematical constant $\pi$ is irrational, with a nonrepeating, nonterminating
decimal expansion.  To 40 decimal places, $\pi$ is
$$
\pi \; =\;  3.1415926535897932384626433832795028841972 \dots \, .
$$
Since $\pi$ is irrational, it {\em cannot} be written as the ratio of two integers.  However, we could try to {\em approximate} 
$\pi$  using rational numbers.   How do we find good approximations to irrational
numbers, particularly with small numerators and denominators?   


Begin by writing $\pi$ as
$$
\pi \; = \;  3 + 0.1415926535897 \ldots \, .
$$
One approximation for $\pi$ is thus three (this is actually inferred in the Bible), but that is not very impressive.  
We could continue by approximating
$0.14\ldots$ as $14/100 = 7/50$ in order to obtain the first two decimal places of $\pi$.  However, there is a more clever approach.
Instead of approximating $0.14 \ldots$ as $7/50$, consider inverting it twice, writing 
$$
0.1415926535897 \ldots \; = \;  \frac{1}{ \displaystyle{ \frac{1}{0.1415926535897 \ldots }}} \; = \;  \frac{1}{7.062513305931 \ldots} \, .
$$
Ignoring the decimals after $7.06 \ldots \,$, this suggests the approximation $3 + 1/7 = 22/7$, a well-known estimate
for~$\pi$.  As with the fraction $157/50 = 3 + 7/50$, this gives $\pi$ to two decimal
places, but notice that $22/7$ has a denominator about 7 times {\em smaller} than $157/50$.  
This is more in line with our goal of finding low-numbered rational approximations.  


We can continue this process.   Inverting the new ``remainder" decimal $0.062513305931 \ldots$ twice gives
$$
0.062513305931 \dots \; = \;  \frac{1}{ \displaystyle{ \frac{1}{0.062513305931 \dots }}} \; = \;  \frac{1}{15.99659441 \dots} \, .
$$
This last number in the denominator is very close to 16.  If we approximate at this point, we find 
$$
\pi \; \approx \;  3 + \frac{1}{ \displaystyle{  7 + \frac{1}{16}}}  \; = \;  3 + \frac{16}{113} \; = \;  \frac{355}{113}  \; = \;  3.14159292 \dots \, .
$$
Remarkably, the approximation $355/113$ agrees with $\pi$ to six decimal places!  If we tried to obtain this approximation by truncating
$\pi$ to six decimal places, we would have a reduced fraction with denominator $125,\!000$.  That's roughly $1100$ times larger than~113.


If we continue this process of inverting the remainder decimal, after two more iterations
we obtain the following multilayered fraction:
\begin{equation}
\pi \; \approx \;  3 + \frac{1}{ \displaystyle{  7 + \frac{1}{15 + \displaystyle{  \frac{1}{ 1 + \frac{1}{293}}} } } } 
\; = \; \frac{104,\! 348}{33,\! 215}  \; = \;  3.14159265392142 \ldots ,
\label{pi}
\end{equation}
which approximates $\pi$ accurately to nine decimal places.

These crazy, multistory fractions are called {\bf continued fractions} and are
an important topic in the subject of number theory, although they find their way into all sorts of applications in other fields.




%%%%%%%%%%%%%%%%%
\section{Continued Fractions}
%%%%%%%%%%%%%%%%%


\begin{define}  
Given a real number $\alpha$, the \underline{continued fraction expansion} of $\alpha$ is
$$
\alpha \; = \;  a_0 + \frac{1}{a_1 + \dsty{ \frac{1}{ \dsty{ a_2 +  \frac{1}{\dsty{ a_3 + \frac{1}{\ddots} }} }} }} \; = \;  [a_0; a_1, a_2, a_3, \ldots \,]
$$
where each $a_i$ (except possibly $a_0$) is a positive integer.
\end{define}

The notation $\alpha = [a_0; a_1, a_2, a_3, \dots \,]$ is much easier to use than writing the multistory fraction.  The first integer $a_0$ is just the
number to the left of the decimal point (e.g., $a_0 = 3$ for $\alpha = \pi$).  Notice the semicolon after the $a_0$.  
The succeeding list of integers are the denominators
of each fraction since we know that each numerator is always~1.  For example, from Equation~(\ref{pi}), 
we have that
$$
\pi \; = \;  [3; 7,15,1,292, \dots \, ].
$$
The reason for 292, as opposed to 293, is that the final approximation in the denominator was
$292.63459 \dots \,$.    Although we rounded this to 293 to obtain the approximation $104,\! 348/33,\!215$ for $\pi$, the actual integer
{\em before} rounding is 292.  


Observe that if the number we are approximating is irrational, then this process of inverting the remainder decimal twice will continue forever;
otherwise, the approximation would be exact and we would obtain a rational number.  


\begin{theorem}
The continued fraction expansion of a real number is finite if and only if that number is rational.  
In other words, the continued fraction expansion of an irrational number is infinite.
\end{theorem}



 
\begin{ex}
Compute the continued fraction expansion for the rational number $\alpha = 37/13$.
\end{ex}


\sols  We start by dividing 37 by 13 to obtain 2 with a remainder of 11.  Thus,
$$
\frac{37}{13} \; = \;  2 + \frac{11}{13} \; = \;  2 + \frac{1}{ 13/11}  \, .
$$
Notice that the final fraction in the denominator is bigger than~1.  This will always be the case
since we are inverting a number less than~1 (the remainder).  Continuing, we divide 13 by 11 to obtain 1 with a 
remainder of 2.  Thus, we have
$$
\frac{37}{13} \; = \;  2 + \frac{11}{13} \; = \;  2 + \frac{1}{ 13/11}  \; = \;  2 + \frac{1}{ \dsty{ 1 + \dsty{ \frac{2}{11} }} }  \; = \;  2 + \frac{1}{ \dsty{ 1 + \dsty{  \frac{1}{11/2} }  } } \, .
$$
Next, we divide 11 by 2 to obtain 5 with a remainder of 1.  This gives
$$
\frac{37}{13} \; = \;  2 + \frac{11}{13} \; = \;  2 + \frac{1}{ 13/11}  \; = \;  2 + \frac{1}{ \dsty{ 1 + \dsty{ \frac{2}{11} }} }  \; = \;  2 + \frac{1}{ \dsty{ 1 + \dsty{  \frac{1}{11/2} }  }} 
\; = \;  2 + \frac{1}{ \dsty{ 1 + \dsty{  \frac{1}{5 + \dsty{ \frac{1}{2} } } }  }} \, .
$$
The process terminates at this point because we are left with the integer $2$ in the denominator rather than
a fraction.  There is nothing left to divide when the remainder is~1.  The last fraction of $11/2$ is simply $5 + 1/2$, 
which is already in the required form because of the~1 in the numerator.  
Thus, we have shown that the continued fraction expansion for the rational number $37/13$ is
$$
\frac{37}{13} \; = \;  [ 2; 1, 5, 2] \, .      
$$
\solsFin

\ls


Note that before we reached the final step in the example, each of the previous steps did not have a~1 for a remainder.
This is a useful fact.

\begin{framed}
\nin  {\bf Key Fact:}  When writing the finite continued fraction expansion of a rational number, the process terminates precisely
when a remainder of~1 occurs.
\end{framed}




%%%%%%%%%%%%%%%%%%
\subsection{Periodic Expansions}
%%%%%%%%%%%%%%%%%%


Sometimes, instead of terminating, the continued fraction expansion will repeat a certain pattern forever.  For example,
$$
\sqrt{8} \; = \;  [2; 1, 4, 1, 4, 1, 4, 1, 4, \dots] 
$$
has a repeating pattern of period 2 since it ends with the sequence $1, 4, 1, 4, \dots$.  We will refer to this kind of sequence
as a {\em periodic sequence of period~2}.  When a continued fraction expansion has a periodic sequence,
we write 
$$
\sqrt{8} \; = \;  [2; \overline{1, 4} \,] .
$$
Another example is
$$
\sqrt{7}  \; = \;  [2; 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, \dots] \; = \;  [2; \overline{1, 1, 1, 4} \,].
$$



\begin{ex}
Find the irrational number that corresponds to the continued fraction expansion 
$$
\alpha \; = \;  [1; 2, 2, 2, \ldots]  \; = \;  [1; \overline{2} \,] .
$$
\end{ex}

\sols  One way to approach the problem is to approximate $\alpha$ by terminating the expansion
at different locations.  These approximations are called {\bf convergents}.  In general,
the 
$$
n^{\mbox{{\footnotesize th}}} \mbox{ convergent to } \alpha \; = \;   \frac{p_n}{q_n} \; = \;  [a_0;  a_1, a_2, a_3, \ldots , a_n] \, .
$$
The larger $n$ is (the further out in the expansion we go), the better the approximation
to $\alpha$ becomes.

For $\alpha \; = \;  [1; 2, 2, 2, \ldots] $, the first five convergents are given below:
\begin{eqnarray*}
\frac{p_0}{q_0} &=&  1  \qquad \mbox{(this is just $a_0$),} \\
\frac{p_1}{q_1} &=&  1 + \frac{1}{2} \; = \;  \frac{3}{2} \; = \; 1.5, \\[0.07in]
\frac{p_2}{q_2} &=&  1 + \frac{1}{2 + \dsty{ \frac{1}{2}} } \; = \;  \frac{7}{5} \; = \; 1.4, \\[0.1in]
\frac{p_3}{q_3} &=&  1 + \frac{1}{2 + \dsty{ \frac{1}{2 + \dsty{ \frac{1}{2} }  }}} \; = \;  \frac{17}{12} \; = \; 1.41\bar{6},  \\[0.1in]
\frac{p_4}{q_4} &=&  1 + \frac{1}{2 + \dsty{ \frac{1}{2 + \dsty{ \frac{1}{2  + \dsty{ \frac{1}{2}}  } }  }}} \; = \;  \frac{41}{29} \; \approx \; 1.4138.
\end{eqnarray*}

Do you recognize the last approximation of $1.414$?  This suggests that $\alpha = \sqrt{2}$, which turns out to be correct.   Notice
that not only are the convergents getting closer to $\sqrt{2}$, but they also oscillate about it (below, above, below, above,
etc.).  This will always be the case, no matter the value of~$\alpha$.


There is a clever trick to see that $\alpha = \sqrt{2}$.  Since the continued fraction pattern is periodic, the expression for
$\alpha$ actually {\em reappears} inside its own expansion.  We have
$$
\alpha \; = \;   1 + \frac{1}{2 + \dsty{ \frac{1}{ \dsty{ 2 +  \frac{1}{\dsty{ 2 + \frac{1}{\ddots} }} }} }} \; = \;  
1 + \frac{1}{1 + 1 + \dsty{ \frac{1}{ \dsty{ 2 +  \frac{1}{\dsty{ 2 + \frac{1}{\ddots} }} }} }} \; = \;  
1 + \frac{1}{1 + \alpha}.
$$
This last expression may seem strange, but if we know that the infinite continued fraction converges to a real number (this requires
a proof), then the continued fraction expansion in the denominator of the penultimate expression is equal to the original continued
fraction expansion for $\alpha$.  The main concept being invoked here is known as
{\bf self-similarity}, a key ingredient in the fascinating field of {\bf chaos theory}.  



Thus, we have that 
\begin{eqnarray*}
\alpha \; = \;  1 + \frac{1}{1 + \alpha} \quad  &\Longrightarrow&  \quad  \alpha - 1 \; = \;   \frac{1}{1 + \alpha} \\
&\Longrightarrow&  \alpha^2 - 1 \; = \;  1  \qquad \mbox{(by cross-multiplying)} \\
&\Longrightarrow&  \alpha^2 \; = \; 2  \\  
&\Longrightarrow&  \alpha = \sqrt{2} \, .
\end{eqnarray*}
Note that we choose the positive square root because it is clear from the continued fraction expansion that $\alpha > 0$.
\solsFin



\ls

This example is illustrative of an important fact about continued fractions.


\begin{theorem}
The continued fraction expansion of an irrational number is \underline{periodic} if and only if
$\alpha$ is of the form $\alpha = r + s \sqrt{n}$, where $r, s$ are rational numbers and $n$ is a positive
integer not equal to a perfect square.  In this case, periodic means that the continued fraction expansion ends with
a periodic, repeating sequence of positive integers.
\end{theorem}





%%%%%%%%%%%%%
\subsection{Convergents and Their Accuracy}
%%%%%%%%%%%%%

Instead of having to compute the value of the convergents from scratch each time, there are some convenient {\bf recursive
formulas} available that give the next convergent in terms of the previous entries.  The formulas are:
\begin{eqnarray*}
p_0 &=&  a_0 \\
p_1 &=& a_1 a_0 + 1 \\
p_n &=& a_n \, p_{n-1} + p_{n-2} \quad \mbox{if $n \geq 2$,} 
\end{eqnarray*}
and
\begin{eqnarray*}
q_0 &=&  1 \\
q_1 &=& a_1  \\
q_n &=& a_n \, q_{n-1} + q_{n-2}  \quad \mbox{if $n \geq 2$}.  
\end{eqnarray*}

For example, if $\alpha = \sqrt{2} = [1; 2, 2, 2, \ldots ] \, ,$ then $p_0 = 1, p_1 = 2 \cdot 1 + 1 = 3$, and
\begin{eqnarray*}
p_2  &= &  a_2 \, p_1 + p_0 \; = \;  2 \cdot 3 + 1 \; = \; 7   \\
p_3  & = & a_3 \, p_2 + p_1 \; = \;  2 \cdot 7 + 3 \; = \;  17 \\
p_4  & = & a_4 \, p_3 + p_2 \; = \;  2 \cdot 17 + 7 \; = \;  41. 
\end{eqnarray*}
A similar set of calculations can be used to find the denominators
$q_n$.  Try checking them with $\sqrt{2} \,$ and comparing with the convergents we obtained in Example~2.4.




Before closing our discussion of continued fractions, we make one final point concerning the accuracy of
the convergents.   It turns out
that the rational approximations to an irrational number~$\alpha$ obtained by using a continued fraction expansion are the {\em best} possible
for a given denominator.   Moreover, each convergent is closer to $\alpha$ than the preceding one, and the convergents
oscillate about $\alpha$, with the even convergents ($n=0, 2, 4, \dots$) lying below $\alpha$ and the odd
convergents  ($n=1, 3, 5, \dots$) lying above.  Specifically, we have the following theorem:
\begin{theorem}
If $\dsty{  \{  p_n/q_n \}}$ is the sequence of convergents to an irrational number $\alpha$, then
$$
\frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} \; = \; \frac{ (-1)^{n+1} }{q_{n-1} \, q_n} .
$$
Moreover, any particular convergent $p_n/q_n$ is closer to $\alpha$ than 
any other fraction whose denominator is less than $q_n$.
\end{theorem}

For example, when approximating $\alpha = \sqrt{2}$, choosing the fourth convergent $41/29$ gives the best possible rational approximation
to $\sqrt{2}$ with denominator less than $29$.  This is precisely why the convergents of a continued fraction expansion are considered to be
the {\em best} rational approximations.




%%%%%%%%%%%%%%
\section{Exercises}
%%%%%%%%%%%%%%

\begin{enumerate}

\item  Compute the continued fraction expansion for the rational numbers $\alpha = 67/9$ and $\beta = 57/16$.  Be sure to show your work.
Give each answer in the form $[a_0; a_1, a_2, \ldots] \, .$

\item  Compute the continued fraction expansion for the irrational numbers $\alpha = \sqrt{10}$ and $\beta = \sqrt{14}$.  Be sure to show your work.
Give each answer in the form $[a_0; a_1, a_2, \ldots] \, .$  {\em Hint:}  Each answer is periodic.


\item  Consider the irrational number $\alpha$ with periodic continued fraction expansion $[1; 1, 1, 1, \ldots ] \, .$

\begin{description}
\item[{\bf a)}]  Compute the first seven convergents of $\alpha$, that is, compute $p_n/q_n$ for 
$n= 0, 1, \ldots, 6$.  What do you notice about the numbers in the numerator and denominator?

\item[{\bf b)}]  Find the exact value of $\alpha$ using the method of self-similarity demonstrated in Example~2.4.
What special name is given to the number $\alpha$?

\end{description}


\item  The number $\log_2(3/2)$ is important when attempting to find good approximations
to a true or just perfect fifth.  

\begin{description}

\item[{\bf a)}]  Compute the first seven convergents of $\log_2(3/2)$, that is, compute $p_n/q_n$ for 
$n= 0, 1, \ldots, 6$.  Be sure to show your work.

\item[{\bf b)}]   If you have done part {\bf a)} correctly, you should recognize the fraction obtained
for $n=4$.  Explain how this particular fraction relates to equal temperament. 

\item[{\bf c)}]  Why would it ``work'' to divide the octave into 53 equal parts, creating a scale with 53 notes
equally spaced by the step $H = 2^{1/53}$?  In this case, what is the value of the frequency multiplier 
to raise the pitch by a perfect fifth?  (This is the number that you would multiply the frequency of the tonic by in order
to raise the pitch a P5.)  What is the value of this multiplier in cents (to three decimal places) 
and how close is it (in cents, three decimal places) to a just perfect fifth?

\item[{\bf d)}]  Consider the 53-tone equally tempered scale, where the distance between consecutive scale degrees
is $2^{1/53}$.   How many steps are in a major third?  Convert the multiplier to raise the pitch a major third into cents (three decimal places).
How close is it (in cents, three decimal places) to a just major third?  Would you need to raise or lower the 
pitch in your new scale to obtain a just major third?  

\end{description}

\end{enumerate}


\begin{thebibliography}{99}


\bibitem{frech} S. Frechette, Course Notes, Math 399, College of the Holy Cross,
Spring 2007.

\bibitem{silver} J. H. Silverman,  {\em A Friendly Introduction to Number Theory}, Third Ed.,
Pearson Prentice Hall, Upper Saddle River, New Jersey, 2006,
pp. 324--355.

\bibitem{mathworld} E. Weisstein, {\em Continued Fraction}, 
MathWorld: A Wolfram Web Resource,
{\tt http://mathworld.wolfram.com/ContinuedFraction.html}

\end{thebibliography}


\end{document}