|
|
| 1行目: |
1行目: |
| − | [[Image:Zeckendorf representations.svg|thumb|right|320px|正の整数の最初 160 個（X軸上) をゼッケンドルフの表現で表したもの。長方形それぞれの色がフィボナッチ数列での番号、高さが値に対応している。]]
| + | {{テンプレート:20180815sk}} |
| − | '''ゼッケンドルフの定理'''は[[整数]]の[[フィボナッチ数]]の和としての表現に関する定理である。名前は[[ベルギー]]の[[数学者]]、[[:en:Edouard Zeckendorf|Edouard Zeckendorf]] に由来する。
| |
| − | ゼッケンドルフの定理は、任意の[[正の整数]]が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できるというものである。より厳密には、{{Math_theorem|''N'' を任意の正の整数とすれば、{{math|''c''<sub>''i'' + 1</sub> > ''c''<sub>''i''</sub> + 1}} を満たす正の整数 {{math|''c''<sub>''i''</sub> ≥ 2}} が存在して、
| |
| − | | |
| − | :<math>N = \sum_{i = 0}^k F_{c_i}</math>
| |
| − | | |
| − | （ただし ''F<sub>n</sub>'' は ''n'' 番目のフィボナッチ数）}}というものである。このような和は ''N'' の '''ゼッケンドルフの表現''' と呼ばれる。<!--The [[Fibonacci coding]] of {{mvar|N}} can be derived from its Zeckendorf representation.-->
| |
| − | | |
| − | 例えば、100 のゼッケンドルフの表現は
| |
| − | :{{math|1=100 = 89 + 8 + 3}}
| |
| − | となる。100 をフィボナッチ数の和として表す方法は他にも
| |
| − | :{{math|1=100 = 89 + 8 + 2 + 1}}
| |
| − | :{{math|1=100 = 55 + 34 + 8 + 3}}
| |
| − | のように存在するが、これらはそれぞれ 1 と 2, 34 と 55 が連続するフィボナッチ数であるため、ゼッケンドルフ表現ではない。
| |
| − | | |
| − | 任意の正の整数に対して、ゼッケンドルフの定理の条件を満たす表現は、各段階で可能な最大のフィボナッチ数を選ぶ[[貪欲法]]によって得ることができる。
| |
| − | | |
| − | ==証明==
| |
| − | ゼッケンドルフの定理はふたつの部分に分けられる。
| |
| − | #'''存在''': 任意の正の整数 ''n'' に対してゼッケンドルフの表現が存在する。
| |
| − | #'''一意性''': どの正の整数 ''n'' も、相異なるふたつのゼッケンドルフの表現を持たない。
| |
| − | | |
| − | ;存在
| |
| − | 最初の部分（存在）は[[数学的帰納法]]によって示すことができる。{{math|1=''n'' = 1, 2, 3}} については（これらはフィボナッチ数だから）明らかに真であり、{{math|1=''n'' = 4}} に対しては {{math|1=4 = 3 + 1}} が当てはまる。さて、すべての {{math|''n'' ≤ ''k''}} に対してゼッケンドルフの表現が存在すると仮定する。{{math|''k'' + 1}} がフィボナッチ数ならばそれがゼッケンドルフの表現となり、そうでない場合には {{math|''F''<sub>''j''</sub> < ''k'' + 1 < ''F''<sub>''j'' + 1</sub> }} となるような {{mvar|j}} が存在することになる。後者の場合に、 {{math|1=''a'' = ''k'' + 1 − ''F''<sub>''j''</sub> }} を考えると、{{math|''a'' ≤ ''k''}} であるから、 {{mvar|a}} は帰納法の仮定により、ゼッケンドルフの表現を持つ。さらに、{{math|''F''<sub>''j''</sub> + ''a'' < ''F''<sub>''j'' + 1</sub>}} でありまた {{math|''F''<sub>''j'' + 1</sub> {{=}} ''F''<sub>''j''</sub> + ''F''<sub>''j'' − 1</sub>}} （フィボナッチ数の定義から）だから、{{math|''a'' < ''F''<sub>''j'' − 1</sub>}} となって {{mvar|a}} のゼッケンドルフ表現は {{math|''F''<sub>''j'' − 1</sub> }} を含まないことがいえる。よって、{{math|''k'' + 1}} は {{mvar|F<sub>j</sub>}} と {{mvar|a}} のゼッケンドルフの表現の和として表すことができる。
| |
| − | ;一意性
| |
| − | 後半（一意性）を示すには次の補題が必要となる。
| |
| − | | |
| − | {{Math_theorem|補題|最大の要素が {{mvar|F<sub>j</sub>}} であるような、連続せず互いに異なったフィボナッチ数の任意の空でない集合について、その和は {{math|''F''<sub>''j'' + 1</sub>}} より（実際に）小さい。}}
| |
| − | | |
| − | この補題は {{mvar|j}} についての帰納法で証明することができる。
| |
| − | | |
| − | さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合 {{math|'''S'''}} と {{math|'''T'''}} を考える。ここで集合 {{math|'''S<var>′</var>'''}} と {{math|'''T<var>′</var>'''}}<!-- the use of <var>′</var> instead of ''′'' is not a necessity if the CSS defines "span.texhtml i" properly, along with "span.texhtml var". see [[template:math]] --> を考える。これはそれぞれ {{math|'''S'''}} と {{math|'''T'''}} から共通する要素を取り除いたものである（つまり、{{math|1='''S<var>′</var>''' = '''S''' <span lang="en">\</span> '''T'''}}, {{math|1='''T<var>′</var>''' = '''T''' <span lang="en">\</span> '''S'''}} である）。{{math|'''S'''}} と {{math|'''T'''}} の和は等しく、それぞれの集合から {{math|'''S''' <!---->}}<math>\cap</math>{{math| '''T'''}} を取り除いたものであることから、{{math|'''S<var>′</var>'''}} の和と {{math|'''T<var>′</var>'''}} の和もまた等しい。
| |
| − | | |
| − | ここから[[背理法]]によって {{math|'''S<var>′</var>'''}} と {{math|'''T<var>′</var>'''}} の一方は空であることを示す。{{math|'''S<var>′</var>'''}} と {{math|'''T<var>′</var>'''}} がいずれも空でないと仮定し、{{math|'''S<var>′</var>'''}} の最大の要素を {{mvar|F<sub>s</sub>}}, {{math|'''T<var>′</var>'''}} の最大の要素を {{mvar|F<sub>t</sub>}} とする。{{math|'''S<var>′</var>'''}} と {{math|'''T<var>′</var>'''}} には共通する要素はないから、{{math|''F''<sub>''s''</sub> ≠ ''F''<sub>''t''</sub>}} である。ここで {{math|''F''<sub>''s''</sub> < ''F''<sub>''t''</sub>}} としても[[一般性を失わない]]。このとき補題から、{{math|'''S<var>′</var>'''}} の総和は {{math|''F''<sub>''s'' + 1</sub>}} より小さく、従って {{mvar|F<sub>t</sub>}} よりも小さいが、{{math|'''T<var>′</var>'''}} の和は明らかに {{mvar|F<sub>t</sub>}} 以上である。これは {{math|'''S<var>′</var>'''}} と {{math|'''T<var>′</var>'''}} の総和が等しいことと矛盾しており、従って {{math|'''S<var>′</var>'''}} か {{math|'''T<var>′</var>'''}} の少なくとも一方は空であるといえる。
| |
| − | | |
| − | このとき {{math|'''S<var>′</var>'''}} が空であるとしても一般性を失わない。すると {{math|'''S<var>′</var>'''}} の和は 0 であり、このため {{math|'''T<var>′</var>'''}} の和も同様に 0 であるはずである。{{math|'''T<var>′</var>'''}} の要素は正の整数のみであるから、これを満たすためには {{math|'''T<var>′</var>'''}} は空集合でなければならない。従って {{math|1='''S<var>′</var>''' = '''T<var>′</var>''' = <!---->}}<math>\emptyset</math>, すなわち {{math|1='''S''' = '''T'''}} であって、ゼッケンドルフの表現の一意性が示された。
| |
| − | | |
| − | ==フィボナッチ積==
| |
| − | 自然数 {{mvar|a}}, {{mvar|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 のゼッケンドルフの表現は {{math|F<sub>3</sub>}}, 4 に対するそれは {{math|F<sub>4</sub> + F<sub>2</sub>}} ({{math|F<sub>1</sub>}} は用いない) であるから、<math>2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18</math> となる。
| |
| − | | |
| − | 和の順序を入れ替えることでこれが[[可換]]であることは示すことができるが、[[ドナルド・クヌース]]はさらに、この演算が[[結合法則|結合的]]でもあるということを証明した。
| |
| − | | |
| − | ==負数番のフィボナッチ数を用いた表現==
| |
| − | フィボナッチ数列は、[[漸化式]]を書き換えて
| |
| − | :<math>F_{n-2} = F_n - F_{n-1}, \, </math>
| |
| − | とし、これをすべての整数について適用することで負数番 {{mvar|n}} にも拡張することができ、次の性質を満たす。
| |
| − | :<math>F_{-n} = (-1)^{n+1} F_n. \, </math>
| |
| − | | |
| − | 任意の整数は、連続したフィボナッチ数を使わない形で負数番のフィボナッチ数の和として一意に表すことができる<ref>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></ref>。例えば
| |
| − | | |
| − | * {{math|1=−11 = ''F''<sub>−4</sub> + ''F''<sub>−6</sub> = (−3) + (−8)}}
| |
| − | * {{math|1=12 = ''F''<sub>−2</sub> + ''F''<sub>−7</sub> = (−1) + 13}}
| |
| − | * {{math|1=24 = ''F''<sub>−1</sub> + ''F''<sub>−4</sub> + ''F''<sub>−6</sub> + ''F''<sub>−9</sub> = 1 + (−3) + (−8) + 34}}
| |
| − | * {{math|1=−43 = ''F''<sub>−2</sub> + ''F''<sub>−7</sub> + ''F''<sub>−10</sub> = (−1) + 13 + (−55)}}
| |
| − | * 0 は空集合に対する和として表される。
| |
| − | | |
| − | たとえば {{math|1=0 = ''F''<sub>−1</sub> + ''F''<sub>−2</sub> }} であるから、この表現の一意性は連続するフィボナッチ数を用いないという条件に依存している。
| |
| − | | |
| − | この表現によって、ゼッケンドルフの表現と同様に[[整数]]を符号化することが可能である<small>([[:en:NegaFibonacci_coding]])</small>。整数 {{mvar|x}} を表す文字列においては、{{mvar|n}} 番目の桁は {{mvar|F<sub>n</sub>}} が {{mvar|x|}} を表す和に現れるなら 1, そうでないなら 0 となる。例えば {{math|1=24 = ''F''<sub>−1</sub> + ''F''<sub>−4</sub> + ''F''<sub>−6</sub> + ''F''<sub>−9</sub> }} であるから 24 は 9, 6, 4, 1 桁目に 1 を置いて 100101001 によって表現できる。整数 {{mvar|x}} が奇数桁でこのように表されることと、{{math|''x'' > 0}} であることは同値である。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{脚注ヘルプ}}
| |
| − | {{reflist}}
| |
| − | | |
| − | ==参考文献==
| |
| − | *{{Cite book|和書|author=[[中村滋 (数学者)|中村滋]]|date=2008-01|title=フィボナッチ数の小宇宙（ミクロコスモス） フィボナッチ数、リュカ数、黄金分割|edition=改訂版|publisher=日本評論社|isbn=978-4-535-78492-5|ref={{Harvid|中村|2008}}}}
| |
| − | * {{Citation | first=Donald E. | last=Knuth | authorlink=Donald Knuth | title=Fibonacci multiplication |journal=Applied Mathematics Letters |volume=1 |issue=1 |year=1988 |pages=57–60 | doi=10.1016/0893-9659(88)90176-0 | zbl=0633.10011 | issn=0893-9659 }}
| |
| − | * {{Citation | zbl=0252.10011 | last=Zeckendorf | first=E. | title=Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas | language=仏語 | journal=Bull. Soc. R. Sci. Liège | volume=41 | pages=179-182 | year=1972 | issn=0037-9565 }}
| |
| − | | |
| − | ==関連項目==
| |
| − | {{Div col}}
| |
| − | *{{仮リンク|オストロウスキーの数表現|en|Ostrowski numeration}}
| |
| − | *{{仮リンク|フィボナッチ符号|en|Fibonacci coding}}
| |
| − | {{Div col end}}
| |
| − | | |
| − | ==外部リンク==
| |
| − | *{{高校数学の美しい物語|title=ゼッケンドルフの定理とその証明|urlname=zeckendorf}}
| |
| − | *{{MathWorld |title=Zeckendorf's Theorem |urlname=ZeckendorfsTheorem}}
| |
| − | *{{MathWorld |title=Zeckendorf Representation |urlname=ZeckendorfRepresentation}}
| |
| − | *[[:en:cut-the-knot|cut-the-knot]] での [http://www.cut-the-knot.org/ctk/OnePile.shtml#fibnim Zeckendorf's theorem]
| |
| − | *{{SpringerEOM|urlname=Z/z120020|title=Zeckendorf representation|author=G.M. Phillips}}
| |
| − | *{{SloanesRef |sequencenumber=A101330|name=Knuth's Fibonacci (or circle) product}}
| |
| − | | |
| − | {{PlanetMath attribution|id=38810|title=proof that the Zeckendorf representation of a positive integer is unique}}
| |
| − | | |
| − | {{DEFAULTSORT:せつけんとるふのていり}}
| |
| − | [[Category:数の表現]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | <!--[[Category:Fibonacci numbers]]
| |
| − | [[Category:Theorems in number theory]]
| |
| − | [[Category:Articles containing proofs]]-->
| |