6 非同次の線形漸化式

最後に、非同次の定数係数線形漸化式

$$\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=f_n, \hspace{1zw} (n\geq 0)$$ (29)

($\{f_n\}$ は既知の数列、$\{a_n\}$ が未知の数列) についても簡単に述べておこう。

次の事実は、命題 1 と同様に容易にわかる (証明は略す)。

命題 4

非同次の漸化式 (29) の一般解は、 (29) の一つの解と、 同次の漸化式 (3) の一般解の和で表される。

これにより、(29) の一般解を求めるには、 (29) のなんらかの解 (特殊解) を一つ求めれば良いことになるが、その解法を述べるために、 次のような記法、用語を用いることにする。

まず、非同次の漸化式 (29) に対しても、 (10) を (29) の特性方程式と呼び、 (10) の左辺を (29) の 特性多項式 と呼ぶ。 逆に、最高次数の係数が 1 で、定数項が 0 でない多項式

$$F(\lambda)=\lambda^N+p_{N-1}\lambda^{N-1}+\cdots+p_0$$

を特性多項式とする漸化式 (29) の左辺を、 この多項式 $F(\lambda)$ に 付随する漸化式 と呼び、

$$D(F,a,n)=a_{n+N}+p_{N-1}a_{n+N-1}+\cdots+p_0a_n$$

のような記号で書くことにする。

命題 5

1. $\alpha\neq 0$ のとき、非同次漸化式

   $$a_{n+1}-\alpha a_n=f_n\hspace{1zw}(n\geq 0)$$ (30)

   
   の解の一つは、

   $$a_n=\sum_{k=0}^{n-1}\alpha^{n-k-1}f_k\hspace{1zw}(n\geq 1),\hspace{1zw}a_0=0$$ (31)

   
   で与えられる。
2. (29) の特性多項式 $F(\lambda)$ が、 最高次数の係数が 1 の 2 つの多項式 $G(\lambda)$, $H(\lambda)$ の積に 因数分解されるとき、 数列 $b_n$ をこの $G(\lambda)$ に付随する漸化式 $b_n=D(G,a,n)$ とすると、 $b_n$ は $H(\lambda)$ を特性多項式に持つ漸化式 $D(H,b,n)=f_n$ を満たす (すなわち $D(F,a,n)=D(H,b,n)$ が成り立つ)。

証明

1. $\alpha\neq 0$ より、(30) の $n$ を $k$ として、 その両辺を $\alpha^{k+1}$ で割れば

$$\frac{a_{k+1}}{\alpha^{k+1}}-\frac{a_k}{\alpha^k}=\frac{f_k}{\alpha^{k+1}}$$

となる。$n\geq 1$ に対してこれを $k=0$ から $k=n-1$ まで加えれば、

$$\frac{a_n}{\alpha^n}-\frac{a_0}{1} = \sum_{k=0}^{n-1}\frac{f_k}{\alpha^{k+1}}$$

となるので、$a_0=0$ とすれば (31) が得られる。

2. まず、$G$ が 1 次式のときに示す。

$$G(\lambda)=\lambda-\alpha,\hspace{1zw} H(\lambda)=\sum_{j=... ...\lambda^j,\hspace{1zw} F(\lambda)=(\lambda-\alpha)H(\lambda)$$

とすると、 $b_n=D(G,a,n)=a_{n+1}-\alpha a_n$ より

$$D(H,b,n) = \sum_{j=0}^{N-1}q_jb_{n+j} = \sum_{j=0}^{N-1}q_j(a_{n+j+1}-\alpha a_{n+j})$$

$$= %= \sum_{j=1}^{N}q_{j-1}a_{n+j}-\sum_{j=0}^{N-1}\alpha q_j a_{n+j}$$

$$= q_{N-1}a_{n+N}+\sum_{j=1}^{N-1}(q_{j-1}-\alpha q_j)a_{n+j} -\alpha q_0 a_n$$ (32)

となる。一方、

$$F(\lambda) = (\lambda-\alpha)\sum_{j=0}^{N-1}q_j\lambda^j = \sum_{j=0}^{N-1}q_j(\lambda^{j+1}-\alpha\lambda^j)$$

$$= %= \sum_{j=1}^{N}q_{j-1}\lambda^j-\sum_{j=0}^{N-1}\alpha q_j\lambda^j$$

$$= q_{N-1}\lambda^N+\sum_{j=1}^{N-1}(q_{j-1}-\alpha q_j)\lambda^j -\alpha q_0$$ (33)

となり、確かに (32) が (33) に 付随する漸化式であることがわかる。 よって (32) の右辺は $D(F,a,n)$ と書けるから

$$D(H,b,n)=D(F,a,n)=D(HG,a,n)$$ (34)

が一次式の $G$ について言えたことになる。

$G$ が 2 次以上の場合は、(34) を 繰り返し用いればよい。例えば $G$ が 2 次の場合、

$$G(\lambda)=(\lambda-\alpha)(\lambda-\beta)$$

と因数分解して $c_n=D(\lambda-\beta,a,n)=a_{n+1}-\beta a_n$ とすれば、 (34) より $b_n=D(G,a,n)$ は

$$b_n=D((\lambda-\alpha)(\lambda-\beta),a,n)=D(\lambda-\alpha,c,n)$$

となるから、再び (34) を繰り返し使うことで

$$D(H,b,n) =D((\lambda-\alpha)H,c,n) =D((\lambda-\alpha)(\lambda-\beta)H,a,n) =D(F,a,n)$$

が得られる。

ここで、命題 5 の 1. の (31) の右辺は、たたみこみ と呼ばれる次の記号

$$(P_n\ast Q_n)(j) = \left\{\begin{array}{ll} \displaystyle ... ...k=0}^j P_{j-k}Q_k & (j\geq 0),\\ 0 & (j< 0)\end{array}\right.$$

を使うと $(\alpha^n\ast f_n)(n-1)$ と書けることを注意しておく。

この命題 5 により、 非同次の漸化式 (29) の特殊解を求める問題は、 一つ項数の低い漸化式に帰着できることがわかる。

例えば特性多項式 $F(\lambda)$ が

$$F(\lambda) =(\lambda-\alpha)(\lambda^2+p\lambda+q) =\lambda^3+(p-\alpha)\lambda^2+(q-\alpha p)\lambda-\alpha q$$

の 3 次式の場合を考えてみよう。この場合、非同次の漸化式は

$$a_{n+3}+(p-\alpha)a_{n+2}+(q-\alpha p)a_{n+1}-\alpha q a_n=f_n$$ (35)

となるが、命題 5 の 2. は、

$$b_n = D(\lambda^2+p\lambda+q,a,n)=a_{n+2}+pa_{n+1}+qa_n$$ (36)

とすると、(35) の左辺が

$$D(F,a,n)=D(\lambda-\alpha,b,n)=b_{n+1}-\alpha b_n$$ (37)

となることを意味している。 なおこれは、(37) に (36) を 代入することで (35) の左辺が得られることを 直接確認することもできる。

よって、(35) は $b_n$ では

$$b_{n+1}-\alpha b_n = f_n$$

となるので、命題 5 の 1. により

$$b_n = (\alpha^n\ast f_n)(n-1)$$ (38)

がその一つの解となる。 よって、(36), (38) により

$$a_{n+2}+pa_{n+1}+qa_n = (\alpha^n\ast f_n)(n-1)$$ (39)

となり、4 項の非同次漸化式 (35) が 3 項の非同次漸化式 (39) に帰着されることになる。 同じように $\lambda^2+p\lambda+q$ を因数分解すれば 2 項の漸化式に帰着され、 最終的に $a_n$ が求まることになる。

されに今の考察から、 例えば $F(\lambda)=(\lambda-\alpha)(\lambda-\beta)$ の場合、

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

の特殊解は、

$$\begin{eqnarray*}a_n &=& (\alpha^n\ast\{(\beta^n\ast f_n)(n-1)\})(n-1) = \su... ...&=& \sum_{j=0}^{n-2}f_j\sum_{m=j}^{n-2}\alpha^{n-2-m}\beta^{m-j}\end{eqnarray*}$$

となることがわかる。 この最後の和は、 $\alpha\neq\beta$ のときは等比級数で、

$$\begin{eqnarray*}\sum_{m=j}^{n-2}\alpha^{n-2-m}\beta^{m-j} &=& \alpha^{n-2-j}+... .../\alpha)-1} = \frac{\beta^{n-1-j}-\alpha^{n-1-j}}{\beta-\alpha}\end{eqnarray*}$$

となり、$\alpha=\beta$ のときは定数和で、

$$\sum_{m=j}^{n-2}\alpha^{n-2-m}\beta^{m-j} = \sum_{m=j}^{n-2}\alpha^{n-2-j} =(n-1-j)\alpha^{n-2-j}$$

となる。 よって、(40) の 特殊解は、 $a_0=a_1=0$, $n\geq 2$ に対しては、

$$a_n=\left\{\begin{array}{ll} \displaystyle \sum_{j=0}^{n-2}... ...{n-2-j}f_j & (\mbox{$\alpha=\beta$\ のとき})\end{array}\right.$$

となる。

なお、高校の数学での漸化式の解法では、 特性方程式はむしろ本節のような使い方をするのが主のようで、例えば

$$a_{n+2}+pa_{n+1}+q a_n=0$$

の一般項を求めるのに、 特性方程式 $\lambda^2+p\lambda+q=0$ の 2 つの解 $\alpha$, $\beta$ を使って、 命題 5 の 2. のような変形を行い、

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

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

とし、 $b_n=a_{n+1}-\alpha a_n$ とおいて

$$b_{n+1}-\beta b_n=0$$

より $b_n$ を等比数列として求め、 そこから命題 5 の 1. の ような方法で $a_n$ を求めること行われているようである。

なお、 $\alpha\neq\beta$ の場合は、 (41) の $\alpha$ と $\beta$ を入れかえた

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

という変形を行うことで $c_n=a_{n+1}-\beta a_n$ とおいて $c_n$ を求めることができるから

$$a_{n+1}-\alpha a_n=b_n,\hspace{1zw} a_{n+1}-\beta a_n=c_n$$

から $a_{n+1}$ を消去して $a_n$ を求める、という方法もある。