ゼッケンドルフの定理
ゼッケンドルフの定理は整数のフィボナッチ数の和としての表現に関する定理である。名前はベルギーの数学者、Edouard Zeckendorf に由来する。
ゼッケンドルフの定理は、任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できるというものである。より厳密には、
定理 ― N を任意の正の整数とすれば、ci + 1 > ci + 1 を満たす正の整数 ci ≥ 2 が存在して、
N = ∑ i = 0 k F c i {\displaystyle N=\sum _{i=0}^{k}F_{c_{i}}}
(ただし Fn は n 番目のフィボナッチ数)
というものである。このような和は N の ゼッケンドルフの表現 と呼ばれる。
例えば、100 のゼッケンドルフの表現は
100 = 89 + 8 + 3
となる。100 をフィボナッチ数の和として表す方法は他にも
100 = 89 + 8 + 2 + 1
100 = 55 + 34 + 8 + 3
のように存在するが、これらはそれぞれ 1 と 2, 34 と 55 が連続するフィボナッチ数であるため、ゼッケンドルフ表現ではない。
任意の正の整数に対して、ゼッケンドルフの定理の条件を満たす表現は、各段階で可能な最大のフィボナッチ数を選ぶ貪欲法によって得ることができる。
S′ と T′ がいずれも空でないと仮定し、S′ の最大の要素を Fs, T′ の最大の要素を Ft とする。S′ と T′ には共通する要素はないから、Fs ≠ Ft である。ここで Fs < Ft としても一般性を失わない。このとき補題から、S′ の総和は Fs + 1 より小さく、従って Ft よりも小さいが、T′ の和は明らかに Ft 以上である。これは S′ と T′ の総和が等しいことと矛盾しており、従って S′ か T′ の少なくとも一方は空であるといえる。
このとき S′ が空であるとしても一般性を失わない。すると S′ の和は 0 であり、このため T′ の和も同様に 0 であるはずである。T′ の要素は正の整数のみであるから、これを満たすためには T′ は空集合でなければならない。従って S′ = T′ = ∅ {\displaystyle \emptyset } , すなわち S = T であって、ゼッケンドルフの表現の一意性が示された。