最終更新:2019/04/24

フィボナッチ数列の一般項と数学的帰納法

分野: 数列  レベル: 最難関大学

フィボナッチ数列とは,1,1,2,3,5,8,13,21 のように,各項が「前の2つを足した値」になるような数列のこと。

この記事では,フィボナッチ数列の意味を解説した後,フィボナッチ数列の美しい性質を3つ紹介します。

フィボナッチ数列とは

1,1,2,3,5,8,13,21,34,55,…
という数列は,
・最初の2つが1で
・3つめ以降は「前の2つを足した値」になっています。

例えば,$5+8=13$ なので,$5,8,13$ が並んでいます。このような数列のことをフィボナッチ数列と言います。

また,フィボナッチ数列に登場する数字のことをフィボナッチ数と言います。例えば,21や55はフィボナッチ数です。

フィボナッチ数列はいろいろな分野で登場します。大学入試問題では,数列の問題としてだけでなく,場合の数の問題(漸化式をたてて解く問題),整数問題に登場したりもします。

フィボナッチ数列の性質1

フィボナッチ数列:
1,1,2,3,5,8,13,21,34,55
について,どの隣り合う2項も,互いに素(最大公約数は1)です。

例えば,$21$ と $34$ の最大公約数は1です。

これを証明してみましょう。

証明

$a_k$ と $a_{k-1}$ が共通の約数 $p\geq 2$ を持つと仮定する:
$a_k=mp, a_{k-1}=np$
ただし $(m, n, p)$ は整数,と書ける。

漸化式より,
$a_{k-2}=a_{k}-a_{k-1}=(m-n)p$
も $p$ の倍数なので,
$a_{k-1}$ と $a_{k-2}$ も共通因数 $p$ を持つ。
これを繰り返すと $a_2$ と $a_1$ も共通因数 $p$ を持つ。
これは $a_2=a_1=1$ に矛盾

このように,通常の数学的帰納法とは逆向きに進めていく帰納法を後ろ向き帰納法(無限降下法)といいます。数学的帰納法に関しては様々なタイプがあるので,数学的帰納法のパターンまとめを参考にしてみてください。

フィボナッチ数列の性質2:一般項

フィボナッチ数列の $n$ 番目の数字は,
$\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$
と表すことができます。

これを「ビネの公式」と言います。

例えば,
$\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^3-\left(\dfrac{1-\sqrt{5}}{2}\right)^3\right\}$
という一見複雑な式を計算すると,それは3番目のフィボナッチ数である2になります。一般項の式には無理数が含まれていますが,計算してみると整数になるというのは不思議ですね。(この事実を背景とする整数問題も出題されます)

ビネの公式の証明

漸化式:$a_{n}=a_{n-1}+a_{n-2}$ を,$a_1=a_2=1$ のもとで解きます。

フィボナッチ数列は三項間漸化式なので,特性方程式を用いて一般項を求めることができます。しかし,高校数学で登場する三項間漸化式は,ほとんどの場合特性方程式の解が整数となるのですが,フィボナッチ数列の特性方程式の解は無理数なので計算が多少複雑になります。

証明

$x^2=x+1$ の解を $\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{1-\sqrt{5}}{2}$ とおくと,$\alpha+\beta=1, \alpha\beta=-1$ より
$a_n=(\alpha+\beta)a_{n-1}-\alpha\beta a_{n-2}$
これを変形して,$a_n-\alpha a_{n-1}=\beta(a_{n-1}-\alpha a_{n-2})$
よって,$a_n-\alpha a_{n-1}$ は公比 $\beta$ の等比数列となる:
$a_n-\alpha a_{n-1}=\beta^{n-2}(a_2-\alpha a_1)=\beta^{n-1}$
同様にして,
$a_n-\beta a_{n-1}=\alpha^{n-2}(a_2-\beta a_1)=\alpha^{n-1}$
この2式から $a_{n-1}$ を消去して $a_n$ について解く:
$a_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\\
=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}$

ちなみに,上では特性方程式を用いてフィボナッチ数列の一般項を求めましたが,答えを予想する解法の方が高速に一般項を求めることができます。
→三項間漸化式の3通りの解き方

ちなみに,上記ビネの公式は帰納法を用いて簡単に導くこともできます:

証明の概要

$n=1, n=2$ のときビネの公式が正しいことは簡単に確認できる。
$n=k, k+1$ のときにビネの公式が正しいと仮定すると,
$a_{k+2}=\dfrac{\alpha^{k+1}-\beta^{k+1}}{\alpha-\beta}+\dfrac{\alpha^{k}-\beta^{k}}{\alpha-\beta}=\dfrac{\alpha^{k+2}-\beta^{k+2}}{\alpha-\beta}\\
(\because \alpha+1=\alpha^2, \beta+1=\beta^2)$
となり,$n=k+2$ のときも正しい。

フィボナッチ数列の性質3:黄金比

フィボナッチ数列の,隣り合う2項の比は黄金比に近づいていきます。

黄金比とは,$\alpha=\dfrac{1+\sqrt{5}}{2}$ のことです。

例えば,フィボナッチ数列をどんどん計算して,$\dfrac{a_{100001}}{a_{100000}}$ を求めて見ると,それは黄金比とほぼ等しくなります。

これは,ビネの公式から(極限の計算方法を知っていれば)すぐに分かります:
$\displaystyle\lim_{n\to\infty}\dfrac{a_{n+1}}{a_n}=\lim_{n\to\infty}\dfrac{\alpha^{n+1}-\beta^{n+1}}{\alpha^n-\beta^n}=\alpha$
$(\because \alpha > \beta)$

フィボナッチ数列に関する問題は様々なタイプがありますが,背景知識としてはこの3つを知っておけばよいでしょう。また,フィボナッチ数列の次に頻出のカタラン数についても背景知識があるとよいと思います。→カタラン数の意味と漸化式

高校時代はじめてビネの公式を見た時は超感動しました。

Tag: 数学的帰納法のパターンまとめ
Tag: 漸化式の解き方と応用例まとめ
Tag: 数学Bの教科書に載っている公式の解説一覧