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} + p x + q = 0$

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

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

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

$a_{n} = A α^{n} + B β^{n}$

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

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

例題 1：異なる 2 解

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

特性方程式は $x^{2} - 5 x + 6 = 0$ で、 $(x - 2) (x - 3) = 0$ より $α = 2$ 、 $β = 3$ 。

$a_{n} = A \cdot 2^{n} + B \cdot 3^{n}$

初期条件を代入します。

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

上の式を 2 倍して引くと $3 B = 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} - 4 a_{n + 1} + 4 a_{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} = (A n + B) \cdot 2^{n}$

代入します。

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

$A + B = \frac{1}{2}$ 、 $2 A + 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$ の解は次のとおり。

$α = \frac{1 + 5}{2}, β = \frac{1 - 5}{2}$

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

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

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

別解：2 段階に分ける

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

$a_{n + 2} - α a_{n + 1} = β (a_{n + 1} - α a_{n})$

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

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

例題 4：別解で解く

例題 1 を別解でやってみます。 $α = 2$ 、 $β = 3$ です。

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

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

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

$a_{n} = 3^{n} - 2^{n}$

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

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

練習問題

$a_{n + 2} - 6 a_{n + 1} + 8 a_{n} = 0$ の特性方程式の解はどれですか。

$1$ と $8$
$2$ と $4$
$- 2$ と $- 4$
$3$ と $5$

__RESULT__

$x^{2} - 6 x + 8 = (x - 2) (x - 4) = 0$ です。一般項は $A \cdot 2^{n} + B \cdot 4^{n}$ の形になります。

特性方程式が重解 $x = 3$ になったとき、一般項の形はどれですか。

$A \cdot 3^{n}$
$(A n + B) \cdot 3^{n}$
$A \cdot 3^{n} + B$
$A \cdot 3^{n} + B \cdot 3^{- n}$

__RESULT__

$A \cdot 3^{n}$ だけでは定数が 1 つしかなく、初期条件 2 つに合わせられません。 $n$ を掛けた項を足して定数を 2 つにします。

参考文献

Linear recurrence with constant coefficients - Wikipedia

Oscar Levin, *Discrete Mathematics: An Open Introduction*, 2.4 Solving Recurrence Relations（特性根の方法と重解の場合）, University of Northern Colorado

a(n+2) + p a(n+1) + q a(n) = 0 に等比数列を当てはめると、n が消えて 2 次方程式だけが残ります。この特性方程式の解が 2 つなら、2 つの等比数列を重ねた形が答え。片方が伸び、もう片方が削るという足し引きを図で確かめます。重解のときに n を掛けた項が要る理由、フィボナッチ数列に黄金比が現れる仕組み、2 段階に分ける別解まで。