2

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

435
0
$$\newcommand{a}[0]{\alpha} \newcommand{b}[0]{\beta} \newcommand{C}[0]{\mathbb{C}} \newcommand{d}[0]{\delta} \newcommand{dis}[0]{\displaystyle} \newcommand{e}[0]{\varepsilon} \newcommand{farc}[2]{\frac{#1}{#2}} \newcommand{G}[0]{\Gamma} \newcommand{g}[0]{\gamma} \newcommand{Gal}[0]{\operatorname{Gal}} \newcommand{id}[0]{\operatorname{id}} \newcommand{Im}[0]{\operatorname{Im}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{l}[0]{\left} \newcommand{L}[0]{\Lambda} \newcommand{la}[0]{\lambda} \newcommand{Li}[0]{\operatorname{Li}} \newcommand{li}[0]{\operatorname{li}} \newcommand{N}[0]{\mathbb{N}} \newcommand{ol}[1]{\overline{#1}} \newcommand{ord}[0]{\operatorname{ord}} \newcommand{P}[0]{\mathfrak{P}} \newcommand{p}[0]{\mathfrak{p}} \newcommand{q}[0]{\mathfrak{q}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{r}[0]{\right} \newcommand{R}[0]{\mathbb{R}} \newcommand{Re}[0]{\operatorname{Re}} \newcommand{s}[0]{\sigma} \newcommand{t}[0]{\theta} \newcommand{ul}[1]{\underline{#1}} \newcommand{vp}[0]{\varphi} \newcommand{vt}[0]{\vartheta} \newcommand{x}[0]{\boldsymbol{x}} \newcommand{Z}[0]{\mathbb{Z}} \newcommand{z}[0]{\zeta} \newcommand{ZZ}[1]{\mathbb{Z}/#1\mathbb{Z}} \newcommand{ZZt}[1]{(\mathbb{Z}/#1\mathbb{Z})^\times} $$

はじめに

 この記事では三項間漸化式
$$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$を求めれば十分となります。

$\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)$$
と解けます。

投稿日:202313
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

子葉
子葉
994
231188
主に複素解析、代数学、数論を学んでおります。 私の経験上、その証明が簡単に探しても見つからない、英語の文献を漁らないと載ってない、なんて定理の解説を主にやっていきます。 同じ経験をしている人の助けになれば。最近は自分用のノートになっている節があります。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中