フィボナッチ数列の整除性（ｍｏｄ２，３，４，・・・）の周期性については，コラム「フィボナッチ数列と有限体」で述べたのでそれを参照していただきたいのですが，ｋフィボナッチ数列の剰余数列にも周期が存在することが証明されます．ここでは行列による周期性の解法のあらすじを紹介します．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】フィボナッチ数列の周期性の解析
Ｆn+1＝Ｆn＋Ｆn-1と同値なベクトルの漸化式を
［Ｆn ］＝［０，１］［Ｆn-1］＝Ａ［Ｆn-1］
［Ｆn+1］ ［１，１］［Ｆn ］ ［Ｆn ］
で置き換えると，
［Ｆn ］＝Ａ^n［Ｆn-1］
［Ｆn+1］ ［Ｆn ］
Ａ＝［０，１］
［１，１］
は対称行列で，
Ａ^2＝［１，１］，Ａ^3＝［１，２］，Ａ^4＝［２，３］
［１，２］ ［２，３］ ［３，５］
Ａ^5＝［３，５］
［５，８］
Ａ^nも対称行列となることに加え，フィボナッチ数列が現れることがわかる．すなわち，
Ａ^n＝Ａ^n-1Ａ＝［Ｆn-2，Ｆn-1］［０，１］＝［Ｆn-1，Ｆn ］ ［Ｆn-1，Ｆn ］［１，１］ ［Ｆn， Ｆn+1］
ここではこの道具を使って，合同式
Ｌ705＝１ （ｍｏｄ７０５）
を確かめてみることにするが，Ｌ0＝２，Ｌ1＝１，ｎ＝７０４として
［Ｌ704］＝Ａ^704［２］
［Ｌ705］ ［１］
したがって，Ｌ705＝１（ｍｏｄ７０５）の整除性の周期性はＡ^704（ｍｏｄ７０５）を評価することに等しく，行列の積の演算において７０５の倍数をすべて捨ててよいことになる．
７０４＝６４＋１２８＋５１２
Ａ^64 ＝［１４２，４２３］，Ａ^128＝［２８３，１４１］
［４２３，５６５］ ［１４１，４２４］
Ａ^512＝［４２４，５６４］，Ａ^704＝［１４２，４２３］
［５６４，２８３］ ［４２３，５６５］
［Ｌ704］＝［１４２，４２３］［２］＝［７０７］＝［２］
［Ｌ705］ ［４２３，５６５］［１］ ［１４１１］［１］
より
Ｌ705＝１ （ｍｏｄ７０５）
Ｌ704＝２ （ｍｏｄ７０５）
が成り立つことが示されたことになる．
［参］シェーンベルグ「数学点描」近代科学社（三村護訳）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】ｋフィボナッチ数列の周期性の解析
Ａ＝［０，１］
［１，１］
の拡張行列は
Ａ3 ＝［０，１，０］，Ａ4 ＝［０，１，０，０］
［０，０，１］ ［０，０，１，０］
［１，１，１］ ［０，０，０，１］
［１，１，１，１］
となり，ｋフィボナッチ数列の周期性の解析に応用することができる．
トリボナッチ数列に対しては
Ａ3^n ＝［Ｆn-2，Ｆn-2＋Ｆn-3，Ｆn-1］
［Ｆn-1，Ｆn-1＋Ｆn-2，Ｆn ］
［Ｆn ，Ｆn ＋Ｆn-1，Ｆn+1］
テトラナッチ数列に対しては
Ａ4^n ＝［Ｆn-3，Ｆn-3＋Ｆn-4，Ｆn-3＋Ｆn-4＋Ｆn-5，Ｆn-2］
［Ｆn-2，Ｆn-2＋Ｆn-3，Ｆn-2＋Ｆn-3＋Ｆn-4，Ｆn-1］
［Ｆn-1，Ｆn-1＋Ｆn-2，Ｆn-1＋Ｆn-2＋Ｆn-3 Ｆn ］
［Ｆn ，Ｆn ＋Ｆn-1，Ｆn ＋Ｆn-1＋Ｆn-2，Ｆn+1］
となる．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】ｋフィボナッチ数列の一般項
ｋパスカルの三角形の自己相似性については省略し，ｋフィボナッチ数列の一般項を求めるあらすじを紹介したい．特性方程式
ｘ^2−ｘ−１＝０，ｘ^3−ｘ^2−ｘ−１＝０，・・・は重解をもたないので，これらの行列は対角化可能である．ｋ＝３の場合で示すが，
Ａ3 ＝［０，１，０］
［０，０，１］
［１，１，１］
Ｐ^-1Ａ3Ｐ＝［λ1 ，０，０］，Ｐ^-1Ａ3^nＰ＝［λ1^n，０，０］
［０，λ2 ，０］ ［０，λ2^n，０］
［０，０，λ3 ］ ［０，０，λ3^n］
区間［３／２，２］に実数解をもつ以外にｋが奇数のときは１，ｋが偶数のときには１と区間［−１，０］にも実数解が存在する．たとえば，特性方程式
ｘ^2−ｘ−１＝０
の２つの解は
α＝（１＋√５）／２，β＝（１−√５）／２
ただし，異なるｋ個の固有値はすべて実数というわけではなく，複素数解をもつので注意が必要である．
一方，
Ａ3^n ＝［Ｆn-2，Ｆn-2＋Ｆn-3，Ｆn-1］
［Ｆn-1，Ｆn-1＋Ｆn-2，Ｆn ］
［Ｆn ，Ｆn ＋Ｆn-1，Ｆn+1］
が成り立つので，トリボナッチ数列の一般項は
Ｆn＝α1λ1^n＋α2λ2^n＋α3λ3^n
Ｆ0＝０，Ｆ1＝１，Ｆ2＝１ならば
α1＋α2＋α3＝０
α1λ1＋α2λ2＋α3λ3＝１
α1λ1^2＋α2λ2^2＋α3λ3^2＝１
すなわち，ヴァンデルモンデの行列の入った連立方程式
［１ ，１ ，１ ］［α1］ ［０］
［λ1 ，λ2 ，λ3 ］［α2］＝［１］
［λ1^2，λ2^2，λ3^2］［α3］ ［１］
が得られる．結局，ｋフィボナッチ数列の一般項は行列の対角化と連立方程式の問題に帰着されたことになる．
α1＝λ1／（λ1−λ2）（λ1−λ3）
α2＝λ2／（λ2−λ1）（λ2−λ3）
α3＝λ3／（λ3−λ1）（λ3−λ2）
より，トリボナッチ数列の一般項は
Ｆn＝λ1^n+1／（λ1−λ2）（λ1−λ3）＋λ2^n+1／（λ2−λ1）（λ2−λ3）＋λ3^n+1／（λ3−λ1）（λ3−λ2）
のような部分分数分解の形になる．
ところで，フィボナッチ数列｛Ｆn｝の通常型母関数ｆ（ｘ）は
ｆ（ｘ）＝Ｆ0＋Ｆ1ｘ＋Ｆ2ｘ^2＋Ｆ3ｘ^3＋・・・
ｘｆ（ｘ）＝ Ｆ0ｘ＋Ｆ1ｘ^2＋Ｆ2ｘ^3＋・・・
ｘ^2ｆ（ｘ）＝ Ｆ0ｘ^2＋Ｆ1ｘ^3＋・・・
また，Ｆn＝Ｆn-1＋Ｆn-2より
ｆ（ｘ）＝ｘ／（１−ｘ−ｘ^2）＝ΣＦnｘ^n
と簡単な式になる．ｋフィボナッチ数列の母関数も同様にして
ｆ（ｘ）＝ｘ／（１−ｘ−ｘ^2−・・・−ｘ^k）＝ΣＦnｘ^n
＝Σ（α1λ1^n＋α2λ2^n＋α3λ3^n＋・・・）ｘ^n
具体的には求めないが，
Σλi^nｘ^n＝λiｘ／（１−λiｘ）
より，部分分数分解
Σαiλiｘ／（１−λiｘ）＝ｘ／（１−ｘ−ｘ^2−・・・−ｘ^k）
して両辺を比較することでも，αiが決定されることになる．
こうして，ｋフィボナッチ数列の一般項は
＝Σλi^n+k-2／（λi−λ1）・・・（λi−λi-1）（λi−λi+1）・・・（λi−λk）
であることがわかる．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】ペラン数列
［参］松田修＋津山高専数学クラブ「１１からはじまる数学」東京図書
に最後の章末問題：ペラン数列について説明します．
フィボナッチ数列では正方形をらせん状に並べましたが，ここでは正三角形をらせん状に並べてみましょう．最初の３つの正三角形は１辺の長さを１，次の２つは１辺の長さが２で，そのあとは３，４，５，７，９，１２，１６，２１，・・・．このようにしてもおおよそ対数らせんを描きます．
数列
１，１，１，２，２，３，４，５，７，９，１２，１６，２１，・・・
は直前の１項を除いたその前の２項を加えたものです．パドヴァンの数列と呼ぶことにしますが，漸化式は
Ｐn＝Ｐn-2＋Ｐn-3 （Ｐ0＝Ｐ1＝Ｐ2＝１）
で表されます．
その特性方程式
ｘ^3−ｘ−１＝０
の唯一の実数解より，パドヴァン数列の連続する２項の比は
ｐ＝１／３｛3√（２７／２−３√６９／２）＋3√（１／２＋√６９／１８）｝＝１．３２４７１８・・・
に次第に近づくことになります．ｐがφよりも小さいことより，パドヴァン数列はフィボナッチ数列に較べてゆっくりと増加することになります．
ｐ^5−ｐ^3−ｐ^2＝０
ｐ^4−ｐ^2−ｐ^1＝０
より
ｐ^5−ｐ^4−ｐ^3−ｐ^1＝ｐ^5−ｐ^4−１
ですから，３次方程式ｐ^3−ｐ−１＝０の解はこの５次方程式も満たすことがわかります．あるいは，因数分解
ｐ^5−ｐ^4−１＝（ｐ^3−ｐ−１）（ｐ^2−ｐ＋１）
でもよいのですが，このことから
Ｐn＝Ｐn-1＋Ｐn-5
の関係が成り立つこともわかります．
リュカはパドヴァン数列と同じ生成規則に従い，最初の項の値が異なるものを考案しました（１８７６年）．
Ａn＝Ａn-2＋Ａn-3 （Ａ0＝３，Ａ1＝０，Ａ2＝２）
３，０，２，３，２，５，５，７，１０，１２，１７，２２，２９，・・・
この数列は現在ではペラン数列と呼ばれるものです．この数列の項比もｐに近づきますが，さらに深遠な性質「ｎが素数のときＡnはｎで割り切れる」をもっています．しかし，逆命題「Ａnがｎで割り切れるときｎは素数である」は必ずしも成り立たないことが知られています．ただし，その最小の反例は数万の大きさなので，コンピュータでも使わなければ反証できません．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝