2 つ前まで見る漸化式、三項間漸化式と特性方程式

$a_{n+2}+p{a}_{n+1}+q{a}_n=0$ は、2 つ前の項まで見て次を決める漸化式です。三項間漸化式といいます。

初期条件も 2 つ要ります。$a_1$ と $a_2$ を決めれば、あとは順に定まる^[1]。

等比数列を当てはめてみる

答えの形を当てずっぽうで置いてみます。$a_n=x^n$ が解になるとしたら何が起きるか。

$$x^{n+2}+p{x}^{n+1}+q{x}^n=0$$

$x^n$ でくくると、$n$ が消えて $x$ だけの方程式が残ります。

$$x^2+px+q=0$$

これが特性方程式です^[1][2]。2 次方程式なので、解はふつう 2 つ出ます。

解が 2 つあるときは足し合わせる

$x^2+px+q=0$ の解を $\alpha$、$\beta$ とします。${\alpha }^n$ も ${\beta }^n$ も漸化式を満たすので、それらを定数倍して足したものも満たします。

$$a_n=A{\alpha }^n+B{\beta }^n$$

$A$ と $B$ は、$a_1$ と $a_2$ の値から決めます^[2]。未知数 2 つに条件 2 つなので、ちょうど決まる。

2 つの等比数列を重ねたものが答えになります。片方が大きく伸び、もう片方がそれを削る。その差がもとの数列です。

例題 1：異なる 2 解

$a_1=1$、$a_2=5$、$a_{n+2}-5a_{n+1}+6a_n=0$ を解きます。

特性方程式は $x^2-5x+6=0$ で、$(x-2)(x-3)=0$ より $\alpha =2$、$\beta =3$。

$$a_n=A\cdot 2^n+B\cdot 3^n$$

初期条件を代入します。

$$2A+3B=1,4A+9B=5$$

上の式を 2 倍して引くと $3B=3$、$B=1$。すると $A=-1$ です。

$$a_n=3^n-2^n$$

$n=3$ で確かめます。漸化式では $5\cdot 5-6\cdot 1=19$、公式では $27-8=19$。合いました。

例題 2：重解のとき

$a_1=1$、$a_2=4$、$a_{n+2}-4a_{n+1}+4a_n=0$ を解きます。

特性方程式は $(x-2{)}^2=0$ で、解が $2$ ひとつだけ。$A\cdot 2^n+B\cdot 2^n$ と置いても $(A+B)2^n$ にまとまってしまい、条件 2 つを満たせません。

重解のときは $n$ を掛けた項を用意します^[1][2]。

$$a_n=(An+B)\cdot 2^n$$

代入します。

$$(A+B)\cdot 2=1,(2A+B)\cdot 4=4$$

$A+B=\frac{1}{2}$、$2A+B=1$ から $A=\frac{1}{2}$、$B=0$。

$$a_n=\frac{n}{2}\cdot 2^n=n\cdot 2^{n-1}$$

$n=3$ で確かめます。漸化式では $4\cdot 4-4\cdot 1=12$、公式では $3\cdot 4=12$。合いました。

例題 3：フィボナッチ数列

$a_1=1$、$a_2=1$、$a_{n+2}=a_{n+1}+a_n$ を解きます。移項すると $a_{n+2}-a_{n+1}-a_n=0$ です。

特性方程式 $x^2-x-1=0$ の解は次のとおり。

$$\alpha =\frac{1+\sqrt{5}}{2},\beta =\frac{1-\sqrt{5}}{2}$$

$\alpha$ が黄金比です。$A{\alpha }^n+B{\beta }^n$ と置いて初期条件を入れると、$A=\frac{1}{\sqrt{5}}$、$B=-\frac{1}{\sqrt{5}}$ になります。

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

すべての項が整数なのに、式には $\sqrt{5}$ が並びます。$\beta$ の絶対値が $1$ より小さいので、$n$ が大きいと第 1 項だけでほぼ決まる。

別解：2 段階に分ける

特性方程式の解 $\alpha$、$\beta$ を使うと、漸化式は次のように書き直せます。

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

展開して $\alpha +\beta =-p$、$\alpha \beta =q$ を使えば、もとの式に戻ります。

つまり $\{a_{n+1}-\alpha a_n\}$ は公比 $\beta$ の等比数列。$\alpha$ と $\beta$ を入れかえた式も同時に成り立ちます。

例題 4：別解で解く

例題 1 を別解でやってみます。$\alpha =2$、$\beta =3$ です。

$$a_{n+1}-2a_n=3^{n-1}(a_2-2a_1)=3^{n-1}\cdot 3=3^n$$

$$a_{n+1}-3a_n=2^{n-1}(a_2-3a_1)=2^{n-1}\cdot 2=2^n$$

2 つの式を引き算すると $a_{n+1}$ が消えます。

$$a_n=3^n-2^n$$

同じ答えが出ました。連立してから引くだけなので、こちらのほうが計算が短いこともあります。

重解のときはこの手が使えません。式が 1 本しか作れないためです。その場合は $(An+B){\alpha }^n$ の形に戻ります。

練習問題

参考文献