2015/01/09

ゼッケンドルフの定理とその証明

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

ゼッケンドルフの定理(Zeckendorf):
任意の正の整数は「連続しない」フィボナッチ数の和で一意に表すことができる。


フィボナッチ数の美しい性質です。証明は誘導付きで最難関大の入試に出てもおかしくないレベルで,非常によい練習になります。

フィボナッチ数

  • フィボナッチ数列に登場する数をフィボナッチ数と言います。ここではフィボナッチ数を $F_1=1,\:F_2=2,\:F_{n}=F_{n-1}+F_{n-2}\:(n\geq 3)$ とします。(フィボナッチ数列には $1$ が最初二回登場しますが,区別しません)
  • フィボナッチ数の基本的な話についてはフィボナッチ数列の一般項と数学的帰納法を参照して下さい。

・フィボナッチ数を小さい順に並べると以下のようになります。
$1,\:2,\:3,\:5,\:8,\:13,\:21,\:34,\:55,\:89$

定理の主張について

・「連続しない」というのは(任意の $k$ に対して)$F_k$ と $F_{k+1}$ を同時に使わないという意味です。

$48=34+13+1$,$88=55+21+8+3+1$

このように連続しないフィボナッチ数の和で表すことをゼッケンドルフ表現と言うことにします。

・定理の主張は以下の二つに分けることができます:
任意の正の整数 $n$ に対して
1(存在性):ゼッケンドルフ表現が存在する。
2(唯一性):ゼッケンドルフ表現が存在すれば一意である。

1(存在性)の証明

まずは比較的簡単な1を証明します。丁寧に書いたのでけっこう長く見えますが見かけよりも簡単です。

方針:帰納法で証明します。実際に小さな数 $n$ のゼッケンドルフ表現を求めようとすると「 $n$ 以下の最大のフィボナッチ数」を使う必要がありそうだと分かります。

証明

$n=1$ のときはOK。 $n$ 未満の正の整数に対してゼッケンドルフ表現が存在すると仮定する。 $n$ のゼッケンドルフ表現を作ろうと試みる。

$n$ 以下の最大のフィボナッチ数を $F_k$ とする。つまり,$F_{k}\leq n <F_{k+1}$ である。
$n-F_{k}=0$ のときは $n=F_k$ がゼッケンドルフ表現。
そうでないとき「残った部分」 $n-F_{k}$ には帰納法の仮定よりゼッケンドルフ表現が存在する:
$n-F_{k}=\displaystyle\sum_{i\in A} F_i$(注)
よって,$n$ をフィボナッチ数の和で表せた:
$n=F_k+\displaystyle\sum_{i\in A} F_i$
あとはこれらのフィボナッチ数が連続していないこと,つまり,$(k-1)\not\in A$ を証明すればよい。

$n <F_{k+1}=F_{k}+F_{k-1}$ より,$n -F_k <F_{k-1}$ である。
よって,$n-F_k$ が $F_{k-1}$ より小さいのでそれを表現するのに $F_{k-1}$ は使わないことが分かった。

注:$A$ は添字の集合を表します。例えば $A=\{2,5,8\}$ のとき $\displaystyle\sum_{i\in A}F_i=F_2+F_5+F_8$ です。

2の証明に向けて

2の証明の本質的な部分ではフィボナッチ数は十分バラバラに存在することを表す以下の補題を用います。

補題:任意の正の整数 $n$ に対して,
$F_1+F_3+\cdots +F_{2n-1} <F_{2n}$
$F_2+F_4+\cdots +F_{2n} <F_{2n+1}$

証明は漸化式を使うだけです。非常に簡単です!

証明

$F_{2n}=F_{2n-1}+F_{2n-2}\\
=F_{2n-1}+F_{2n-3}+F_{2n-4}\\
=\cdots \\
=F_{2n-1}+F_{2n-3}+\cdots +F_{5}+F_{3}+F_{2}$
となるので一つ目の式が成立。二つ目も同様。

上記の補題より, $F_n$ 以上の整数をゼッケンドルフ表現するには $F_{n}$ 以上のフィボナッチ数を使う必要があることが分かります。

例えば,$48$ をゼッケンドルフ表現するのに $34$ を使わないと,どう頑張っても(残りを取れるだけ取っても)$34$ より小さくなってしまうので,$34$ を使うことが分かります。

ゼッケンドルフの定理の証明〜完結編

方針:補題を使って2(唯一性)を証明します。「 $n$ のゼッケンドルフ表現が二通りあると仮定すると補題に矛盾する」ことを証明します。

証明

$n=\displaystyle\sum_{i\in A}F_i=\sum_{j\in B}F_j$($A\neq B$)
と異なる二通りのゼッケンドルフ表現があると仮定する。双方に含まれるフィボナッチ数を両辺から引くことで以下の形の等式を得る:
$\displaystyle\sum_{i\in A’}F_i=\sum_{j\in B’}F_j$(ただし $A’$と $B’$は共通元を持たない空でない集合)
この両辺に登場するフィボナッチ数の中で最大のものが左辺にあるとしても一般性を失わない,それを $F_k$ とする。

すると,左辺は $F_k$ 以上だが,右辺は全て${F_k}$ より小さいフィボナッチ数の連続しない和で表されているので,補題により $F_{k}$ 未満である。矛盾。

ちゃんと書くと長くなるし,簡潔にするために省略すると分かりにくくなってしまいます,バランスが難しい!
分野: 数列  レベル: マニアック