ゼッケンドルフの定理

数学において、ゼッケンドルフの定理は、ベルギーのアマチュア数学者エドゥアール・ゼッケンドルフにちなんで名付けられた、整数をフィボナッチ数列の和として表現することに関する定理です。

ゼッケンドルフの定理は、すべての正の整数は、 1つ以上の異なるフィボナッチ数の合計として一意に表すことができ、その合計には2つの連続するフィボナッチ数が含まれないというものです。より正確には、Nが任意の正の整数である場合、c _i ≥ 2 （ c _{i  + 1} > c _i + 1 ）の正の整数が存在し、

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

ここで、F _{n は}n^番目のフィボナッチ数です。このような和はNのゼッケンドルフ表現と呼ばれます。Nのフィボナッチ コードはゼッケンドルフ表現から導出できます。

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

64 = 55 + 8 + 1 .

64をフィボナッチ数列の合計として表す方法は他にもある

64 = 55 + 5 + 3 + 1

64 = 34 + 21 + 8 + 1

64 = 34 + 21 + 5 + 3 + 1

64 = 34 + 13 + 8 + 5 + 3 + 1

しかし、34 と 21 は 5 と 3 と同様に連続するフィボナッチ数であるため、これらはゼッケンドルフ表現ではありません。

任意の正の整数について、そのゼッケンドルフ表現は、各段階で可能な限り最大のフィボナッチ数を選択する 貪欲アルゴリズムを使用して見つけることができます。

この定理は1972年に論文を発表した同名の著者にちなんで名付けられているが、同じ結果は20年前にゲリット・レッケルケルカーによって発表されていた。^{[1]そのため、この定理は}スティグラーの同名法則の一例である。

ゼッケンドルフの定理には 2 つの部分があります。

1. 存在: すべての正の整数nには Zeckendorf 表現があります。
2. 一意性: 正の整数nには 2 つの異なる Zeckendorf 表現はありません。

ゼッケンドルフの定理の最初の部分（存在）は、帰納法によって証明できます。n = 1、2、3の場合、これは明らかに真です（これらはフィボナッチ数であるため）。n = 4の場合、 4 = 3 + 1となります。n がフィボナッチ数であれば、証明するものは何もありません。それ以外の場合は、F _j < n < F _{j  + 1}となるj が存在します。ここで、各正の整数a < nにゼッケンドルフ表現があると仮定し（帰納法の仮説）、b = n − F _jについて考えます。b < nなので、帰納法の仮説により、 b にはゼッケンドルフ表現があります。同時に、b = n − F _j < F _{j  + 1} − F _j = F _{j  − 1 で}あるため（最後の等式でフィボナッチ数の定義を適用）、bのゼッケンドルフ表現にはF _{j  − 1}が含まれず、したがってF _jも含まれません。その結果、nはF _jとbのゼッケンドルフ表現の和として表すことができ、その和に含まれるフィボナッチ数は異なるものとなる。^[2]     

ゼッケンドルフの定理の 2 番目の部分 (一意性) には、次の補題が必要です。

補題: 最大のメンバーがF _jである、異なる非連続フィボナッチ数からなる空でない集合の合計は、次に大きいフィボナッチ数F _{j  + 1} よりも必ず小さくなります。

この補題はjに関する帰納法によって証明できる。

ここで、同じ和 を持つ、連続しない異なるフィボナッチ数からなる2 つの空でない集合とを取ります。および に等しい集合 および から共通要素 (つまり および ) を取り除いたものについて考えます。およびの和は等しく、 および であるため、両方の集合からの要素を正確に取り除いたことになります。 および の和も同じでなければなりません( )。${\displaystyle S}$${\displaystyle T}$${\textstyle \sum _{x\in S}x=\sum _{x\in T}x}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S'=S\setminus T}$${\displaystyle T'=T\setminus S}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cap T}$${\displaystyle S'}$${\displaystyle T'}$${\textstyle \sum _{x\in S'}x=\sum _{x\in T'}x}$

ここで、背理法によって、との少なくとも一方が空であることを示します。その逆、つまりと が両方とも空でない場合を仮定し、 の最大のメンバーを F s 、 の最大のメンバーを F t とします。と_には共通要素_がないため、F _s ≠ F _tです。一般性を失うことなく、F _s < F _tと仮定します。すると、補題により、、および 、という事実により、 であるのに対し、 は明らかに です。これは、と の合計が同じであるという事実と矛盾しており、 または のいずれかが空であると結論付けることができます。 ${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S'}$${\displaystyle T'}$${\textstyle \sum _{x\in S'}x<F_{s+1}}$${\textstyle F_{s}<F_{s+1}\leq F_{t}}$${\textstyle \sum _{x\in S'}x<F_{t}}$${\textstyle \sum _{x\in T'}x\geq F_{t}}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S'}$${\displaystyle T'}$

ここで（一般性を失うことなく）が空であると仮定します。すると の和は 0 となり、 も空になります。しかし は正の整数しか含められないため、 も空になります。結論として、これは を意味し、各ゼッケンドルフ表現が一意であることを証明します。^[2]${\displaystyle S'}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle T'}$${\displaystyle S'=T'=\emptyset }$${\displaystyle 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のゼッケンドルフ表現は であり、4のゼッケンドルフ表現は である（は表現では許されていない）ので、${\displaystyle F_{3}}$${\displaystyle F_{4}+F_{2}}$${\displaystyle F_{1}}$${\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18.}$

（生成物は必ずしもゼッケンドルフ形式であるとは限りません。例えば、） ${\displaystyle 4\circ 4=(F_{4}+F_{2})\circ (F_{4}+F_{2})=F_{4+4}+2F_{4+2}+F_{2+2}=21+2\cdot 8+3=40=F_{9}+F_{5}+F_{2}.}$

単純な和の並べ替えにより、これが可換演算であることがわかります。しかし、ドナルド・クヌースは、この演算は結合的でもあるという驚くべき事実を証明しました。^[3]

フィボナッチ数列は、再配置された再帰関係を使用して 負の指数nに拡張できる 。

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

これは、次の式を満たす「ネガフィボナッチ」 数列を生成する。

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

任意の整数は、連続する2つのネガフィボナッチ数が使用されないネガフィボナッチ数の合計として一意に表現できます^[4]。例:

• −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 ₋₂ なので、表現の一意性は、連続する 2 つの負のフィボナッチ数が使用されないという条件に依存します。

これにより、ゼッケンドルフの定理の表現に似た整数のコード化システムが提供されます。整数xを表す文字列では 、x を表す合計にF _−nが現れる場合、 n^番目の桁は 1 になります。それ以外の場合は、その桁は 0 になります。たとえば、 24 は文字列 100101001 で表すことができますが、24 = F ₋₁ + F ₋₄ + F ₋₆ + F ₋₉であるため、桁 9、6、4、1 に数字 1 が含まれます。整数 x は、 x > 0の場合にのみ、奇数の長さの文字列で表されます。  

• 完全なシーケンス
• フィボナッチコーディング
• フィボナッチニム
• オストロフスキー記数法

• ゼッケンドルフ、E. (1972)。 「フィボナッチの貴族とルーカスの貴族の自然の表現」。ブル。社会R.Sci.リエージュ（フランス語）。41 : 179–182。ISSN  0037-9565。Zbl  0252.10011。

• ワイスタイン、エリック・W.「ゼッケンドルフの定理」。マスワールド。
• ワイスタイン、エリック・W.「ゼッケンドルフの表現」。マスワールド。
• 結び目を切るゼッケンドルフの定理
• GM Phillips (2001) [1994]、「ゼッケンドルフ表現」、数学百科事典、EMS Press
• OEISシーケンス A101330 (クヌースのフィボナッチ (または円) 積)

この記事には、 Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMath上の、正の整数の Zeckendorf 表現が一意であることの証明からの資料が組み込まれています。