この記事では三項間漸化式
$$a_{n+2}=pa_{n+1}+qa_n$$
を解くときに$a_{n+k}$を$x^k$に置き換えた方程式
$$x^2=px+q$$
が出てくることの謎について考察していきます。
私が昔漸化式の勉強をしていたときこのような話を見かけました。
三項間漸化式
$$a_{n+2}=pa_{n+1}+qa_n$$
は特性方程式
$$x^2=px+q$$
の解$x=\a,\b$を使って
$$a_n=\l\{\begin{array}{cl}A\a^n+B\b^n&(\a\neq\b)
\\(An+B)\a^n&(\a=\b)\end{array}\r.$$
と解ける。
このカラクリについては線形代数の勉強をしていたときに次のような説明を知りました。
上の三項間漸化式は
$$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}
=\begin{pmatrix}p&q\\1&0\end{pmatrix}\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix}$$
と表すことができ、右の行列の固有方程式が
$$x^2-px-q=0$$
となることからある行列$P$があって
$$P^{-1}\begin{pmatrix}p&q\\1&0\end{pmatrix}P
=\begin{pmatrix}\a&0\\0&\b\end{pmatrix},
\begin{pmatrix}\a&1\\0&\a\end{pmatrix}$$
と標準化できる。よって漸化式は
$$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}
=\begin{pmatrix}p&q\\1&0\end{pmatrix}^n\begin{pmatrix}a_2\\a_1\end{pmatrix}
=\l\{\begin{array}{c}
P\begin{pmatrix}\a^n&0\\0&\b^n\end{pmatrix}P^{-1}\begin{pmatrix}a_2\\a_1\end{pmatrix}
\\P\begin{pmatrix}\a^n&n\a^{n-1}\\0&\a^n\end{pmatrix}P^{-1}\begin{pmatrix}a_2\\a_1\end{pmatrix}
\end{array}\r.$$と解ける。
しかしこれだけだと漸化式の特性方程式と行列の固有方程式が一致することの本質的な説明がされておらず、いまいちしっくりきませんでした。
ということで「なぜ$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$を求めれば十分となります。
ここで元の漸化式に戻って
$$(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=\begin{pmatrix}p&q\\r&s\end{pmatrix}\quad(\det A=ps-qr\neq0)$$
の複素数$z$への作用を
$$Az=\frac{pz+q}{rz+s}$$
によって定めます。このときこの作用は結合的となる、つまり行列$A,B$に対して
$$A(Bz)=(AB)z$$
が成り立ちます。このことは次のように確かめられます。
ベクトル$\x=(x,y)\;(y\neq0)$に対して$f(\x)=(x/y,1)=\x/y$と定めると$f(a\x)=f(\x)$より
$$f(Af(B\x))=f(AB\x/(B\x)_2)=f(AB\x)$$
が成り立つので$\x=(z,1)$としてこの両辺の第一成分を比較することで$A(Bz)=(AB)z$を得る。
さてこれによって一次分数型の漸化式$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$$
が出てきます。
また特性方程式が異なる二解$x=x_1,x_2$を持つとき、$A$は
$$P=(-\x_1\quad\x_2)=\begin{pmatrix}-x_1&x_2\\-1&1\end{pmatrix}$$
によって
$$P^{-1}AP=\begin{pmatrix}\a&0\\0&\b\end{pmatrix}$$
と対角化されるので
$$Q=\begin{pmatrix}1&-x_2\\1&-x_1\end{pmatrix}=(\det P)P^{-1}$$
とおくと
$$Qa_{n+1}=QAQ^{-1}(Qa_n)=\frac{\a(Qa_n)+0}{0(Qa_n)+\b}=\frac\a\b (Qa_n)$$
と等比数列
$$b_n=Qa_n$$
が得られたりします。
ちなみに$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)$$
と解けます。