# Farey sequence

A Farey sequence of order $n$ is the sequence of all completely reduced fractions between 0 and 1 where, when in lowest terms, each fraction has a denominator less than or equal to $n$. Each fraction starts with 0, denoted by the fraction 0/1, and ends in 1, denoted by the fraction 1/1.

## Examples

Farey sequences of orders 1-4 are: $F_1=\{0/1, 1/1\}$ $F_2=\{0/1, 1/2, 1/1\}$ $F_3=\{0/1, 1/3, 1/2, 2/3, 1/1\}$ $F_4=\{0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1\}$

Where $F_n$ denotes a Farey sequence of order $n$.

## Proof Sketch

Which is bigger, $\frac{a}{b}$ or $\frac{a+1}{b+1}$?

Which is bigger, $\frac{a}{b}$ or $\frac{a+1}{b+2}$?

Do you see a pattern?

Assume $a$ and $b$ are positive.

## Properties

### Sequence length

A Farey sequence of any order contains all terms in a Farey sequence of lower order. More specifically, $F_n$ contains all the terms in $F_{n-1}$. Also, $F_n$ contains an extra term for every number less than $n$ relatively prime to $n$. Thus, we can write $\#(F_n)=\#(F_{n-1})+\phi{(n)}$