|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
ゼッケンドルフの定理は整数のフィボナッチ数の和としての表現に関する定理である。名前はベルギーの数学者、Edouard Zeckendorf に由来する。 ゼッケンドルフの定理は、任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できるというものである。より厳密には、''N'' を任意の正の整数とすれば、 を満たす正の整数 が存在して、 : （ただし ''Fn'' は ''n'' 番目のフィボナッチ数）というものである。このような和は ''N'' の ゼッケンドルフの表現 と呼ばれる。 例えば、100 のゼッケンドルフの表現は : となる。100 をフィボナッチ数の和として表す方法は他にも : : のように存在するが、これらはそれぞれ 1 と 2, 34 と 55 が連続するフィボナッチ数であるため、ゼッケンドルフ表現ではない。 任意の正の整数に対して、ゼッケンドルフの定理の条件を満たす表現は、各段階で可能な最大のフィボナッチ数を選ぶ貪欲法によって得ることができる。 ==証明== ゼッケンドルフの定理はふたつの部分に分けられる。 #存在: 任意の正の整数 ''n'' に対してゼッケンドルフの表現が存在する。 #一意性: どの正の整数 ''n'' も、相異なるふたつのゼッケンドルフの表現を持たない。 最初の部分（存在）は数学的帰納法によって示すことができる。 については（これらはフィボナッチ数だから）明らかに真であり、 に対しては が当てはまる。さて、すべての に対してゼッケンドルフの表現が存在すると仮定する。 がフィボナッチ数ならばそれがゼッケンドルフの表現となり、そうでない場合には となるような が存在することになる。後者の場合に、 を考えると、 であるから、 は帰納法の仮定により、ゼッケンドルフの表現を持つ。さらに、 でありまた （フィボナッチ数の定義から）だから、 となって のゼッケンドルフ表現は を含まないことがいえる。よって、 は と のゼッケンドルフの表現の和として表すことができる。 後半（一意性）を示すには次の補題が必要となる。 : 補題: 最大の要素が であるような、連続せず互いに異なったフィボナッチ数の任意の空でない集合について、その和は より（実際に）小さい。 この補題は についての帰納法で証明することができる。 さて、和の等しい、互いに異なった連続しないフィボナッチ数の空でない集合 と を考える。ここで集合 と を考える。これはそれぞれ と から共通する要素を取り除いたものである（つまり、, である）。 と の和は等しく、それぞれの集合から を取り除いたものであることから、 の和と の和もまた等しい。 ここから背理法によって と の一方は空であることを示す。 と がいずれも空でないと仮定し、 の最大の要素を , の最大の要素を とする。 と には共通する要素はないから、 である。ここで としても一般性を失わない。このとき補題から、 の総和は より小さく、従って よりも小さいが、 の和は明らかに 以上である。これは と の総和が等しいことと矛盾しており、従って か の少なくとも一方は空であるといえる。 このとき が空であるとしても一般性を失わない。すると の和は 0 であり、このため の和も同様に 0 であるはずである。 の要素は正の整数のみであるから、これを満たすためには は空集合でなければならない。従って , すなわち であって、ゼッケンドルフの表現の一意性が示された。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゼッケンドルフの定理」の詳細全文を読む スポンサード リンク
|