フィボナッチ積
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/05/21 05:07 UTC 版)
「ゼッケンドルフの定理」の記事における「フィボナッチ積」の解説
自然数 a, b に対して次のような演算 a ∘ b {\displaystyle a\circ b} を定義することができる。ゼッケンドルフの表現 a = ∑ i = 0 k F c i ( c i ≥ 2 ) {\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)} と b = ∑ j = 0 l F d j ( d j ≥ 2 ) {\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)} に対して、フィボナッチ積 a ∘ b = ∑ i = 0 k ∑ j = 0 l F c i + d j . {\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.} 例えば、2 のゼッケンドルフの表現は F3, 4 に対するそれは F4 + F2 (F1 は用いない) であるから、 2 ∘ 4 = F 3 + 4 + F 3 + 2 = 13 + 5 = 18 {\displaystyle 2\circ 4=F_{3+4}+F_{3+2}=13+5=18} となる。 和の順序を入れ替えることでこれが可換であることは示すことができるが、ドナルド・クヌースはさらに、この演算が結合的でもあるということを証明した。
※この「フィボナッチ積」の解説は、「ゼッケンドルフの定理」の解説の一部です。
「フィボナッチ積」を含む「ゼッケンドルフの定理」の記事については、「ゼッケンドルフの定理」の概要を参照ください。
- フィボナッチ積のページへのリンク
