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

$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}$ は使わないことが分かった。

$$\begin{aligned} 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} \end{aligned}$$

となるので一つ目の式が成立。二つ目も同様。

$$n=\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}$ 未満である。矛盾。