ゼッケンドルフの定理

数学におけるゼッケンドルフの定理とは、任意の正の整数は、1つ以上の、番号が連続しないフィボナッチ数の和として一意に表せるという定理である。名前はベルギーの数学者、Edouard Zeckendorf に由来する。より厳密には、

定理 ― N を任意の正の整数とすれば、c_i+1 > c_i + 1 を満たす正の整数 c_i ≥ 2 が存在して、

${\displaystyle N=\sum _{i=0}^{k}F_{c_{i}}}$

（ただし F_n は n 番目のフィボナッチ数）

正の整数の最初 160 個（X軸上) をゼッケンドルフの表現で表したもの。長方形それぞれの色がフィボナッチ数列での番号、高さが値に対応している。

というものである。このような和は N のゼッケンドルフの表現と呼ばれる。

例えば、100 のゼッケンドルフの表現は

100 = 89 + 8 + 3

となる。100 をフィボナッチ数の和として表す方法は他にも

100 = 89 + 8 + 2 + 1

100 = 55 + 34 + 8 + 3

のように存在するが、これらはそれぞれ 1 と 2, 34 と 55 が連続するフィボナッチ数であるため、ゼッケンドルフ表現ではない。

与えられた任意の正の整数のゼッケンドルフ表現は、その数を超えない最大のフィボナッチ数を取っていく貪欲法によって得られる。

証明

ゼッケンドルフの定理は2つの部分に分けられる。

1. 存在：任意の正の整数 n に対してゼッケンドルフの表現が存在する。
2. 一意性：どの正の整数 n も、相異なる2つのゼッケンドルフの表現を持たない。

存在

最初の部分（存在）は数学的帰納法によって示すことができる。n = 1, 2, 3 については（これらはフィボナッチ数だから）明らかに真であり、n = 4 に対しては 4 = 3 + 1 が当てはまる。さて、すべての n ≤ k に対してゼッケンドルフの表現が存在すると仮定する。k + 1 がフィボナッチ数ならばそれがゼッケンドルフの表現となり、そうでない場合には F_j < k + 1 < F_j+1 となる j が存在することになる。後者の場合に、a = k + 1 − F_j を考えると、a ≤ k であるから、 a は帰納法の仮定により、ゼッケンドルフの表現を持つ。さらに、F_j + a < F_j+1 でありまた F_j+1 = F_j + F_j−1（フィボナッチ数の定義から）だから、a < F_j−1 となって a のゼッケンドルフ表現は F_j−1 を含まないことがいえる。よって、k + 1 は F_j と a のゼッケンドルフの表現の和として表すことができる。

一意性

後半（一意性）を示すには次の補題が必要となる。

補題 ― 最大の要素が F_j である、連続せず互いに異なったフィボナッチ数の任意の空でない集合について、その和は F_j+1 より（実際に）小さい。

この補題は j についての帰納法で証明することができる。

さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合 S と T を考える。ここで集合 S′ と T′ を考える。これはそれぞれ S と T から共通する要素を取り除いたものである（つまり、S′ = S \ T, T′ = T \ S である）。S と T の和は等しく、それぞれの集合から S ${\displaystyle \cap }$ T を取り除いたものであることから、S′ の和と T′ の和もまた等しい。

ここから背理法によって S′ と T′ の一方は空であることを示す。S′ と T′ がいずれも空でないと仮定し、S′ の最大の要素を F_s,T′ の最大の要素を F_t とする。S′ と T′ には共通する要素はないから、F_s ≠ F_t である。ここで F_s < F_t としても一般性を失わない。このとき補題から、S′ の総和は F_s+1 より小さく、従って F_t よりも小さいが、T′ の和は明らかに F_t 以上である。これは S′ と T′ の総和が等しいことと矛盾しており、従って S′ か T′ の少なくとも一方は空であるといえる。

このとき S′ が空であるとしても一般性を失わない。すると S′ の和は 0 であり、このため T′ の和も同様に 0 であるはずである。T′ の要素は正の整数のみであるから、これを満たすためには T′ は空集合でなければならない。従って S′ = T′ =${\displaystyle \emptyset }$, すなわち S = T であって、ゼッケンドルフの表現の一意性が示された。

フィボナッチ積

自然数 a, b に対して次の演算 ${\displaystyle a\circ b}$ を定義することができる。ゼッケンドルフの表現 ${\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)}$ と ${\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)}$ に対して、フィボナッチ積 ${\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.}$

例えば、2 のゼッケンドルフの表現は F₃, 4 に対するそれは F₄ + F₂ (F₁ は用いない) であるから、${\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18}$ となる。

和の順序を入れ替えることでこれが可換であることは示すことができるが、ドナルド・クヌースはさらに、この演算が結合的でもあるということを証明した。

負数番のフィボナッチ数を用いた表現

フィボナッチ数列は、漸化式を書き換えて

${\displaystyle F_{n-2}=F_{n}-F_{n-1},}$

とし、これをすべての整数について適用することで負数番 n にも拡張することができ、次の性質を満たす。

${\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}$

任意の整数は、連続したフィボナッチ数を使わない形で負数番のフィボナッチ数の和として一意に表すことができる^[1]。例えば

• −11 = F₋₄ + F₋₆ = (−3) + (−8)
• 12 = F₋₂ + F₋₇ = (−1) + 13
• 24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ = 1 + (−3) + (−8) + 34
• −43 = F₋₂ + F₋₇ + F₋₁₀ = (−1) + 13 + (−55)
• 0 は空集合に対する和として表される。

たとえば 0 = F₋₁ + F₋₂ であるから、この表現の一意性は連続するフィボナッチ数を用いないという条件に依存している。

この表現によって、ゼッケンドルフの表現と同様に整数を符号化することが可能である (en:NegaFibonacci_coding)。整数 x を表す文字列においては、n 番目の桁は F_n が x を表す和に現れるなら 1, そうでないなら 0 となる。例えば 24 = F₋₁ + F₋₄ + F₋₆ + F₋₉ であるから 24 は 9, 6, 4, 1 桁目に 1 を置いて 100101001 によって表現できる。整数 x が奇数桁でこのように表されることと、x > 0 であることは同値である。

関連項目

• ワイソフのゲーム（2山の片方からまたは、両方から同数ずつ取る石取りゲーム）の後手必勝形は、次のようにゼッケンドルフ表示できる^[2]：

  x = F_n1 + F_n2 + … + F_nk, y = F_n1+1 + F_n2+1 + … + F_nk+1（n₁ < n₂ < … < n_k は連続しない自然数）