3項間漸化式の解法に関するメモ

数列 行列

例題：漸化式 a_{n+1}-5a_{n}+6a_{n-1}=0 の一般項を求めよ
特性方程式s^2-5s+6=0を解いて解s=2,3を求めた後に漸化式を
a_{n+1}-2a_{n}=3(a_{n}-2a_{n-1}),\,a_{n+1}-3a_{n}=2(a_{n}-3a_{n-1})
と式変形して一般項a_{n}=3^{n-1}(a_{2}-2a_{1})-2^{n-1}(a_{2}-3a_{1})を求めるのだが、最初の式変形の操作が漸化式を表す行列の左固有ベクトル(Left Eigenvector -- from Wolfram MathWorld)を掛け算する操作
(-2\, 1)\left(\begin{array}{l}a_{n}\\a_{n+1}\end{array}\right)=(-2\, 1)\left(\begin{array}{rr}0&1\\-6&5\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)=(-6\, 3)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)
(-3\, 1)\left(\begin{array}{l}a_{n}\\a_{n+1}\end{array}\right)=(-3\, 1)\left(\begin{array}{rr}0&1\\-6&5\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)=(-6\, 2)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)
になっている。すなわち固有空間へのベクトルの射影を取るために、双対なベクトル基底との内積を取る計算になっている。

追記 2009.1.28: 固有値が縮退している場合

例題：漸化式 a_{n+1}-4a_{n}+4a_{n-1}=0 の一般項を求めよ
この漸化式は行列を用いて\left(\begin{array}{l}a_{n}\\a_{n+1}\end{array}\right)=\left(\begin{array}{rr}0&1\\-4&4\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)=\left(\begin{array}{rr}0&1\\-4&4\end{array}\right)^n\left(\begin{array}{l}a_{0}\\a_{1}\end{array}\right)と書ける。この行列の一般左固有ベクトルは{}^t\vec{e}_1=(-2,1), {}^t\vec{e}_2=(1,0)であり、Jordanブロックへの変形は\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)\left(\begin{array}{rr}0&1\\-4&4\end{array}\right)=\left(\begin{array}{rr}2&1\\0&2\end{array}\right)\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)となる(途中の式だけど)。だから漸化式の両辺に行列\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)を掛け算して
\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)\left(\begin{array}{l}a_{n}\\a_{n+1}\end{array}\right)=\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)\left(\begin{array}{rr}0&1\\-4&4\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)=\left(\begin{array}{rr}2&1\\0&2\end{array}\right)\left(\begin{array}{rr}1&0\\-2&1\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}\end{array}\right)
\Longrightarrow\left(\begin{array}{l}a_{n}\\a_{n+1}-2a_{n}\end{array}\right)=\left(\begin{array}{rr}2&1\\0&2\end{array}\right)\left(\begin{array}{l}a_{n-1}\\a_{n}-2a_{n-1}\end{array}\right)=\left(\begin{array}{rr}2^n&2^{n-1}n\\0&2^n\end{array}\right)\left(\begin{array}{l}a_{0}\\a_{1}-2a_{0}\end{array}\right)
となる。これが一般項を求める式。一般右固有ベクトルの基底の向きへの射影をとる計算になっている。