3 解の構造

2 節の命題 1 により、 (3) の解を求めるには $N$ 個の線形独立な解を求めればよいことがわかったが、 それはいわゆる特性方程式によって求めることができる。

$N$ 次方程式

$$\sum_{j=0}^{N}p_j\lambda^j =\lambda^N+p_{N-1}\lambda^{N-1}+\cdots+p_1\lambda+p_0 =0$$ (10)

を、(3) の 特性方程式 と呼ぶ。 これは一般には $N$ 個の複素数解を持つが、 条件 (4) によりそれらはいずれも 0 ではない。

(10) を $\lambda^n$ 倍すると、

$$\lambda^{n+N}+p_{N-1}\lambda^{n+N-1}+\cdots+p_1\lambda^{n+1}+p_0\lambda^n=0$$

となる。 これはすなわち $a_n=\lambda^n$ が (3) の 解の一つであることを意味している¹。

よって、特性方程式 (10) の解 $\lambda_0,\lambda_1,\ldots,\lambda_{N-1}$ がすべて違っていれば、

$$\{\lambda_0^{n}\},\ \{\lambda_1^{n}\},\ \ldots,\ \{\lambda_{N-1}^{n}\}$$

が一次独立であることは、例えばファンデルモンドの行列式によってわかるから、 (3) の一般解は、

$$a_n = \sum_{j=0}^{N-1}c_j\lambda_j^n =c_0\lambda_0^n + c_1\lambda_1^n + \cdots + c_{N-1}\lambda_{N-1}^n$$

と表されることになる。

問題は特性方程式 (10) が重解を持つ場合であるが、 この場合は次が成り立つ。

命題 2

$\lambda=\lambda_0$ が (10) の $k$ 重解の場合 ($2\leq k\leq N$)、

$$\{n^j\lambda_0^n\}\hspace{1zw}(j=0,1,\ldots,k-1)$$

の $k$ 個の一次独立な数列がすべて (3) の解となる。

証明

$\lambda=\lambda_0$ が (10) の $k$ 重解であれば、 (10) の左辺は $(\lambda-\lambda_0)^k$ を因数に持つので、 (10) の左辺を $\lambda$ で微分した式に $\lambda=\lambda_0$ を 代入すれば 0 となる。 よって、

$$N\lambda_0^{N-1}+p_{N-1}(N-1)\lambda_0^{N-2}+\cdots p_22\lambda_0+p_1=0$$

が成り立つ。 この式を $\lambda_0$ 倍すると

$$N\lambda_0^N+p_{N-1}(N-1)\lambda_0^{N-1}+\cdots +p_1\lambda_0=0$$ (11)

となるが、これに、 (10) に $\lambda=\lambda_0$ を代入して $n$ 倍したものを加えると、

$$(n+N)\lambda_0^N+p_{N-1}(n+N-1)\lambda_0^{N-1}+\cdots +p_1(n+1)\lambda_0 +p_0n=0$$

となるが、これをさらに $\lambda_0^n$ 倍すれば

$$(n+N)\lambda_0^{n+N}+p_{N-1}(n+N-1)\lambda_0^{n+N-1}+\cdots +p_0n\lambda_0^{n}=0$$

となる。 これは $\{n\lambda_0^n\}$ が (3) の解であることを 意味する。

$k\geq 3$ の場合は、(11) の左辺の $\lambda_0$ を $\lambda$ で置き換えた式

$$N\lambda^N+p_{N-1}(N-1)\lambda^{N-1}+\cdots +p_1\lambda$$

は、(10) の左辺を 1 回微分して $\lambda$ 倍した式であるから、 $(\lambda-\lambda_0)^{k-1}$ を因数に持つ。 よって、やはりこの式を微分したものに $\lambda=\lambda_0$ を 代入すれば 0 となる。

$$N^2\lambda_0^{N-1}+p_{N-1}(N-1)^2\lambda_0^{N-2}+\cdots +p_1=0$$

これを $\lambda_0$ 倍して、

$$N^2\lambda_0^N+p_{N-1}(N-1)^2\lambda_0^{N-1}+\cdots +p_1\lambda_0=0$$

とし、 これに (11) の $2n$ 倍と、 (10) に $\lambda_0$ を代入して $n^2$ 倍したものを加えると、

$$\sum_{j=1}^N p_j j^2\lambda_0^j +\sum_{j=1}^N p_j 2nj\lambda_0^j +\sum_{j=0}^N p_j n^2\lambda_0^j = 0$$

より

$$\sum_{j=0}^N p_j (n+j)^2\lambda_0^j = 0$$

となるので、これを $\lambda_0^n$ 倍すれば、

$$\sum_{j=0}^N p_j (n+j)^2\lambda_0^{n+j} = 0$$

となる。 これは、 $\{n^2\lambda_0^n\}$ が (3) の解であることを 意味する。

以下、これを繰り返せばよい。

これにより、(10) が重解を持つ場合も含めて (3) の解の構造がわかったことになる。

基本的には、$a_n=\lambda^n$ のように等比数列だと考えて得られるのが 特性方程式 (10) なので、 (3) の解がその形の解によってほぼ表現される、 というところが (3) の解の構造の本質となる。

例えば、4 項漸化式

$$a_{n+3}-2a_{n+2}-a_{n+1}+2a_n=0$$

の場合、$a_n=\lambda^n$ とすると

$$\lambda^{n+3}-2\lambda^{n+2}-\lambda^{n+1}+2\lambda^n=0$$

となるので、$\lambda^n$ で割ると

$$\lambda^3-2\lambda^2-\lambda+2=0$$

という 3 次方程式が得られるが、これが特性方程式である。これは、

$$(\lambda-1)(\lambda+1)(\lambda-2)=0$$

と因数分解されるので、 $\lambda=1,-1,2$ と求まる。よって、 $1^n$, $(-1)^n$, $2^n$ という一次独立な解があるので、一般解は、

$$a_n=c_0+c_1(-1)^n+c_22^n$$

と表される。$a_0$, $a_1$, $a_2$ を与えれば、 それにより $c_0$, $c_1$, $c_2$ が決定され、一つの解が決まることになる。

同様に、

$$a_{n+3}-3a_{n+1}+2a_n=0$$

の場合は、特性方程式は $\lambda^3-3\lambda+2=0$ であり、これは

$$(\lambda-1)^2(\lambda+2)=0$$

と因数分解され、$\lambda=1$ は重解になるので、 この場合の一次独立な解は命題 2 により $1^n$, $n\cdot 1^n$, $2^n$ となり、よって、一般解は

$$a_n = c_0+c_1n+c_22^n$$

となる。

フィボナッチ数列 $a_{n+2}-a_{n+1}-a_n=0$ の場合は、特性方程式は

$$\lambda^2-\lambda-1=0$$ (12)

であり、この解は

$$\lambda=\lambda_0,\ \lambda_1 = \frac{1+\sqrt{5}}{2},\ \frac{1-\sqrt{5}}{2}$$

となる。よって、

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

と表される。(1) の $a_0=0$, $a_1=1$ となる解を求めると、

$$a_0=c_0+c_1=0,\hspace{1zw}a_1=c_0\frac{1+\sqrt{5}}{2}+c_1\frac{1-\sqrt{5}}{2}=1$$

の連立方程式を解いて、

$$c_0=\frac{1}{\sqrt{5}},\ c_1=-\frac{1}{\sqrt{5}}$$

となり、これにより (2) が得られる。

つまり、$\sqrt{5}$ は、2 次方程式 (12) の解として 出てくるのであって、それを満たす $\lambda$ が

$$\lambda^{n+2}=\lambda^{n+1}+\lambda^n$$

を満たすことで $\lambda^n$ がフィボナッチ数列の解となるという 構造から (2) のような式が出てくるわけである。 このように、線形同次漸化式の解は、 基本的には (ほぼ) 等比数列の一次結合という構造になっている。