ゼッケンドルフの定理

ファイル:Zeckendorf representations.svg

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

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

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

100 = 89 + 8 + 3

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

100 = 89 + 8 + 2 + 1

100 = 55 + 34 + 8 + 3

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

任意の正の整数に対して、ゼッケンドルフの定理の条件を満たす表現は、各段階で可能な最大のフィボナッチ数を選ぶ貪欲法によって得ることができる。

証明

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

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

存在

最初の部分（存在）は数学的帰納法によって示すことができる。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 のゼッケンドルフの表現の和として表すことができる。

一意性

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

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

さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合 S と T を考える。ここで集合 S′ と T′ を考える。これはそれぞれ S と T から共通する要素を取り除いたものである（つまり、S′ = S \ T, T′ = T \ S である）。S と T の和は等しく、それぞれの集合から S [math]\cap[/math] 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′ =[math]\emptyset[/math], すなわち S = T であって、ゼッケンドルフの表現の一意性が示された。

フィボナッチ積

自然数 a, b に対して次のような演算 [math]a\circ b[/math] を定義することができる。ゼッケンドルフの表現 [math]a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2)[/math] と [math]b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2)[/math] に対して、フィボナッチ積 [math]a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}.[/math]

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

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

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

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

[math]F_{n-2} = F_n - F_{n-1}, \, [/math]

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

[math]F_{-n} = (-1)^{n+1} F_n. \, [/math]

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

• −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 であることは同値である。

参考文献

• 中村滋 『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』 日本評論社、2008-01、改訂版。ISBN 978-4-535-78492-5。
• Knuth, Donald E. (1988), “Fibonacci multiplication”, Applied Mathematics Letters 1 (1): 57–60, doi:10.1016/0893-9659(88)90176-0, ISSN 0893-9659, Zbl 0633.10011 
• Zeckendorf, E. (1972), “Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas” (仏語), Bull. Soc. R. Sci. Liège 41: 179-182, ISSN 0037-9565, Zbl 0252.10011 

関連項目

• オストロウスキーの数表現
• フィボナッチ符号

外部リンク

• テンプレート:高校数学の美しい物語
• Weisstein, Eric W. “Zeckendorf's Theorem”. MathWorld（英語）.
• Weisstein, Eric W. “Zeckendorf Representation”. MathWorld（英語）.
• cut-the-knot での Zeckendorf's theorem
• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• テンプレート:SloanesRef