ゼッケンドルフの定理
ウィキペディアから
ウィキペディアから
数学におけるゼッケンドルフの定理とは、任意の正の整数は、1つ以上の、番号が連続しないフィボナッチ数の和として一意に表せるという定理である。名前はベルギーの数学者、Edouard Zeckendorf に由来する。より厳密には、
定理 ― N を任意の正の整数とすれば、ci+1 > ci + 1 を満たす正の整数 ci ≥ 2 が存在して、
（ただし Fn は n 番目のフィボナッチ数）
というものである。このような和は N のゼッケンドルフの表現と呼ばれる。
例えば、100 のゼッケンドルフの表現は
となる。100 をフィボナッチ数の和として表す方法は他にも
のように存在するが、これらはそれぞれ 1 と 2, 34 と 55 が連続するフィボナッチ数であるため、ゼッケンドルフ表現ではない。
与えられた任意の正の整数のゼッケンドルフ表現は、その数を超えない最大のフィボナッチ数を取っていく貪欲法によって得られる。
ゼッケンドルフの定理は2つの部分に分けられる。
最初の部分（存在）は数学的帰納法によって示すことができる。n = 1, 2, 3 については（これらはフィボナッチ数だから）明らかに真であり、n = 4 に対しては 4 = 3 + 1 が当てはまる。さて、すべての n ≤ k に対してゼッケンドルフの表現が存在すると仮定する。k + 1 がフィボナッチ数ならばそれがゼッケンドルフの表現となり、そうでない場合には Fj < k + 1 < Fj+1 となる j が存在することになる。後者の場合に、a = k + 1 − Fj を考えると、a ≤ k であるから、 a は帰納法の仮定により、ゼッケンドルフの表現を持つ。さらに、Fj + a < Fj+1 でありまた Fj+1 = Fj + Fj−1（フィボナッチ数の定義から）だから、a < Fj−1 となって a のゼッケンドルフ表現は Fj−1 を含まないことがいえる。よって、k + 1 は Fj と a のゼッケンドルフの表現の和として表すことができる。
後半（一意性）を示すには次の補題が必要となる。
補題 ― 最大の要素が Fj である、連続せず互いに異なったフィボナッチ数の任意の空でない集合について、その和は Fj+1 より（実際に）小さい。
この補題は j についての帰納法で証明することができる。
さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合 S と T を考える。ここで集合 S′ と T′ を考える。これはそれぞれ S と T から共通する要素を取り除いたものである（つまり、S′ = S \ T, T′ = T \ S である）。S と T の和は等しく、それぞれの集合から S T を取り除いたものであることから、S′ の和と T′ の和もまた等しい。
ここから背理法によって S′ と T′ の一方は空であることを示す。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′ =, すなわち S = T であって、ゼッケンドルフの表現の一意性が示された。
自然数 a, b に対して次の演算 を定義することができる。ゼッケンドルフの表現 と に対して、フィボナッチ積
例えば、2 のゼッケンドルフの表現は F3, 4 に対するそれは F4 + F2 (F1 は用いない) であるから、 となる。
和の順序を入れ替えることでこれが可換であることは示すことができるが、ドナルド・クヌースはさらに、この演算が結合的でもあるということを証明した。
フィボナッチ数列は、漸化式を書き換えて
とし、これをすべての整数について適用することで負数番 n にも拡張することができ、次の性質を満たす。
任意の整数は、連続したフィボナッチ数を使わない形で負数番のフィボナッチ数の和として一意に表すことができる[1]。例えば
たとえば 0 = F−1 + F−2 であるから、この表現の一意性は連続するフィボナッチ数を用いないという条件に依存している。
この表現によって、ゼッケンドルフの表現と同様に整数を符号化することが可能である (en:NegaFibonacci_coding)。整数 x を表す文字列においては、n 番目の桁は Fn が x を表す和に現れるなら 1, そうでないなら 0 となる。例えば 24 = F−1 + F−4 + F−6 + F−9 であるから 24 は 9, 6, 4, 1 桁目に 1 を置いて 100101001 によって表現できる。整数 x が奇数桁でこのように表されることと、x > 0 であることは同値である。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
