フィボナッチ数列について

フィボナッチ数列とは

フィボナッチ数列は、数列の漸化式を学ぶときにその例としてよく取り上げられるものです。数列の構成は割合単純ですが、その一般項や性質を理解するにはやや難しいところもあります。ここでは、まずフィボナッチ数列の基本をまとめておきましょう。きっかけは、ある公立中学の定期テストの問題として、出題されている例をみかけたことにあります。前提とする知識が少ないにも関わらず生徒に出題するのはいかがなものかと思います。

フィボナッチ数列の定義

フィボナッチ数列の定義は明確です。

\(n\)を自然数とするとき、\(a_{n+2}＝a_{n+1}+a_n\) ･･････①　で構成される数列　\(a_n\)のことです。通常　\(a_1=a_2＝1\)とします。
すなわち、\(1,1,2,3,5,8,13,21,･･････････\)　となる数列です。\(n\)　が大きくなると、この数列の値が相当大きくなることが予想されます。
この数列は、3項間の漸化式ですから、一般項を求めるのは容易です。

①の数列を変形し

\(a_{n+2}－α・a_{n+1}＝β(a_{n+1}－a_n)\)　･････････②　とすれば同時に
\(a_{n+2}－β・a_{n+1}＝α(a_{n+1}－a_n)\) ･････････③　も成り立ちます。

また、フィボナッチ数列をこれからは　￥(F_n\)　としましょう。この各項を　ある数で割った余りが、周期性を持つことは少しやればわかりますが、この性質は証明なしに使うべきではないと思います。

②、③は\(α、β\)について、対称形です。①と比較すれば、\(α+β＝1、α・β＝－1\)　よって、\(α、β\)　は、\(t^2－t－1＝0\)の解ですから、
\(ｔ＝(1±\sqrt{5})/2\)　です。

これから、②、③　は、
\(a_{n+2}－α・a_{n+1}＝β^{n－1}・(a_{n+1}－a_n)\)
\(a_{n+2}－β・a_{n+1}＝α^{n－1}・(a_{n+1}－a_n)\)
これから、辺辺引いて、
\(a_n＝1/(α－β)・(α^{n-1}・(１－β)+β^{n-1}・(1－α））＝1/\sqrt{5}・(α^n－β^n)\)
具体的に書くと

\(a_n＝1/\sqrt{5}・((1+\sqrt{5}/2)^n－(1－\sqrt{5}/2)^n)\)

\((1+\sqrt{5})/2 \)　は有名な黄金分割比であり、連分数展開でも表せます。

もちろん漸化式は、特性方程式を使ってもかまいません。ここまでは計算さえいとわなければ楽に導出できます。少し高校数学を学んでいればできます。ただし一般の生徒には無理でしょう。

では、何が問題なのでしょうか。それはフィボナッチ数列の性質に関する問題です。例えば、来年の年号の　\(2021\)　に関連して、\(a_{2021}\)　を具体的に求めさせることは、まず無理です。何桁になるか想像もできない大変大きな数字です。一般項を導出するよりはるかに難しい問題です。

フィボナッチ数列の性質

また、フィボナッチ数列をこれからは　\(F_n\)　としましょう。この各項を　ある数で割った余りが、周期性を持つことは少しやればわかりますが、この性質は証明なしに使うべきではないと思います。 論理的な証明や数学的帰納法での証明が必要です。

フィボナッチ数列　\(F_n\)　を少し書いてみましょう。

　　\(１，１，２，３，５，８，１３，２１，３４，５５，８９，１４４，２３３，３７７，６１０，９８７，･････\)　となります。

これを、２で割った余り、すなわち各\(F_n\)　の　\(r_n\)　\(mod　2\)　を求めてみると、すなわち\(F_n≡r_n(mod　2)\)
　\(r_n\)：\(１，１，０，１，1，０，１，１，０，１，１，０，1、１，０、･････････\)
つまり、\(mod　2\)　では、周期\(3\)　で　\(1,1,0\)　が繰り返されられると予想されます。
（これは、あくまで予想で有り、確かめられたわけではありません。）

また、\(mod　3\)　では、
　\(r_n\) ：\(１，１，２，０，２，２，１，１，１，２，０，２，２，１\)
つまり、周期は、\(8\)　であり、\(１，１，２，０，２，２，１，０\)　が繰り返されます。

同様に、フィボナッチ数列をどんな数で割ってもいいわけで、一般に　\(mod　n\)　で割った余りは周期をもつことが
予想されます。しかし、これを使うには当然証明が必要です。ここが不足しているところです。

フィボナッチ数列を任意の自然数で割った余り

\(F_n\)　を　ある自然数　\(n\)　で割った余りは、周期をもつことが予想されますが、これを証明してみましょう。

これには、「\(F_n\)　の連続する　2項を　\(n\)　で割った余りが、以前の連続する2項の余りと順序を含めて一致する」
事を言えばよいですね。

\(F_n\)　を　\(n\)　で割った余りの対は、\((0,0),(0,1)、･････････(n-1,n-1)\)　の　\(n^2\)通りあります。
従って、\(n^2+1\)　項を持ってくれば、どれか　\(2\)　項　は一致することになり、直感的な理解はできます。
もう少し、掘り下げてみましょう。・

【証明】
\(n\in N\)　とします。\(N\)　は自然数の集合です。
\(F_n\)を　\(n\)　で割った余りを　\(r_n\)　とすると、\(F_n≡r_n　(mod　n)\)　\(0≦r_n≦n-1\)
ここで、順序を考えた　\(r_n\)　の対を考えると、順序も考えた　\(r_n\)　の対　\((r_n,r_{n+1})\)　は、
\(n^2\)通りの値をとります。よって、\(1≦n≦n^2+1\)　の範囲を考えると、\(l,m　\in N　(l<m) \)　なる
\(l,m\)に対して、\((r_l,r_{l+1})＝(r_m.r_{m+1})\)　となる　\(l,m\)　が存在します。

これで直感的には理解できますが、もう少し低し丁寧に証明してみましょう。

\(n \in N\)　となる自然数とします。フィボナッチ数列の第　各項を　\(n\)　で割った余りを　\(r_n\)　とすると
\(F_n≡r_n　(mod　n)\)　\(0≦r_n≦n-1\)　
ここで、順序を考えた　\(r_n\)　の対　\(r_n、r_{n+1}\)　は、\(0≦r_n≦n-1\)　だから\(n^2\)通りの値をとります。
よって、\(0≦ｎ≦ｎ^2+1\)　の範囲で考えると、この範囲で　自然数　\(l,m　(l<m)\)　に対して
\((r_l,r_{l+1})＝(r_m、r_{m+1})\)　となる　組が存在します。
ここで、\(l=1\)　なら自明
\(l≠1\)　なら、\(mod　ｎ\)　として

　　\(r_{l-1}≡F_{l-1}\)
　　　＝\(F_{l+1}-F_l\)
　　　≡\(r_{ｌ+1}-r_l\)
　　　=\(r_{m+1}-r_m\)
　　　≡\(F_{m+1}-F_m\)
　　　＝\(F_{m-1}\)
　　　≡\(r_{m-1}\)
よって、\(r_{l-1}≡r_{m-1}　(mod　n)\)
また、\(0≦r_{l-1}、r_{m-1}≦n-1\)　より　\(r_{l-1}＝r_{m-1}\)
従って、\((r_{L-1}、r_l)＝r_{m-1}、r_m)\)　となる順序対が存在することになります。
\(ｌ-1＝1\)　なら　自明です。
\(l-1≠1\)　なら同様のプロセスで証明できることになります。

フィボナッチ数列がある程度わかったところで、問題をやってみましょう。

【問題】

　フィボナッチ数列　\(F_n\)　の第1項から第1000項までを考えます。
　\(1000\)　項までのフィボナッチ数列の各項には、一桁目が　\(7\) であるものは、いくつありますか。