2 定数係数線形同次漸化式

定数係数線形同次 $(N+1)$ 項漸化式とは、以下のような漸化式を言う。

$$\sum_{j=0}^{N}p_ja_{n+j} =a_{n+N}+p_{N-1}a_{n+N-1}+\cdots+p_1a_{n+1}+p_0a_n=0 \hspace{1zw} (n\geq 0)$$ (3)

ここで、$p_k$ ($0\leq k\leq N$) は定数で、$p_N=1$ とする。 また、$p_0=0$ であれば、一つずらすことで $N$ 項以下の漸化式にできるので、 ここでは

$$p_0\neq 0$$ (4)

であると仮定する。

まず、数列の線形性について述べておく。今、数列 $a_0,a_1,a_2,\ldots$ を

$$\{a_n\}_{n\geq 0} = \{a_n\}$$

のように書くことにする。このとき、 2 つの数列 $\{a_n\}$, $\{b_n\}$ の和を $\{a_n+b_n\}$ で定義でき、 また数列 $\{a_n\}$ のスカラー倍 ($\alpha$ 倍) を $\{\alpha a_n\}$ で 定義できる。これにより、数列 $\{a_n\}$ を抽象的なベクトルと見ることができ、 数列の集まりをベクトル空間 (線形空間) と考えることができる。

漸化式 (3) は、 $a_0,a_1,\ldots,a_{N-1}$ を与えれば $a_N,a_{N+1},a_{N+2},\ldots$ がこの漸化式によって順に求められていくから、 (3) を満たす数列には $N$ 個の自由度があるといえる。 これを線形代数の言葉で表現すれば次の命題 1 のようになる。 なお、以下では (3) を満たす数列のことを (3) の 解 と呼ぶことにする。

命題 1

1. (3) の解は、線形 (部分) 空間を作る (これを (3) の 解空間 と呼ぶ)。 すなわち、(3) の解である 2 つの数列の和、 および (3) の解のスカラー倍も (3) の解となる。
2. (3) の解空間の次元は丁度 $N$ である。 すなわち、$N$ 個の一次独立な数列 $\{a^{(j)}_n\}$ ( $j=0,1,\ldots,N-1$) が存在して、解空間の任意の数列 $\{a_n\}$ は、 ある定数 $\alpha_j$ ( $0\leq j\leq N-1$) を用いて

   $$a_n =\sum_{j=0}^{N-1}\alpha_j a^{(j)}_n =\alpha_0 a^{(0)}_n+\alpha_1 a^{(1)}_n+\cdots+\alpha_{N-1}a^{(N-1)}_n$$

   
   と書ける。

証明

1. $\{a_n\}$, $\{b_n\}$ が (3) の解であれば、

$$\sum_{j=0}^N p_ja_{n+j}=0,\hspace{1zw}\sum_{j=0}^N p_jb_{n+j}=0\hspace{1zw}(n\geq 0)$$

が成り立つから、任意のスカラー $\alpha$ に対して、

$$\sum_{j=0}^N p_j(a_{n+j}+b_{n+j})=0,\hspace{1zw}\sum_{j=0}^N p_j(\alpha a_{n+j})=0 \hspace{1zw}(n\geq 0)$$

となるので、$\{a_n+b_n\}$, $\{\alpha a_n\}$ も (3) の解となる。よって、それらは線形空間を作る。

2. $a_0,a_1,\ldots,a_{N-1}$ を与えれば (3) の解は 一意に決まるので、 $0\leq j\leq N-1$ に対し、

$$\left[\begin{array}{c}a_0\\ a_1\\ \vdots\\ a_{N-1}\end{arra... ...\begin{array}{c}0\\ \vdots\\ 1\\ \vdots\\ 0\end{array}\right]$$ (5)

( $\mbox{\boldmath$e$}_j$ は上から $(j+1)$ 番目の成分が 1 で、 他の成分が全部 0 の $N$ 次元ベクトル) によって決まる (3) の解を $\{a^{(j)}_n\}$ と書くことにすると、 これにより $N$ 個の解が作られることになる。 この $N$ 個の解は一次独立である。 実際、定数 $d_j$ ( $j=0,1,\ldots,N-1$) に対し、

$$\sum_{j=0}^{N-1}d_j a^{(j)}_n =d_0a^{(0)}_n+d_1a^{(1)}_n+\cdots+d_{N-1}a^{(N-1)}_n=0$$ (6)

がすべての $n\geq 0$ について成り立つとすると、 (5) により $k\leq N-1$ に対して

$$a^{(j)}_k=0\ (j\neq k),\hspace{1zw}a^{(k)}_k=1$$ (7)

が成り立つから、(6) で $n=k$ とすれば $d_k=0$ となる。 結局 $d_0$, $d_1$, ...はすべて 0 となるので、 よって $\{a^{(j)}_n\}$ ( $j=0,1,\ldots,N-1$) が一次独立であることがわかる。

また、(3) の任意の解 $\{a_n\}$ に対しても、

$$b_n=\sum_{j=0}^{N-1}a_j a^{(j)}_n =a_0a^{(0)}_n+a_1a^{(1)}_n+\cdots+a_{N-1}a^{(N-1)}_n$$ (8)

とすると、$\{b_n\}$ は $\{a^{(j)}_n\}$ の一次結合であるから 1. により (3) の解の一つであり、 $0\leq k\leq N-1$ に対しては、 (7) より $b_k=a_k$ になっているので、 $\{b_n\}=\{a_n\}$ であることがわかる。 すなわち、任意の解 $\{a_n\}$ は (8) のように $\{a^{(j)}_n\}$ の一次結合として表されることになる。

フィボナッチ数列 (1) で言えば、 (2) は $a_0=0$, $a_1=1$ の解であるから、 これは命題 1 の 2. の $\{a^{(1)}_n\}$ に当たる。もう一つの解である $\{a^{(0)}_n\}$ は、

$$\left\{\begin{array}{l} a_{n+2}=a_{n+1}+a_n\hspace{1zw}(n\geq 0),\\ a_0=1,\hspace{1zw}a_1=0\end{array}\right.$$

を満たすものとなるが、これは $a_2=a_0+a_1=1$ となるので、 $\{a^{(1)}_n\}$ を一つずらしたものであることがわかる。すなわち、

$$a^{(0)}_n = a^{(1)}_{n-1} = \frac{1}{\sqrt{5}}\left\{\le... ...\right)^{n-1} -\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right\}$$ (9)

となる。