2015/07/02

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

分野: 数列  レベル: マニアック

$0$ 以上 $1$ 以下であり,分母が $n$ 以下であるような既約分数を小さい順に並べた数列を($n$ に対応する)ファレイ数列という。


昔,たけしのコマ大数学科という番組でも取り上げられたファレイ(ファレー,Farey)数列について,その性質と証明を解説します。

ファレイ数列の具体例

$n=2$:$\dfrac{0}{1},\dfrac{1}{2},\dfrac{1}{1}$

$n=3$:$\dfrac{0}{1},\dfrac{1}{3},\dfrac{1}{2},\dfrac{2}{3},\dfrac{1}{1}$

$n=4$:$\dfrac{0}{1},\dfrac{1}{4},\dfrac{1}{3},\dfrac{1}{2},\dfrac{2}{3},\dfrac{3}{4},\dfrac{1}{1}$

$n=5$:$\dfrac{0}{1},\dfrac{1}{5},\dfrac{1}{4},\dfrac{1}{3},\dfrac{2}{5},\dfrac{1}{2},\dfrac{3}{5},\dfrac{2}{3},\dfrac{3}{4},\dfrac{4}{5},\dfrac{1}{1}$

ファレイ数列には美しい性質がいくつか隠れています。以下紹介する性質を実際に $n=2,3,4,5$ の場合で確認するとけっこう感動します!

性質1(普通)

以下,$n$ に対応するファレイ数列を $F_n$ と表記します。

性質1:$F_n$ の隣り合う二項の分母の和は $n+1$ 以上。

証明

背理法で証明する。 $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}}$ が隣り合うということに)矛盾。

注:途中で登場した不等式は加比の理と傾きによる証明を知っているとイメージしやすいです。

性質2(しょうもない)

$F_{n+1}$ で初めて登場する項たちは,$F_{n+1}$ では隣り合わない。

例えば $n=4$ の場合,$F_5$ に新たに登場するのは $\dfrac{1}{5},\dfrac{2}{5},\dfrac{3}{5},\dfrac{4}{5}$ ですが,これらは $F_5$ では隣り合いません。

証明

$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}$(を約分したもの)というタイプの分数が間に割り込む。

性質3(本命)

性質3:ファレイ数列の隣り合う項 $\dfrac{q_i}{p_i},\dfrac{q_{i+1}}{p_{i+1}}$ について,$p_iq_{i+1}-q_ip_{i+1}=1$ が成立する。

僕はファレイ数列の性質の中でこれが一番美しいと思います。ぜひ $n=3$ とかの場合に確認してみてください。

証明

帰納法で証明する。 $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が成り立つことが分かった!

ついでに,$\dfrac{q}{p}=\dfrac{q_i+q_{i+1}}{p_i+p_{i+1}}$ が分かり,以下の性質4が導かれます。

性質4(ファレイ数列を構成するのに使える)

$F_n$ の隣り合う二項で分母の和が $n+1$ のもの $\dfrac{q_i}{p_i},\dfrac{q_{i+1}}{p_{i+1}}$ について,この間に $\dfrac{q_i+q_{i+1}}{p_i+p_{i+1}}$ を入れる(該当箇所全部にこの操作をする)と $F_{n+1}$ ができる。

例えば,$F_4$ を見ると $\dfrac{0}{1},\dfrac{1}{4},\dfrac{1}{3},\dfrac{1}{2},\dfrac{2}{3},\dfrac{3}{4},\dfrac{1}{1}$ であり,隣り合う二項で分母の和が $5$ であるものは四カ所あります。ここにそれぞれ「両隣の分母,分子をそれぞれ足した分数」を入れると $F_5$ が作れます!

「高校数学の美しい物語」らしい記事になりました!
分野: 数列  レベル: マニアック