\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}