【数学小話】フィボナッチ数列の一般項 (3項間漸化式)

ちょっと前に、フィボナッチ数列の記事を書きました。今回は数Bで習う数列の知識を使ってその一般項を求めてみます。

hibiyastudy.hatenablog.com

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,...

隣り合った2つの和が次の値になる。そんなルールで作られています。

a₁ = 1 ,a₂ = 1

a_n+2 = a_n+1 + a_n (n≧1)

隣接3項間漸化式と言われるやつです。このパターンの問題の解き方のみならず、特性方程式の考え方もついでに書いてみます。

3項間漸化式の特性方程式

漸化式 $a_{n+2}+pa_{n+1}+qa_n=0$ の $a_{n+2},\ a_{n+1},\ a_n$ をそれぞれ $x^2,\ x,\ 1$ に置きかえて得られる2次方程式
$x^2+px+q=0$
を特性方程式という。

この特性方程式の解を $x=\alpha,\ \beta$ とすると、漸化式を変形して次のような2つの式が得られる。

$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n)\dots①\\a_{n+2}-\beta a_{n+1}=\alpha(a_{n+1}-\beta a_n)\dots②$

①について、 $a_{n+1}-\alpha a_n$ は公比 $\beta$ の等比数列なので、
$a_{n+1}-\alpha a_n=\beta^{n-1}(a_2-\alpha a_1)\dots③$

②について、 $a_{n+1}-\beta a_n$ は公比 $\alpha$ の等比数列なので、
$a_{n+1}-\beta a_n=\alpha^{n-1}(a_2-\beta a_1)\dots④$

③、④より、 $a_n$ の一般項が得られる。

実践してみる

問.フィボナッチ数列
$a_1=1,\ a_2=1,\ a_{n+2}=a_{n+1}+a_n\ (n\geqq1)$
の一般項を求めよ。

解. フィボナッチ数列の漸化式は、 $a_{n+2}=a_{n+1}+a_n$ なので、特性方程式は
$x^2=x+1$
であり、その解は
$\displaystyle x=\frac{1\pm\sqrt{5}}{2}$
である。漸化式はこのように変形できる。

$a_{n+2}-\frac{1+\sqrt{5}}{2} a_{n+1}=\frac{1-\sqrt{5}}{2}(a_{n+1}-\frac{1+\sqrt{5}}{2} a_n)\dots①\\a_{n+2}-\frac{1-\sqrt{5}}{2} a_{n+1}=\frac{1+\sqrt{5}}{2}(a_{n+1}-\frac{1-\sqrt{5}}{2} a_n)\dots②$

(この2つの式はそれぞれ展開、整理すると本来の漸化式に戻ります。計算の練習としてやってみてください。)

①より、

$a_{n+1}-\frac{1+\sqrt{5}}{2} a_n=(\frac{1-\sqrt{5}}{2})^{n-1}(a_2-\frac{1+\sqrt{5}}{2}a_1)=(\frac{1-\sqrt{5}}{2})^{n}\dots③$

②より、

$a_{n+1}-\frac{1-\sqrt{5}}{2} a_n=(\frac{1-\sqrt{5}}{2})^{n-1}(a_2-\frac{1+\sqrt{5}}{2}a_1)=(\frac{1+\sqrt{5}}{2})^{n}\dots④$

④-③より、

$(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2})a_n=(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}\\\displaystyle \underline{a_n=\frac{1}{\sqrt{5}}\bigg\{\bigg(\frac{1+\sqrt{5}}{2}\bigg)^n-\bigg(\frac{1-\sqrt{5}}{2}\bigg)^n\bigg\}}$

これでフィボナッチ数列の一般項が求められました。フィボナッチ数列の項は全て自然数でありながら、一般項には無理数が現れるという、ちょっと不思議な結果になりました。

特性方程式の考え方

特性方程式を考える理由はなにより、等比数列型の漸化式を作るためです。
隣接3項間漸化式の前にこのような漸化式を考えてみます。

$a_{n+1}=2a_n-1\dots①$
このとき特性方程式は、
$x=2x-1$
であり、これを解くと $x=1$ となります。そこで、 $x$ に1を代入した式、
$1=2\times1-1\dots②$
を考え、①-②を考えると、

f:id:hby:20190928153240j:plain

$a_{n+1}-1=2(a_n-1)$
が得られます。 $a_n-1$ は公比2の等比数列です。これで等比数列型の漸化式ができました。

これの応用として、隣接3項間漸化式の特性方程式が、xの2次方程式を作る、というものになります。

漸化式 $a_{n+2}+pa_{n+1}+qa_n=0\dots①$ を変形して等比数列型の漸化式を作るとすると、次のような形になると予想できます。
$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n)$
この式における $\alpha,\ \beta$ を求めたい。これを整理すると、
$a_{n+2}-(\alpha+\beta)a_{n+1}+\alpha\beta a_n\dots②$
となります。①と②の係数を比較して、
$\alpha+\beta=-p,\ \alpha\beta=q$
よって、 $\alpha,\ \beta$ は2次方程式
$x^2+px+q=0$ の解です。
このことから、与えられた隣接3項間漸化式から2次方程式を作って、その解でもって漸化式を等比数列型の漸化式に変形できるのです。

何よりも、等比数列型の漸化式
$a_{n+1}+f(n+1)=p(a_n+f(n))\ (f(n)はnのなんらかの式)$
を得るのが重要なので、例えば、このような問題でもこのように考えると解けます。

問. $a_1=1,\ a_{n+1}=2a_{n}+n-2\ (n\leqq1)$ の一般項を求めよ。

解. 漸化式を変形することで、このような式が得られると予想します。
$a_{n+1}+(A(n+1)+B)=2\{a_n+(An+B)\}$
もともとの漸化式の $a_{n+1},\ a_n$ の係数と、 $a_{n+1},\ a_n$ 以外の部分がnの1次式であることから予想します。これはnに関する恒等式なので、この式を展開してA,Bを求めます。
$a_{n+1}+\{An+(A+B)\}=2a_n+(2An+2B)\\a_{n+1}=2a_n+An+(B-A)$
もとの漸化式と係数を比較して、A=1,B=-1となるので、
$a_{n+1}+((n+1)-1)=2(a_n+n-1)$
ここで $b_n=a_n+(n-1)$ とおくと、
$b_1=1,\ b_{n+1}=2b_n\ (n\leqq1)$
となるので、 $b_n=2^{n-1}$ よって、
$a_n+(n-1)=2^{n-1}\\\underline{a_n=2^{n-1}-n+1}$