例題はこちら（画像をクリックするとPDFファイルで開きます。）
今回のテーマ別演習ではフィボナッチ数列、及びリュカ数列にまつわる話題を取り扱っていきます。
古典的な内容となるため、いいか悪いかは別として知っている人からすればアドバンテージになり得る内容です。
細かな知識を事細かに逐一全て覚えなきゃと身構える必要はなく、高校で学習する基本事項の運用で訊かれていることを導出できればそれで構いません。
一つのストーリーとして気がついたら頭に入っていたという状態となれば幸いです。
シリーズ一覧
第６講では、フィボナッチ数列の加法定理というものを見ていきます。
問題の (3) で示すべき内容である
フィボナッチ数列の加法定理
- \(F_{n+m}=F_{m}F_{n+1}+F_{m-1}F_{n}\)
というものがフィボナッチ数列の加法定理と呼ばれるものです。
フィボナッチ数列には様々な性質がありますが、それら各種性質の導出に貢献する性質です。
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む これについては具体的に書き下していくだけです。 計算ミスすることなく計算を進めていけば \(F_{15}=610\) となります。 という内容の証明で、これについては第２講で扱った内容ですので、そちらを参考にしてください。 今回の肝となる加法定理の証明です。 問題では「数学的帰納法で示せ」という指示があるため、方針面で迷うことはないでしょう。 やっていけば気づくと思いますが、 というフィボナッチ数列の特性上、帰納法の構造についても というタイプの帰納法 ( 通称：一昨日昨日法 ) で仕留めます。 (3) で示した加法定理が強力にはたらいてきます。 \(p=n+m\) , \(q=n\) とすることで \(F_{p}=F_{p-q}F_{q+1}+F_{p-q-1}F_{q}\) という関係式が得られ、移項すれば \(F_{p}-F_{p-q-1}F_{q}=F_{p-q}F_{q+1}\) ということになります。 \(F_{p}\) , \(F_{q}\) がともに \(k\) の倍数であれば、左辺は \(k\) の倍数です。 したがって、右辺も \(k\) の倍数となりますが、 であるため、\(F_{p-q}\) が \(k\) の倍数となるしかなく、題意が示されます。 という (4) の性質から、どんどん添え字を小さくして考えることができます。 \(F_{126}\) , \(F_{78}\) の最大公約数を \(G\) とします。 (4) の性質から ということになり、\(F_{6}=8\) は \(G\) の倍数です。 これより、 \(G \leq 8\) ということになります。 一方、 ８の倍数の判定法 という性質を考えると であるため、\(F_{126}\) , \(F_{78}\) は公約数 \(8\) をもちます。 ゆえに \(G \geq 8\) ということになります。 以上から、\(G=8\) となるしか逃げ道がなくなり、求める最大公約数は \(8\) ということになるわけです。 今回の加法定理において \(n\) が \(m\) の倍数のとき、すなわち \(n=mq\) として加法定理を用いてみると \(F_{m(q+1)}=F_{m}F_{mq+1}+F_{m-1}F_{mq}\) ということが言えます。 これにより、 フィボナッチ数列の整除性 \(n\) が \(m\) の倍数であるとき ということが \(q\) に関する数学的帰納法で示せる見通しが立つと思います。 （これについては【総括】の中で示しています。） 第５講の類題で扱った次の問題 この問題の (2) は見る人が見ると、当然の結果と言えます。 というのも、フィボナッチ数列 \(\{a_{n}\}\) に対して \(a_{6}=8\) ですから、この問題の (2) は と言われていることに他なりません。 そして、それは上述した、フィボナッチ数列の整除性から明らかでしょう。 （もちろん、試験場ではそんな一言で片づけるわけにはいきませんけどね。） 上述した フィボナッチ数列の整除性 \(n\) が \(m\) の倍数であるとき については逆も言えます。 つまり、 という同値性が言えます。 これについて問題形式にしましたので、余力のある人はぜひ考えてみてください。(1) について
(2) について
(3) について
(4) について
(5) について
加法定理の応用
第５講の類題はこちら（画像をクリックするとPDFファイルで開きます。）
追記
補足問題はこちら（画像をクリックするとPDFファイルで開きます。）
