ファレイ数列の４つの性質とその証明

背理法で証明する。$F_n$ の隣り合う二項 $\dfrac{q_i}{p_i},\dfrac{q_{i+1}}{p_{i+1}}$ で $p_i+p_{i+1}\leq n$ なるものが存在すると仮定する。

このとき $\dfrac{q_i+q_{i+1}}{p_i+p_{i+1}}$ を約分した分数を考えると，

分母は $n$ 以下であり $\dfrac{q_i}{p_i} <\dfrac{q_i+q_{i+1}}{p_i+p_{i+1}} <\dfrac{q_{i+1}}{p_{i+1}}$ であるので（$F_n$ で $\dfrac{q_i}{p_i},\dfrac{q_{i+1}}{p_{i+1}}$ が隣り合うということに）矛盾。

$F_{n+1}$ で新たに登場する分数の分母は $n+1$ である。

$k=1,\cdots,n-1$ に対して $\dfrac{k}{n+1} <\dfrac{k}{n} <\dfrac{k+1}{n+1}$ であるので，必ず $\dfrac{k}{n}$ （を約分したもの）というタイプの分数が間に割り込む。

帰納法で証明する。$F_2$ については簡単に確認できる。

$F_n$ のときOKと仮定して，$F_{n+1}$ でもOKであることを証明する。

$F_{n+1}$ で新たに加わる分数 $\dfrac{q}{p}$ について，$F_{n+1}$ における両隣を $\dfrac{q_i}{p_i},\dfrac{q_{i+1}}{p_{i+1}}$ とする（性質2よりこれらは $F_n$ の隣り合う項でもある）。

$\dfrac{q_i}{p_i} <\dfrac{q}{p} <\dfrac{q_{i+1}}{p_{i+1}}$ の分母を払うと，

$p_iq-q_ip=N$，$q_{i+1}p-p_{i+1}q=M$

（ただし $N,M$ は正の整数）

（帰納法の仮定より $p_iq_{i+1}-q_ip_{i+1}=1$ であることに注意して）上の二式を $p,q$ について解くと

$p=Mp_i+Np_{i+1}$ ，$q=Mq_i+Nq_{i+1}$

ここで，性質1より $p_i+p_{i+1} \geq n+1$ であることと $p\leq n+1$ であることから $N=M=1$ 。つまり $F_{n+1}$ でも性質3が成り立つことが分かった！