【８】整数のフィボナッチ数分割

　フィボナッチ数は漸化式

　　Ｆn＝Ｆn-1＋Ｆn-2

に従って，その前の２つの数の合計として順次計算することができて，

　　１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・

となる．

　任意の正の整数ｎは，それを超えない最大のフィボナッチ数と余りに分割されるが，このとき余りもそれを超えない最大のフィボナッチ数と余りに分割され，任意の正の整数ｎは一意的に表すことができる．たとえば，

　　８３＝５５＋２８

　　２８＝２１＋７

　　　７＝５＋２

より，８３＝５５＋２７＋５＋２となる．

　２進法では，８３＝６４＋１６＋２＋１のように隣り合った２のベキ乗がしばしば必要になるが，数のフィボナッチ数分割では，どの２つのフィボナッチ数も隣り合っていないことに注意されたい．「あらゆる正の整数は連続でないフィボナッチ数の和として一意に表記することができる」

フィボナッチ数系では，

　　　　　３＝３

　　　　　４＝３＋１

　　　　　５＝５

　　　　　６＝５＋１

　　　　　７＝５＋２

　　　　　８＝８

　　　　　９＝８＋１

　　　　１０＝８＋２

　　　　１１＝８＋３

　　　１２＝８＝３＋１

・・・・・・・・・・・

　　１０００＝８９７＋１３

　　・・・・・・・・・・・

１００００００＝８３２０４０＋１２１３９３＋４６３６８＋１４４＋２５＝Ｆ30＋Ｆ26＋Ｆ24＋Ｆ12＋Ｆ10

のように，一般に

　　ｎ＝Ｆk1＋Ｆk2＋・・・＋Ｆkn

で表されるのである（ツェッケンドルフの定理）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝