3項間漸化式とフィボナッチ数列

3項間漸化式 Recurrence Equation Between 3 Terms

 次のように3項間で定められる数列
 
\[a_{n+2}=p\,a_{n+1}+q\,a_n \tag{1}\]
は数ある漸化式の中でも最も美しい形です。その一般項を求める手順も非常に奥深いものがあり、後述する フィボナッチ数列 もこの形に属しています。まず (1) が
 
\[a_{n+2}=(\alpha+\beta)\,a_{n+1}-\alpha\, \beta a_n \tag{2}\]
という形に表せたとします。するとこの式は
 
\[\begin{align*}a_{n+2}-\alpha a_{n+1}&=\beta(a_{n+1}-\alpha a_n) \tag{3}\\[6pt]
a_{n+2}-\beta a_{n+1}&=\alpha(a_{n+1}-\beta a_n) \tag{4} \end{align*}\]
のように2通りの書き方ができます。まず $\alpha \neq \beta$ の場合を考えます。数列 $\{a_{n+1}-\alpha a_n\}$ と $\{a_{n+1}-\beta a_n\}$ はそれぞれ公比 $\beta$ の等比数列ですから
 
\[\begin{align*}
a_{n+1}-\alpha a_n&=\beta^{\,n-1}(a_2-\alpha a_1)\\[6pt]
a_{n+1}-\beta a_n&=\alpha^{\,n-1}(a_2-\beta a_1)\end{align*}\]
と表せます。この2式から $a_{n+1}$ を消去して
 
\[A=\frac{a_2-\beta a_1}{\alpha-\beta}\,\quad B=\frac{a_2-\alpha a_1}{\beta-\alpha}\]
とおくことにより
 
\[a_n=A \alpha^{n-1}+B \beta^{n-1}\quad (n \geq 3) \tag{5}\]
という一般項を得ることができます。では $\alpha,\:\beta$ は具体的にどのような値をとるのでしょうか。(1) と (2) を比較すると係数の間に
 
\[\alpha+\beta=p,\quad \alpha \beta=-q \tag{6}\]
という関係があることがわかります。これは解の係数の関係によって $\alpha,\:\beta$ が
 
\[x^2-px-q=0 \tag{7}\]
という方程式(特性方程式)の解であることを示しています。というより、このような対応関係になるように (2) の形にしておいたのです。ですから (7) を解いて、その2解を $\alpha,\:\beta$ とおいて (5) に代入すれば一般項が求められます。 $\alpha = \beta$ のとき(つまり特性方程式が重解をもつとき)は (3) と (4) は同じ式なので
 
\[a_n-\alpha a_{n-1}=\alpha^{n-2}(a_2-\alpha a_1)\]
 すなわち
 
\[a_n=\alpha a_{n-1}+\alpha^{n-2}(a_2-\alpha a_1)\]
となります。これは $a_n=pa_{n-1}+q$ の形なので、両辺を $\alpha^n$ で割ると
 
\[\frac{a_n}{\alpha^n}=\frac{a_{n-1}}{\alpha^{n-1}}+\frac{a_2-\alpha a_1}{\alpha^2}\]
となるので、
 
\[b_n=\frac{a_n}{\alpha^n},\quad c=\frac{a_2-\alpha a_1}{\alpha^2}\]
とおくと、
 
\[b_n=b_{n-1}+c\]
 これは公差 $c$ の等差数列なので、
 
\[b_n=b_1+(n-1)c\]
となり、数列 $\{a_n\}$ の一般項は
 
\[a_n=a_1\alpha^{n-1}+(n-1)(a_2-\alpha a_1)\alpha_{n-2} \tag{8}\]
で表されることになります。以上まとめると

 漸化式
\[a_{n+2}=pa_{n+1}+qa_n\] の一般項 $a_n$ は
\[x^2-px-q=0\] の解を $\alpha,\:\beta$ として
\[a_n=\left\{\begin{matrix}
A \alpha^{n-1}+B \beta^{n-1}\quad (\alpha \neq \beta)\\[6pt]
a_1\alpha^{n-1}+(n-1)(a_2-\alpha a_1)\alpha_{n-2}\quad (\alpha =\beta )
\end{matrix}\right.\] で与えられます。

 

フィボナッチ数列 Fibonacci's Sequence

 このタイプの漸化式で最も有名な数列は $p=q=1$ とした フィボナッチ数列 です。
 
\[a_1=a_2=1,\quad a_{n+2}=a_{n+1}+a_n\]
 特性方程式は
 
\[x^2-x-1=0\]
となるので、これを解いて
 
\[\alpha=\frac{1+\sqrt{5}}{2},\quad \beta=\frac{1-\sqrt{5}}{2}\]
が得られるので、
 
\[a_n=A \alpha^{\,n-1}+B \beta^{\,n-1}\quad (n \geq 3)\]
に代入すると
 
\[a_n=\frac{1}{\sqrt{5}}\, \left \{ \left ( \frac{1+\sqrt{5}}{2}^n \right )-\left ( \frac{1-\sqrt{5}}{2} \right )^n \right \} \tag{9}\]
という一般項が得られます。具体的な値を代入すると

1, 1, 2, 3, 5, 8, 13, 21, 44, ......

という数列が得られるはずです。

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください