Farey sequenceFareySequence2002-06-13 04:33:262002-06-24 06:28:35Definitioncontinued fraction% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newcommand{\Prob}[2]{\mathbb{P}_{#1}\left\{#2\right\}}
\newcommand{\Expect}{\mathbb{E}}
\newcommand{\norm}[1]{\left\|#1\right\|}
% Some sets
\newcommand{\Nats}{\mathbb{N}}
\newcommand{\Ints}{\mathbb{Z}}
\newcommand{\Reals}{\mathbb{R}}
\newcommand{\Complex}{\mathbb{C}}
%%%%%% END OF SAVED PREAMBLE %%%%%%The $n$'th \emph{Farey sequence} is the ascending sequence of all rationals
$\{0 \le \frac{a}{b} \le 1 : b \le n\}$.
The first 5 Farey sequences are
\begin{center}
\begin{tabular}[htp]{|cl|}
\hline
1 & $ \frac{0}{1} < \frac{1}{1} $ \\
2 & $ \frac{0}{1} < \frac{1}{2} < \frac{1}{1} $ \\
3 & $ \frac{0}{1} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{1}{1} $ \\
4 & $ \frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1} $ \\
5 & $ \frac{0}{1} < \frac{1}{5} < \frac{1}{4} < \frac{1}{3} < \frac{2}{5} < \frac{1}{2} < \frac{3}{5} < \frac{2}{3} < \frac{3}{4} < \frac{4}{5} < \frac{1}{1} $ \\
\hline
\end{tabular}
\end{center}
Farey sequences are a singularly useful tool in understanding the convergents that appear in continued fractions. The convergents for any irrational $\alpha$ can be found: they are precisely the closest number to $\alpha$ on the sequences $F_n$.
It is also of value to look at the sequences $F_n$ as $n$ grows. If $\frac{a}{b}$ and $\frac{c}{d}$ are reduced representations of adjacent terms in some Farey sequence $F_n$ (where $b,d\le n$), then they are adjacent fractions; their difference is the least possible:
$$
\left|\frac{a}{b}-\frac{c}{d}\right| = \frac{1}{bd}.
$$
Furthermore, the \emph{first} fraction to appear between the two in a Farey sequence is $\frac{a+c}{b+d}$, in sequence $F_{b+d}$, and (as written here) this fraction is already reduced.
An alternate view of the ``dynamics'' of how Farey sequences develop is given by Stern-Brocot trees.