フィボナッチ数列の性質

Copyright (C) virtual_high_school, 2022

§1. フィボナッチ数列とは

§2. フィボナッチ数列の一般項

§3. 加法定理

§4. 2項間の関係

§5. フィボナッチ素数

§1. フィボナッチ数列とは

漸化式

$F_{n+2}=F_{n}+F_{n+1} \mbox{　}(n \geq 1)$
$F_{1}=1,F_{2}=1$

で定義される数列がフィボナッチ数列である。
初めの 20項を（Excel で）計算すると、下表のようになる。

この数列の一般項は、ずらし演算子を $t\mbox{　}(t(F_{n})=F_{n+1})$ とすれば

$F_{n+2}-F_{n+1}-F_{n}= t^2(F_{n})-t(F_{n})-1(F_{n})$
$=(t^2-t-1)(F_{n})=0$

だから、固有方程式

$t^2-t-1=0$

を解いて

$t=\frac{1\pm\sqrt{5}}{2}$

なる解を得るので、フィボナッチ数列の一般項は

$F_{n}=A (\frac{1+\sqrt{5}}{2})^n+B (\frac{1-\sqrt{5}}{2})^n$

となる。($A,B$ は任意の実数)

【「ズラシ演算子と特性方程式」のページ】 ←ここをクリック！

§2. フィボナッチ数列の一般項

【問題2.1】 $F_{n}=A (\frac{1+\sqrt{5}}{2})^n+B (\frac{1-\sqrt{5}}{2})^n$ は 関係式 $F_{n+2}=F_{n}+F_{n+1} $ を満たすことを示せ。---

【証明】 $\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$ とおこう。

$F_{n+2}-F_{n+1}-F_{n}$
$=A(\alpha^{n+2}-\alpha^{n+1}-\alpha^n)+B(\alpha^{n+2}-\alpha^{n+1}-\alpha^n)$
$=A\alpha^{n}(\alpha^{2}-\alpha-1)+B\beta^{n}(\beta^{2}-\beta-1)$

ここで $\alpha,\beta$ は固有方程式 $t^2-t-1=0$ の解であるから、代入すれば $0$ になる。よって

$=A\alpha^{n}\times 0+B\beta^{n}\times 0=0$
$\Rightarrow F_{n+2}-F_{n+1}-F_{n}=0$ ■

【問題2.2】 $F_{n}=A (\frac{1+\sqrt{5}}{2})^n+B (\frac{1-\sqrt{5}}{2})^n$ が初期条件

$F_{1}=1,F_{2}=1$

を満たすように定数 $A,B$ の値を定めよ。---

【解】 $n=1,2$ を代入して

$\left\{ \begin{array}{l}A\alpha+B\beta=1 \\A\alpha^2+B\beta^2=1 \end{array} \right.$

となる。(第2式)− (第1式)$\times \beta$ から

$A=\frac{1-\beta}{\alpha(\alpha-\beta)}$

だが、解と係数の関係から

$\alpha+\beta=1$,
$\alpha\beta=-1$,
$(\alpha-\beta)^2=(\alpha+\beta)^2-4\alpha\beta=5$

だから、

$A=\frac{\alpha}{\alpha(\alpha-\beta)}=\frac{1}{\alpha-\beta}=\frac{1}{\sqrt{5}}$,
$B=\frac{1-A\alpha}{\beta}=\frac{-\beta}{\alpha-\beta}\cdot\frac{1}{\beta}=-\frac{1}{\sqrt{5}}$ …（答）

以上より、フィボナッチ数列の一般項が次のように確定した。すなわち

$F_{n}=\frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n- (\frac{1-\sqrt{5}}{2})^n\}$

§3. 加法定理

【問題3.1】 $F_{n}$ をフィボナッチ数列とするとき、加法定理

$F_{n+m}=F_{m}F_{n+1} + F_{m-1}F_{n}\mbox{　}(n \geq 1,m \geq 2)$

が成り立つことを証明せよ。---

【証明】 $m$ についての数学的帰納法による。$m=2$ のとき、定義より

$F_{n+2}=F_{n+1}+F_{n}$
$=1 F_{n+1}+1 F_{n}$
$=F_{2} F_{n+1}+F_{1} F_{n}$

だから、成り立つ。$m=3$ のときは、

$F_{n+3}=F_{n+2}+F_{n+1}$
$=(F_{2} F_{n+1}+F_{1} F_{n})+F_{n+1}$
$=(F_{2}+1 )F_{n+1}+F_{1} F_{n}$
$=(F_{2}+F_{1} )F_{n+1}+F_{1} F_{n}$
$=F_{3}F_{n+1}+F_{2} F_{n}$

だから、やはり成り立つ。

次に、$m$ 以下のときすべて成り立つと仮定すると

$F_{n+m+1}=F_{n+m}+F_{n+m-1}$
$=(F_{m}F_{n+1} + F_{m-1}F_{n}) +(F_{m-1}F_{n+1} + F_{m-2}F_{n})$
$=(F_{m}+ F_{m-1})F_{n+1} + (F_{m-1}+F_{m-2})F_{n}$
$=F_{m+1}F_{n+1} + F_{m}F_{n}$

よって、$m+1$ のときにも成り立つ。■

§4. 2項間の関係

【問題4.1】 相隣る 2項は互いに素である、すなわち $F_{n}$ と $F_{n+1}$ は互いに素であることを示せ。---

【証明】 数学的帰納法による。$n=1$ のとき $F_{1}=1$ と $F_{2}=1$ はたしかに互いに素である。
次に、 $F_{n}$ と $F_{n+1}$ が互いに素であると仮定する。もし $F_{n+1}$ と $F_{n+2}$ の最大公約数を $d>1$ とするなら

$F_{n+2}=F_{n}+F_{n+1}$
$\Rightarrow F_{n}=F_{n+2}-F_{n+1}$

の右辺は $d$ で割れるから、左辺の $F_{n}$ は $d$ (以上の整数)で割れる。すると $F_{n}$ も $F_{n+1}$ も $d>1$ で割れるから 2数が互いに素であるとの仮定に反する。よって $F_{n+1}$ と $F_{n+2}$ も互いに素である。■

【問題4.2】 $m$ が $n$ で割り切れるとき、$F_{m}$ は $F_{n}$ で割り切れることを証明せよ。---

【証明】 $k>1$ とするとき $F_{kn}$ が $F_{n}$ の倍数であることを示せばよい。数学的帰納法による。$k=2$ のとき加法定理より

$F_{2n}=F_{n+n}$
$=F_{n}F_{n+1} + F_{n-1}F_{n}$
$=F_{n}(F_{n+1}+F_{n-1})$

だから、たしかに $F_{n}$ の倍数になっている。次に $F_{kn}$ が $F_{n}$ の倍数だと仮定すると

$F_{(k+1)n}=F_{kn+n}$
$=F_{n}F_{kn+1}+F_{n-1}F_{kn}$

仮定より第2項は $F_{n}$ の倍数で、第1項も倍数だから、$F_{(k+1)n}$ もそうである。■

§5. フィボナッチ素数

【問題5.1】  $F_{n}$ が素数であるならば、$n=4$ または $n$ は素数であることを証明せよ。---

【証明】 対偶を証明する。$n \neq 4$ かつ $n$ を合成数とする。そこで

$n=n_{1}n_{2},1<n_{1} \leq n_{2} <n$

とする。先の問題より、$F_{n}$ は $F_{n_{2}}$ の倍数になる。しかも

$F_{n_{2}}\neq 1$ かつ $F_{n_{2}}\neq F_{n}$

である。実際、$n_{2}=2$ だと $n=4$ になってしまい仮定に反するので、$n_{2}>2$ となり $F_{n_{2}}>1$ である。また、$n_{2}>2$ だから $n>n_{2}$ に対し $F_{n}>F_{n_{2}}$ である。■

ちなみに、フィボナッチ数列に現れる素数をフィボナッチ素数という。