n項間の漸化式#3
$4$ 項間の漸化式
\[
a_{n+3} = a_{n+2} + a_{n+1}-a_n, \quad a_1 = 0 , \ a_2 = -1 , \ a_3 = 1
\]
で定まる数列 $\{a_n\}$ の一般項を線形代数（行列）で求める．
この例では行列の対角化ができないため，Jordan 標準形を用いてべき乗を計算する．
問題提示と計算
漸化式
\[
a_{n+3} = a_{n+2} + a_{n+1}-a_n, \quad a_1 = 0 , \ a_2 = -1 , \ a_3 = 1
\]
で定められる数列 $\{a_n\} \quad (n=1,2,3,\ldots)$ の一般項を求める．
以下のノートと同じように，行列での計算を考える：
\[
\boldsymbol{x}_n = \left[
\begin{array}{c}
a_{n+2} \\
a_{n+1} \\
a_n
\end{array}
\right]
\]
で定めて，$\boldsymbol{x}_{n+1} = A \boldsymbol{x}_n$ を満たす $3$ 次正方行列 $A$ を求める
行列が対角化できればべき乗計算につなげることができるが，今回の行列 $A$ は対角化不可能である．
そこで，代わりに Jordan 標準形への分解を考える．
※ この例は $b_n = a_{n+2}-a_n$ とおけば解くことができる．
計算
$3$ 次正方行列 $A$ を求める
ベクトル $\boldsymbol{x}_n$ を
\[
\boldsymbol{x}_n = \left[
\begin{array}{c}
a_{n+2} \\
a_{n+1} \\
a_n
\end{array}
\right]
\]
とおく．
$\boldsymbol{x}_{n+1} = A \boldsymbol{x}_n$ を満たす行列 $A$ を求める．
\[
\boldsymbol{x}_{n+1} = \left[
\begin{array}{c}
a_{n+3} \\
a_{n+2} \\
a_{n+1}
\end{array}
\right]
= \left[
\begin{array}{c}
a_{n+2} + a_{n + 1}-a_n \\
a_{n+2} \\
a_{n+1}
\end{array}
\right]
= \left[
\begin{array}{ccc}
1 & 1 & -1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array}
\right] \left[
\begin{array}{c}
a_{n+2} \\
a_{n+1} \\
a_n
\end{array}
\right] = A\boldsymbol{x}_n
\]
と計算して，
\[
A = \left[
\begin{array}{ccc}
1 & 1 & -1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array}
\right]
\]
を得る．
$A^n$ を求める
固有値を求める．
\[
\varphi_A(x) = |xE-A| = \left|
\begin{array}{ccc}
x-1 & -1 & 1 \\
-1 & x & 0 \\
0 & -1 & x
\end{array}
\right|
= x^3-x^2-x+1 = (x+1)(x-1)^2
\]
より，固有値は $-1$（重複度 $1$） と $1$（重複度 $2$）である．
Jordan 標準形 $J$ を決定するために各固有値に対する固有空間の次元を調べる．
固有値 $1$ に関して，
\[
A-1 \cdot E = \left[
\begin{array}{ccc}
0 & 1 & -1 \\
1 & -1 & 0 \\
0 & 1 & -1
\end{array}
\right] \xrightarrow{\text{行基本変形}}
\left[
\begin{array}{ccc}
1 & 0 & -1 \\
0 & 1 & -1 \\
0 & 0 & 0
\end{array}
\right]
\]
より，${\rm rank}(A-1 \cdot E) = 2$ であるから，固有値 $1$ に対する Jordan 細胞は $3-2 = 1$ より１つ．また，固有値 $1$ に対する固有空間の基底として $\left[
\begin{array}{c}
1 \\
1 \\
1
\end{array}
\right]$ が選べる．
固有値 $-1$ に関して，
\[
A-(-1) \cdot E = \left[
\begin{array}{ccc}
2 & 1 & -1 \\
1 & 1 & 0 \\
0 & 1 & 1
\end{array}
\right] \xrightarrow{\text{行基本変形}}
\left[
\begin{array}{ccc}
1 & 0 & -1 \\
0 & 1 & 1 \\
0 & 0 & 0
\end{array}
\right]
\]
より，${\rm rank}(A-(-1) \cdot E) = 2$ であるから，固有値 $-1$ に対するジョルダン細胞は $3-2 = 1$ より１つ．また，固有値 $-1$ に対する固有空間の基底として $\left[
\begin{array}{c}
1 \\
-1 \\
1
\end{array}
\right]$ が選べる．
したがって $A$ の Jordan 標準形 $J$ は
\[
J = J(1,2) \oplus J(-1,1) = \left[
\begin{array}{ccc}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & -1
\end{array}
\right]
\]
と決定できる．
正則行列 $P$ を求める．$J = P^{-1}AP$ より $AP = PJ$ である．$P = [\boldsymbol{p}_1 ~ \boldsymbol{p}_2 ~ \boldsymbol{p}_3]$ とおくと，
\[
\left\{
\begin{array}{lcrcrcr}
A\boldsymbol{p}_1 & = & 1 \cdot \boldsymbol{p}_1 & + & 0 \cdot \boldsymbol{p}_2 & + & 0 \cdot \boldsymbol{p}_3 \\
A\boldsymbol{p}_2 & = & 1 \cdot \boldsymbol{p}_1 & + & 1 \cdot \boldsymbol{p}_2 & + & 0 \cdot \boldsymbol{p}_3 \\
A\boldsymbol{p}_3 & = & 0 \cdot \boldsymbol{p}_1 & + & 0 \cdot \boldsymbol{p}_2 & + & -1 \cdot \boldsymbol{p}_3
\end{array}
\right.
\]
が成り立つ．１つ目の式より $A \boldsymbol{p}_1 = \boldsymbol{p}_1$ であるが，これは $\boldsymbol{p}_1$ が 固有値 $1$ に対する $A$ の固有ベクトルであることを表すから，先に求めた固有空間の基底を採用して
$\boldsymbol{p}_1 = \left[
\begin{array}{c}
1 \\
1 \\
1
\end{array}
\right]$
としてよい．２つ目の式の $\boldsymbol{p}_2$ を左辺に移項して整理すると $(A-E)\boldsymbol{p}_2 = \boldsymbol{p}_1$ であるから，$\boldsymbol{p}_2 = \left[
\begin{array}{c}
x \\
y \\
z \\
\end{array}
\right]$ とおいて
\[
\left[
\begin{array}{ccc}
0 & 1 & -1 \\
1 & -1 & 0 \\
0 & 1 & -1
\end{array}
\right]\left[
\begin{array}{c}
x \\
y \\
z
\end{array}
\right] = \left[
\begin{array}{c}
1 \\
1 \\
1 \\
\end{array}
\right]
\]
を満たす $x , \ y, \ z$ を１つ求めればよい．
例えば，$\boldsymbol{p}_2 = \left[
\begin{array}{c}
1 \\
0 \\
-1
\end{array}
\right]$ が選べる．３つ目の式は $\boldsymbol{p}_3$ が 固有値 $-1$ に対する $A$ の固有ベクトルであることを表すから，先に求めた基底を採用して，$\boldsymbol{p}_3 = \left[
\begin{array}{c}
1 \\
-1 \\
1
\end{array}
\right]$ としてよい．以上より，求める正則行列 $P$ は
\[
P = \left[
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 0 & -1 \\
1 & -1 & 1
\end{array}
\right]
\]
である．
$A^n = (P J P^{-1})^n = (P J P^{-1})(P J P^{-1}) \cdots (P J P^{-1}) = PJ^nP^{-1}$ である．Jordan 細胞の $n$ 乗の公式と掃き出し法の計算により
\[
J^n = \left[
\begin{array}{ccc}
1^n & n \cdot 1^{n-1} & 0 \\
0 & 1^n & 0 \\
0 & 0 & (-1)^n
\end{array}
\right] = \left[
\begin{array}{ccc}
1 & n & 0 \\
0 & 1 & 0 \\
0 & 0 & (-1)^n
\end{array}
\right], \quad
P^{-1} = \frac{1}{4}\left[
\begin{array}{ccc}
1 & 2 & 1 \\
2 & 0 & -2 \\
1 & -2 & 1
\end{array}
\right]
\]
であるから，
\[
A^{n} = PJ^nP^{-1} = \frac{1}{4}\left[
\begin{array}{lrl}
2n + 3 + (-1)^{n+2} & 2 + 2(-1)^{n+3} & -2n-1 + (-1)^{n+2} \\
2n + 1 + (-1)^{n+1} & 2 + 2(-1)^{n+2} & -2n + 1 + (-1)^{n+1} \\
2n-1 + (-1)^n & 2 + 2(-1)^{n+1} & -2n + 3 + (-1)^n
\end{array}
\right]
\]
を得る．
$\{a_n\}$ の一般項を求める
$\boldsymbol{x}_n = A^{n-1}\boldsymbol{x}_1$ が成り立つことを利用すれば，この右辺を実際に計算して
\[
a_n = \frac{2(n-1) + 3\{(-1)^{n-1}-1\}}{4}
\]
が求められる．
このノートの内容は次のPDFでも見られる：
rrQ2_ans.pdf
20200202 PDFの内容をノートに書き下した