ゼッケンドルフの定理

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

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

テンプレート:Math

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

テンプレート:Math

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

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

証明

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

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

存在

最初の部分（存在）は数学的帰納法によって示すことができる。テンプレート:Math2 については（これらはフィボナッチ数だから）明らかに真であり、テンプレート:Math2 に対してはテンプレート:Math2 が当てはまる。さて、すべてのテンプレート:Math2 に対してゼッケンドルフの表現が存在すると仮定する。テンプレート:Math2 がフィボナッチ数ならばそれがゼッケンドルフの表現となり、そうでない場合にはテンプレート:Math2 となるテンプレート:Mvar が存在することになる。後者の場合に、テンプレート:Math2 を考えると、テンプレート:Math2 であるから、テンプレート:Mvar は帰納法の仮定により、ゼッケンドルフの表現を持つ。さらに、テンプレート:Math2 でありまたテンプレート:Math2（フィボナッチ数の定義から）だから、テンプレート:Math となってテンプレート:Mvar のゼッケンドルフ表現はテンプレート:Math を含まないことがいえる。よって、テンプレート:Math はテンプレート:Mvar とテンプレート:Mvar のゼッケンドルフの表現の和として表すことができる。

一意性

後半（一意性）を示すには次の補題が必要となる。テンプレート:Math theorem この補題はテンプレート:Mvar についての帰納法で証明することができる。

さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合テンプレート:Mathbf とテンプレート:Mathbf を考える。ここで集合テンプレート:Math とテンプレート:Math を考える。これはそれぞれテンプレート:Mathbf とテンプレート:Mathbf から共通する要素を取り除いたものである（つまり、テンプレート:Math, テンプレート:Math である）。テンプレート:Math とテンプレート:Math の和は等しく、それぞれの集合からテンプレート:Math $\cap$ テンプレート:Math を取り除いたものであることから、テンプレート:Math の和とテンプレート:Math の和もまた等しい。

ここから背理法によってテンプレート:Math とテンプレート:Math の一方は空であることを示す。テンプレート:Math とテンプレート:Math がいずれも空でないと仮定し、テンプレート:Math の最大の要素をテンプレート:Math2 の最大の要素をテンプレート:Mvar とする。テンプレート:Math とテンプレート:Math には共通する要素はないから、テンプレート:Math2 である。ここでテンプレート:Math としても一般性を失わない。このとき補題から、テンプレート:Math の総和はテンプレート:Math より小さく、従ってテンプレート:Mvar よりも小さいが、テンプレート:Math の和は明らかにテンプレート:Mvar 以上である。これはテンプレート:Math とテンプレート:Math の総和が等しいことと矛盾しており、従ってテンプレート:Math かテンプレート:Math の少なくとも一方は空であるといえる。

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

フィボナッチ積

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

例えば、2 のゼッケンドルフの表現はテンプレート:Math, 4 に対するそれはテンプレート:Math2 (テンプレート:Math は用いない) であるから、 $2 \circ 4 = F_{3 + 4} + F_{3 + 2} = 13 + 5 = 18$ となる。

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

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

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

F_{n - 2} = F_{n} - F_{n - 1},

とし、これをすべての整数について適用することで負数番テンプレート:Mvar にも拡張することができ、次の性質を満たす。

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

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

たとえばテンプレート:Math であるから、この表現の一意性は連続するフィボナッチ数を用いないという条件に依存している。

この表現によって、ゼッケンドルフの表現と同様に整数を符号化することが可能であるテンプレート:Small。整数テンプレート:Mvar を表す文字列においては、テンプレート:Mvar 番目の桁はテンプレート:Mvar がテンプレート:Mvar を表す和に現れるなら 1, そうでないなら 0 となる。例えばテンプレート:Math2 であるから 24 は 9, 6, 4, 1 桁目に 1 を置いて 100101001 によって表現できる。整数テンプレート:Mvar が奇数桁でこのように表されることと、テンプレート:Math2 であることは同値である。

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

参考文献

外部リンク

↑ Knuth, Donald. "Negafibonacci Numbers and the Hyperbolic Plane" Paper presented at the annual meeting of the Mathematical Association of America, The Fairmont Hotel, San Jose, CA. 2008-12-11 <http://www.allacademic.com/meta/p206842_index.html>
↑ Wythoff_setumei.pdf 数学パズル・ゲームの広場

[1] Knuth, Donald. "Negafibonacci Numbers and the Hyperbolic Plane" Paper presented at the annual meeting of the Mathematical Association of America, The Fairmont Hotel, San Jose, CA. 2008-12-11 <http://www.allacademic.com/meta/p206842_index.html>

[2] Wythoff_setumei.pdf 数学パズル・ゲームの広場

[1]

[2]

ゼッケンドルフの定理

目次

証明

フィボナッチ積

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

関連項目

脚注

参考文献

関連項目

外部リンク

ナビゲーションメニュー

ゼッケンドルフの定理

証明

フィボナッチ積

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

関連項目

脚注

参考文献

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー