m項間漸化式の特性方程式はどこから出て来るのか

はじめに

　この記事では三項間漸化式
$$a_{n+2}=pa_{n+1}+qa_n$$
を解くときに$a_{n+k}$を$x^k$に置き換えた方程式
$$x^2=px+q$$
が出てくることの謎について考察していきます。

　私が昔漸化式の勉強をしていたときこのような話を見かけました。

　このカラクリについては線形代数の勉強をしていたときに次のような説明を知りました。

　しかしこれだけだと漸化式の特性方程式と行列の固有方程式が一致することの本質的な説明がされておらず、いまいちしっくりきませんでした。
　ということで「なぜ$a_{n+k}$を$x^k$に置き換えると特性方程式が出て来るのか」と言う話についてそれっぽい説明付けを考えていこうと思います。

線形代数による説明

問題の言い換え

　以下では一般の$m$項間漸化式
$$\sum^{m-1}_{k=0}c_ka_{n+k}=0\quad(c_{m-1}=1)$$
を考えることにします。
　このとき数列空間上の線形写像
\begin{eqnarray} T:\operatorname{Map}(\N_0,\C)&\to&\operatorname{Map}(\N_0,\C) \\(a_n)_n&\mapsto&\l(\sum^m_{k=0}c_ka_{n+k}\r)_n \end{eqnarray}
行列で表すと
$$T\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\end{pmatrix} =\begin{pmatrix}c_0&c_1&c_2&\cdots&c_m&0&0&\cdots \\0&c_0&c_1&\cdots&c_{m-1}&c_m&0&\cdots \\0&0&c_0&\cdots&c_{m-2}&c_{m-1}&c_m&\cdots \\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} \begin{pmatrix}a_0\\a_1\\a_2\\\vdots\end{pmatrix}$$
を考えると、上の漸化式を解く問題は$T$の核$\Ker T$を求める問題と言い換えることができます。

特性方程式

　さらに別の線形写像(シフト作用素)$S(a_n)_n=(a_{n+1})_n$を考えると$T$は
$$T=\sum^{m-1}_{k=0}c_kS^k$$
と表すことができます。これを$S$について因数分解するために特性方程式
$$\sum^{m-1}_{k=0}c_kx^k=0$$
を解く必要があります。

問題の帰着

　$T$を$S$について因数分解して
$$T=\prod^l_{k=1}(S-\a_k)^{e_k}\quad(\a_i\neq\a_j)$$
とおくと
$$\Ker T=\bigoplus^l_{k=1}\Ker(S-\a_k)^{e_k}$$
が成り立ちます。
　実際$T=f_1(S)f_2(S)\;$($f_1,f_2$は互いに素な多項式)と分解したとき、ある$g,h$があって
$$g(S)f_1(S)+h(S)f_2(S)=1$$
が成り立つので$\boldsymbol x\in\Ker T$に対して
$$\boldsymbol x=g(S)f_1(S)\boldsymbol x+h(S)f_2(S)\boldsymbol x\in\Ker f_1(S)\oplus\Ker f_2(S)$$
が成り立ちます。
　よって$\Ker T$を求めるには$\Ker(S-\a)^e$を求めれば十分となります。

$\Ker(S-\a)^e$の計算

　ここで元の漸化式に戻って
$$(S-\a)^ea_n=0$$
を考えると、左辺に$\a^{-n-e}$を掛けることで
\begin{eqnarray} 0&=&\a^{-n-e}\sum^e_{k=0}\binom ek(-\a)^{e-k}S^ka_n \\&=&\sum^e_{k=0}\binom ek(-1)^{e-k}\a^{-n-k}a_{n+k} \\&=&\sum^e_{k=0}\binom ek(-1)^{e-k}S^k(\a^{-n}a_n) \\&=&(S-1)^e(\a^{-n}a_n) \end{eqnarray}
が成り立ちます。
　いま$S-1$は差分作用素
$$\Delta a_n=a_{n+1}-a_n$$
に他ならないので望遠鏡和(和分)
$$\sum^{n-1}_{k=0}\Delta a_k=a_n-a_0$$
を繰り返すことで$\Delta^ea_n=0$からは
$$a_n-\sum^{e-1}_{k=0}\binom{n+k}k(\Delta^k a_n)_0=0$$
が得られます。
　よって$(S-\a)^ea_n=0$は
$$a_n=\a^n\sum^{e-1}_{k=0}\binom{n+k}k(\Delta^k(\a^{-n}a_n))_0$$
と解けます。
　特に$\binom{n+k}k$は$n$についての$k$次多項式であることに注意すると
$$\Ker(S-\a)^e=\{f(n)\a^n\mid \deg f< e\}$$
が成り立ちます。

おまけ

　ちなみにこれらの操作は
\begin{eqnarray} E_\a(a_n)_n&=&(\a^na_n)_n \\\Sigma(a_n)_n&=&\l(\sum^n_{k=0}a_k\r)_n \\\d(a_n)_n&=&(a_0)_n \end{eqnarray}
と定めると線形写像の演算として
\begin{eqnarray} E_{\a^{-1}}(S-\a)&=&\a\Delta E_{\a^{-1}} \\\Sigma\Delta&=&(1-\d) \\\Sigma^e\Delta^e&=&1-\sum^{e-1}_{k=0}\Sigma^k\d\Delta^k \\\Sigma^k(1)_n&=&(\binom{n+k}k)_n \end{eqnarray}
のように書けます。

まとめ

　$a_{n+k}$をシフト演算子$S^k$に置き換えて考えると
$$T=\sum^{m-1}_{k=0}c_kS^k$$
を因数分解するために特性多項式
$$\sum^{m-1}_{k=0}c_kx^k=0$$
を解く必要があり、
$$T=\prod^l_{k=1}(S-\a_k)^{e_k}$$
と因数分解することで
$$a_n=\sum^l_{k=1}f_k(n)\a_k^n\quad(\deg f_k< e_k)$$
と解くことができる。という話でした。
　これで「なぜ$a_{n+k}$を$x^k$に置き換えるのか」という謎について説明できたのではないでしょうか。
　ついでにいくつかおまけを書いておきます。
　では。

おまけ：一次分数型の漸化式

　一次分数型の漸化式
$$a_{n+1}=\frac{pa_n+q}{ra_n+s}$$
を解くときも特性方程式
$$x=\frac{px+q}{rx+s}$$
が出てきます。これについても行列によってある程度説明できます。
　その前にまずメビウス変換(一次分数変換)と行列の対応について説明します。

　さてこれによって一次分数型の漸化式$a_{n+1}=Aa_n$は
$$a_n=A^na_0$$
と解くことができます。
　よって$A$の標準化を考えればよく、$A$の固有ベクトル
$$A\x=\a\x$$
を$\x=(x,1)$として考えると
$$\begin{pmatrix}px+q\\rx+s\end{pmatrix}=\a\begin{pmatrix}x\\1\end{pmatrix}$$
なのでこの比を取ることで特性方程式
$$\frac{px+q}{rx+s}=x$$
が出てきます。

　ちなみに$a_{n+1}=Aa_n$は$A$の標準化
$$P^{-1}AP=\begin{pmatrix}\a&0\\0&\b\end{pmatrix},\begin{pmatrix}\a&1\\0&\a\end{pmatrix}$$
によって
$$a_n=\frac{a\a^n+b\b^n}{c\a^n+d\b^n},\frac{an+b}{cn+d}$$
と解けます。この$\a,\b$を求める方程式は特性方程式とは違って
$$\det(xI-A)=(x-p)(x-s)-qr=0$$
となります。

おまけ：微分方程式へのアナロジー

　今回漸化式を解いたのと同じようにして$m$階微分方程式
$$\sum^{m-1}_{k=0}c_k\frac{d^ky}{dx^k}=0$$
も解くことができます。
　ここでは関数空間$C^\infty(\C)$上の線形写像
$$L=\sum^{m-1}_{k=0}c_kD^k\quad\l(D=\frac d{dx}\r)$$
を考えます。例のごとく
$$L=\prod^l_{k=1}(D-\a_k)^{e_k}$$
と因数分解すると
$$\Ker L=\bigoplus^l_{k=1}\Ker(D-\a_k)^{e_k}$$
が成り立ちます。
　そしてライプニッツ則より
$$e^{-\a x}(D-\a)^ey =\sum^e_{k=0}\binom ek(e^{-\a x})^{(e-k)}y^{(k)} =D^e(e^{-\a x}y)$$
が成り立つので$(D-\a)^ey=0$は
$$y=f(x)e^{\a x}\quad(\deg f< e)$$
と解けます。