2014/04/04

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

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

フィボナッチ数列に関して導出できるようになっておくべき3つのこと:
1:フィボナッチ数列の一般項が求められる(ビネの公式)
2:隣り合う2項の比の極限は黄金比
3:隣り合う2項は互いに素

フィボナッチ数列とは

フィボナッチ数列とは漸化式:$a_{n}=a_{n-1}+a_{n-2}$ で表される数列のことを言います。多くの場合は初期条件として $a_1=a_2=1$ の場合を考えます。

最初の方から並べて書いてみると,
$1, 1, 2, 3, 5, 8, 13, 21,\cdots$
となります。フィボナッチ数列に登場する数のことをフィボナッチ数といいます。

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

このページではフィボナッチ数列に関する大事な3つの性質を1つずつ解説していきます。特に3番目がおすすめです。

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\{(\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^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$ のときも正しい。

2:フィボナッチ数列の比の極限

ビネの公式から隣り合う2項の比の極限は黄金比$=\dfrac{1+\sqrt{5}}{2}=\alpha$ であることがすぐに分かります:
$\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:フィボナッチ数列と整数問題

このタイプも入試で頻出なのですが,フィボナッチ数列の隣り合う2項が互いに素であることを示します。
背理法と後ろ向き帰納法のコンビネーションで証明します。

証明

$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$ に矛盾

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

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

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

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

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