フィボナッチ数列のお話

フィボナッチ数列とはどんなものですか。

具体的に見てみましょう。こういうものです。

最初が$1$で、次が$1$で、その次が$2$で、その次が$3$というように続く数列ですか。

そうですね。最初の二つの数$1$と$1$を足すと三つ目の$2$になり、二つ目と三つ目の$1$と$2$を足すと四つ目の$3$になり……と作っていくんです。

ややこしいですね。

自分でやってみると、ぜんぜんややこしくないですよ。

やってみます。$1+1=2$で、その次は$1+2=3$で、その次は$2+3=5$で……と続くのですね。

こんなふうに表にしてみましょう。

この表はどう読むんですか。

この表は、$n$番目のフィボナッチ数列を$F_n$で表して、$n$と$F_n$の対応を表しています。

$n = 0$から始まっていますね。

はい。この表を見ると、$F_0 = 1$で、$F_1 = 1$ということがわかります。$F_4$は？

$F_4 = 5$でしょうか。

それでいいですね。フィボナッチ数列は二つの数を足し合わせて次の数を作りますので、こんなふうに漸化式（ぜんかしき）で表現できます。

急に難しくなりました。

一つ一つ読めば難しくありませんよ。$F_0 = 1$と$F_1 = 1$は先ほど確認した通りです。

その次が難しいです。

ゆっくり読みましょう。$F_n = F_{n-1} + F_{n-2}$というひとつの式で、$n = 2$のときも$n = 3$のときも、$n = 4$のときも……一度に表現しようとしているんです。

はあ。

たとえば、$n = 2$のときは、$F_n = F_{n-1} + F_{n-2}$はどんな式になるでしょうか。$n$を$2$に置き換えてみるのです。

$F_n = F_{n-1} + F_{n-2}$は$F_2 = F_{2-1} + F_{2-2}$となります。

$F_2 = F_{2-1} + F_{2-2}$というのはつまり、$$F_2 = F_1 + F_0$$ですから、この式で$F_2$を求める方法がわかりますね。

なるほどわかりました。$F_1 + F_0$を計算すればそれが$F_2$であると。

同じように、$n = 3$のときは、$F_n = F_{n-1} + F_{n-2}$は$F_3 = F_{3-1} + F_{3-2}$となり、これは$$F_3 = F_2 + F_1$$になります。このようにして、$$F_n = F_{n-1} + F_{n-2}$$というひとつの式で、「毎回二つを足したものが次の数に等しい」ということを表しているのです。

そういうふうに読むのですね。

この漸化式を使って……