漸化式を行列で解く
シルヴェスターの公式
$m$次正方行列$A\in \mathbb{C}^{m \times m}$の相異なる固有値を$\lambda_{1},\ldots,\lambda_{k} \in \mathbb{C}$とする．このとき，$A$が対角化可能ならば，任意の多項式$f \in \mathbb{C}[x]$に対して
$$
f(A) = \sum_{i=1}^{k} f(\lambda_{i}) \prod_{j\neq i} \frac{A-\lambda_{j}E}{\lambda_{i}-\lambda_{j}}$$
が成り立つ．
- $\deg{f} \leq k-1$としてよい：実際，仮定より$A$の最小多項式は$(x-\lambda_{1})\cdots(x-\lambda_{k}) \eqqcolon \varphi$なので（cf. satake p.139），$f$を$\varphi$で割った余りを$g$とすると
$$ f(A)=g(A),\ \forall\,i\in\{1,\ldots,k\},\ f(\lambda_{i}) = g(\lambda_{i})$$
が成り立つ． - 各$i\in\{1,\ldots,k\}$に対して
$$ L_{i}(x) \coloneqq \prod_{j\neq i} \frac{x-\lambda_{j}}{\lambda_{i}-\lambda_{j}} \in \mathbb{C}[x]$$
とおき，多項式$p\in\mathbb{C}[x]$を
$$ p(x) \coloneqq \sum_{i=1}^{k} f(\lambda_{i})L_{i}(x)$$
で定める．このとき，$\deg{p} \leq k-1$であり
$$ \forall\,j\in\{1,\ldots,k\},\ p(\lambda_{j}) = \sum_{i=1}^{k} f(\lambda_{i})\delta_{ij} = f(\lambda_{j})$$
が成り立つので，$p=f$である．よって
$$ f(A) = p(A) = \sum_{i=1}^{k} f(\lambda_{i}) \prod_{j\neq i} \frac{A-\lambda_{j}E}{\lambda_{i}-\lambda_{j}}$$
となる．
行列$A\in\mathbb{C}^{2 \times 2}$の固有値$\lambda,\mu \in \mathbb{C}$が相異なるとき，$A$の冪乗は
$$
A^{n} = \lambda^{n}\frac{A-\mu E}{\lambda-\mu} + \mu^{n}\frac{A-\lambda E}{\mu-\lambda} = \frac{\mu^{n}-\lambda^{n}}{\mu-\lambda}A - \frac{\mu^{n}\lambda-\mu\lambda^{n}}{\mu-\lambda}E$$
で与えられる．
行列$A\in\mathbb{C}^{2 \times 2}$の固有値$\lambda,\mu\in\mathbb{C}$が相等しいとき，$A$の冪乗は
$$
A^{n} = n\lambda^{n-1}A - (n-1)\lambda^{n}E$$
で与えられる．
- Base：明らか．
- Induction：ケーリー・ハミルトンの定理より
$$ A^{2} = 2\lambda A - \lambda^{2}E$$
であるから，
\begin{align} A^{n+1} &= (n\lambda^{n-1}A - (n-1)\lambda^{n}E)A \\ &= n\lambda^{n-1}A^{2} - (n-1)\lambda^{n}A \\ &= 2n\lambda^{n}A - n\lambda^{n+1}E - (n-1)\lambda^{n}A \\ &= (n+1)\lambda^{(n+1)-1}A - ((n+1)-1)\lambda^{n+1}E \end{align}
が成り立つ．
上式は
$$
\frac{\mu^{n}-\lambda^{n}}{\mu-\lambda}A - \frac{\mu^{n-1}-\lambda^{n-1}}{\mu-\lambda}\lambda\mu E$$
において$\mu \to \lambda$としたものに等しい．
漸化式を解く
2項間漸化式
$$ a_{n+1}=ra_{n}+s,\ r \neq 1.$$
定数列$b\coloneqq(\frac{s}{1-r})_{n}$は与えられた漸化式を満たすので，
$$
a_{n+1}-b_{n+1} = r(a_{n}-b_{n}) \quad\leadsto\quad a_{n}-b_{n} = r^{n}(a_{0}-b_{0})$$
より
$$
a_{n} = \left(a_{0}-\frac{s}{1-r}\right)r^{n} +\frac{s}{1-r}$$
となる．
$$
\begin{bmatrix}
a_{n+1} \\ 1
\end{bmatrix} = \underbrace{\begin{bmatrix}
r & s \\ 0 & 1
\end{bmatrix}}_{\eqqcolon A} \begin{bmatrix}
a_{n} \\ 1
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
a_{n} \\ 1
\end{bmatrix} = A^{n}\begin{bmatrix}
a_{0} \\ 1
\end{bmatrix}$$
であるから，$A^{n}$（の第1行）を求めればよい．
- $A$の固有多項式は
$$ |xE-A| = (x-r)(x-1)$$
であるから，pow-distにより
$$ A^{n} = \frac{1^{n}-r^{n}}{1-r}A - \frac{1^{n}\cdot r-1\cdot r^{n}}{1-r}E = \begin{bmatrix} r^{n} & \frac{1-r^{n}}{1-r}s \\ \ast & \ast \\ \end{bmatrix}$$
となる．よって
$$ a_{n} = r^{n}a_{0}+\frac{1-r^{n}}{1-r}s = \left(a_{0}-\frac{s}{1-r}\right)r^{n} +\frac{s}{1-r}$$
を得る． - ケーリー・ハミルトンの定理より
$$ O = A^{2}-(r+1)A+rE = (A-rE)(A-1E)=(A-1E)(A-rE)$$
であり
$$ A-1E = \begin{bmatrix} r-1 & s \\ 0 & 0 \end{bmatrix},\ A-rE = \begin{bmatrix} 0 & s \\ 0 & 1-r \end{bmatrix}$$
であるから，
$$ P \coloneqq \begin{bmatrix} 1 & s \\ 0 & 1-r \end{bmatrix} \quad\leadsto\quad P^{-1}AP = \begin{bmatrix} r & 0 \\ 0 & 1 \end{bmatrix}$$
より
$$ A^{n} = \begin{bmatrix} 1 & s \\ 0 & 1-r \end{bmatrix}\begin{bmatrix} r^{n} & 0 \\ 0 & 1^{n} \end{bmatrix}\begin{bmatrix} 1 & \frac{-s}{1-r} \\ 0 & \frac{1}{1-r} \end{bmatrix} = \begin{bmatrix} r^{n} & s \\ \ast & \ast \end{bmatrix}\begin{bmatrix} 1 & \frac{-s}{1-r} \\ 0 & \frac{1}{1-r} \end{bmatrix} = \begin{bmatrix} r^{n} & \frac{1-r^{n}}{1-r}s \\ \ast & \ast \\ \end{bmatrix}$$
となる．よって
$$ a_{n} = r^{n}a_{0}+\frac{1-r^{n}}{1-r}s = \left(a_{0}-\frac{s}{1-r}\right)r^{n} +\frac{s}{1-r}$$
を得る．
3項間漸化式：その1
$$ a_{n+2} - 5a_{n+1} +6a_{n} = 0.$$
$$
a_{n+2} - (2+3)a_{n+1} + (2\cdot 3)a_{n} = 0$$
より
$$
\begin{dcases}
a_{n+2}-2a_{n+1} = 3(a_{n+1}-2a_{n}) \\[3pt]
a_{n+2}-3a_{n+1} = 2(a_{n+1}-3a_{n})
\end{dcases} \quad\leadsto\quad \begin{dcases}
a_{n+1}-2a_{n} = 3^{n}(a_{1}-2a_{0}) \\
a_{n+1}-3a_{n} = 2^{n}(a_{1}-3a_{0})
\end{dcases}$$
となるので，$a_{n+1}$を消去して
$$
a_{n} = (a_{n+1}-2a_{n}) - (a_{n+1}-3a_{n}) = (3a_{0}-a_{1})2^{n} + (a_{1}-2a_{0})3^{n}$$
を得る．
$$
\begin{bmatrix}
a_{n+1} \\ a_{n+2}
\end{bmatrix} = \underbrace{\begin{bmatrix}
0 & 1 \\ -6 & 5
\end{bmatrix}}_{\eqqcolon A} \begin{bmatrix}
a_{n} \\ a_{n+1}
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
a_{n} \\ a_{n+1}
\end{bmatrix} = A^{n} \begin{bmatrix}
a_{0} \\ a_{1}
\end{bmatrix}$$
であるから，$A^{n}$（の第1行）を求めればよい．
- $A$の固有多項式は
$$ |xE-A| = x(x-5)+6 = x^{2} -5x +6 = (x-2)(x-3)$$
であるから，pow-distにより
$$ A^{n} = \frac{3^{n}-2^{n}}{3-2}A - \frac{3^{n}\cdot 2-3\cdot 2^{n}}{3-2}E = \begin{bmatrix} 3\cdot 2^{n}-2\cdot 3^{n} & 3^{n}-2^{n} \\ \ast & \ast \\ \end{bmatrix}$$
となる．よって
$$ a_{n} = (3\cdot 2^{n}-2 \cdot 3^{n})a_{0} + (3^{n}-2^{n})a_{1} = (3a_{0}-a_{1})2^{n} + (a_{1}-2a_{0})3^{n}$$
を得る． - ケーリー・ハミルトンの定理より
$$ O = A^{2}-5A+6E = (A-2E)(A-3E)=(A-3E)(A-2E)$$
であり
$$ A-3E = \begin{bmatrix} -3 & 1 \\ -6 & 2 \end{bmatrix},\ A-2E = \begin{bmatrix} -2 & 1 \\ -6 & 3 \end{bmatrix}$$
であるから，
$$ P \coloneqq \begin{bmatrix} 1 & 1 \\ 2 & 3 \end{bmatrix} \quad\leadsto\quad P^{-1}AP = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}$$
より
$$ A^{n} = \begin{bmatrix} 1 & 1 \\ 2 & 3 \end{bmatrix}\begin{bmatrix} 2^{n} & 0 \\ 0 & 3^{n} \end{bmatrix}\begin{bmatrix} 3 & -1 \\ -2 & 1 \end{bmatrix} = \begin{bmatrix} 2^{n} & 3^{n} \\ \ast & \ast \end{bmatrix}\begin{bmatrix} 3 & -1 \\ -2 & 1 \end{bmatrix} = \begin{bmatrix} 3\cdot 2^{n}-2\cdot 3^{n} & 3^{n}-2^{n} \\ \ast & \ast \\ \end{bmatrix}$$
となる．よって
$$ a_{n} = (3\cdot 2^{n}-2 \cdot 3^{n})a_{0} + (3^{n}-2^{n})a_{1} = (3a_{0}-a_{1})2^{n} + (a_{1}-2a_{0})3^{n}$$
を得る．
- 行列$A$は多項式$6-5x+x^{2}$の同伴行列（の転置）である（cf. comp）．
- 行列$A$の固有値を$\lambda,\mu$とすると
$$ A = \begin{bmatrix} 0 & 1 \\ -\lambda\mu & \lambda+\mu \end{bmatrix} \quad\leadsto\quad O=(A-\lambda E)(A-\mu E) = (A-\lambda E)\begin{bmatrix} -\mu & 1 \\ -\lambda\mu & \lambda \end{bmatrix}$$
となるので，
$$ \begin{bmatrix} 1 \\ \lambda \end{bmatrix} \in \Ker(A-\lambda E)$$
が成り立つ．
$T \colon \mathbb{C}^{\mathbb{N}} \to \mathbb{C}^{\mathbb{N}}$を移動演算子とする：
$$
(Ta)_{n} \coloneqq a_{n+1}.$$
このとき，与えられた漸化式は
$$
(T^{2}-5T+6\id)a=0$$
と表わせる．ところで，
$$
T^{2}-5T+6\id = (T-3\id)(T-2\id) = (T-2\id)(T-3\id)$$
より$(2^{n})_{n},\,(3^{n})_{n}$は与えられた漸化式を満たす数列であり，
$$
\Ker(T^{2}-5T+6\id) \cong \mathbb{C}^{2};\ a \mapsto \begin{bmatrix}
a_{0} \\ a_{1}
\end{bmatrix},\ \begin{vmatrix}
2^{0} & 3^{0} \\ 2^{1} & 3^{1}
\end{vmatrix} = 1 \neq 0$$
が成り立つことから，適当な$\alpha,\beta \in \mathbb{C}$を用いて
$$
a_{n} = \alpha 2^{n} + \beta 3^{n}$$
と表わせる（cf.
Casoratian
）．よって，$n=0,1$として
$$
\begin{dcases}
a_{0} = \alpha+\beta \\
a_{1} = 2\alpha+3\beta
\end{dcases} \quad\leadsto\quad \begin{dcases}
\alpha = 3a_{0}-a_{1} \\
\beta = - 2a_{0}+a_{1}
\end{dcases}$$
を得るので，
$$
a_{n} = (3a_{0}-a_{1})2^{n} + (a_{1}-2a_{0})3^{n}$$
となる．
$\mathbb{C}^{2}$の標準基底ベクトルに対応する数列を$e^{0},e^{1} \in \Ker(T^{2}-5T+6\id) \eqqcolon V$とおく：
$$
e^{0} = (1,0,-6,\cdots),\ e^{1} = (0,1,5,\cdots).$$
このとき，線型変換$T \colon V \to V$の，基底$e\coloneqq(e^{0},e^{1})$に関する表現行列$[Te/e]$は$A$に等しい：
$$
Te^{0} = -6e^{1},\ Te^{1} = e^{0}+5e^{1} \quad\leadsto\quad \left[\frac{Te}{e}\right] = \begin{bmatrix}
0 & 1 \\ -6 & 5
\end{bmatrix} = A.$$
また，基底$e$から基底$e' \coloneqq ((2^{n})_{n},(3^{n})_{n})$への基底変換行列は$P$に等しい：
$$
((1,2,\ldots),(1,3,\ldots)) = ((1,0,\ldots),(0,1,\ldots))\begin{bmatrix}
1 & 1 \\ 2 & 3
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
\alpha \\ \beta
\end{bmatrix} = P^{-1}\begin{bmatrix}
a_{0} \\ a_{1}
\end{bmatrix}.$$
したがって，以下の図式は可換である：
$$
\xymatrix{
{\mathbb{C}^{2}} \ar[rrrr]^{P^{-1}AP=\begin{bmatrix}
\lambda & 0 \\ 0 & \mu
\end{bmatrix}} \ar[rdd]_{e'}^{\cong} \ar[dddd]_{\phantom{=\begin{bmatrix}
\lambda^{0} & \mu^{0} \\ \lambda^{1} & \mu^{1}
\end{bmatrix}=}P} &&&& {\mathbb{C}^{2}} \ar[ddl]^{e'}_{\cong} \ar[dddd]^{P=\begin{bmatrix}
\lambda^{0} & \mu^{0} \\ \lambda^{1} & \mu^{1}
\end{bmatrix}} \\ \\
&{V} \ar[rr]^{T} && {V} & \\ \\
{\mathbb{C}^{2}} \ar[rrrr]_{A=\begin{bmatrix}
0 & 1 \\ -\lambda\mu & \lambda+\mu
\end{bmatrix}} \ar[ruu]^{e}_{\cong} &&&& {\mathbb{C}^{2}} \ar[uul]_{e}^{\cong}
}$$
3項間漸化式：その2
$$ a_{n+2}-6a_{n+1}+9a_{n}=0.$$
$$
a_{n+2} - (3+3)a_{n+1} + (3\cdot 3)a_{n} = 0$$
より
$$
a_{n+2}-3a_{n+1}=3(a_{n+1}-3a_{n}) \quad\leadsto\quad a_{n+1}-3a_{n} = 3^{n}(a_{1}-3a_{0})$$
となる．よって，
$$
\frac{a_{n+1}}{3^{n+1}} - \frac{a_{n}}{3^{n}} = \frac{a_{1}-3a_{0}}{3}$$
より
$$
\frac{a_{n}}{3^{n}} - \frac{a_{0}}{3^{0}} = \sum_{k=0}^{n-1} \left(\frac{a_{k+1}}{3^{k+1}} - \frac{a_{k}}{3^{k}} \right) = \sum_{k=0}^{n-1} \frac{a_{1}-3a_{0}}{3} = \frac{a_{1}-3a_{0}}{3}n$$
となるので，
$$
a_{n} = a_{0}3^{n} + (a_{1}-3a_{0})n3^{n-1}$$
を得る．
$$
\begin{bmatrix}
a_{n+1} \\ a_{n+2}
\end{bmatrix} = \underbrace{\begin{bmatrix}
0 & 1 \\ -9 & 6
\end{bmatrix}}_{\eqqcolon A} \begin{bmatrix}
a_{n} \\ a_{n+1}
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
a_{n} \\ a_{n+1}
\end{bmatrix} = A^{n} \begin{bmatrix}
a_{0} \\ a_{1}
\end{bmatrix}$$
であるから，$A^{n}$（の第1行）を求めればよい．
- $A$の固有多項式は
$$ |xE-A| = 9-6x+x^{2} = (x-3)^{2}$$
であるから，pow-doubleにより
$$ A^{n} = n3^{n-1}A - (n-1)3^{n}E = \begin{bmatrix} (1-n)3^{n} & n3^{n-1} \\ \ast & \ast \end{bmatrix}$$
となる．よって
$$ a_{n} = (1-n)3^{n}a_{0} + n3^{n-1}a_{1} = a_{0}3^{n} + (a_{1}-3a_{0})n3^{n-1}$$
を得る． - ケーリー・ハミルトンの定理より
$$ O = A^{2}-6A+9E = (A-3E)^{2}$$
であり
$$ A-3E = \begin{bmatrix} -3 & 1 \\ -9 & 3 \end{bmatrix},\ (A-3E)\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$$
であるから，
$$ P \coloneqq \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \quad\leadsto\quad P^{-1}AP = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$$
より
$$ A^{n} = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}\begin{bmatrix} 3^{n} & n3^{n-1} \\ 0 & 3^{n} \end{bmatrix}\begin{bmatrix} 1 & 0 \\ -3 & 1 \end{bmatrix} = \begin{bmatrix} 3^{n} & n3^{n-1} \\ \ast & \ast \end{bmatrix}\begin{bmatrix} 1 & 0 \\ -3 & 1 \end{bmatrix} = \begin{bmatrix} 3^{n} - n3^{n} & n3^{n-1}\\ \ast & \ast \end{bmatrix}$$
となる．よって
$$ a_{n} = (3^{n} - n3^{n})a_{0} + n3^{n-1}\cdot a_{1} = a_{0}3^{n} + (a_{1}-3a_{0})n3^{n-1}$$
を得る．
$$
T^{2}-6T+9\id = (T-3\id)^{2}$$
であるから，数列$(3^{n})_{n}$は漸化式を満たす．また，
$$
(n+1)3^{n+1} - 3 \cdot n3^{n} = 3^{n+1}$$
より$(n3^{n})_{n} \in \Ker(T-3\id)^{2}$であり，
$$
\begin{vmatrix}
3^{0} & 0 \cdot 3^{0} \\ 3^{1} & 1\cdot 3^{1}
\end{vmatrix} = 3 \neq 0$$
が成り立つことから，適当な$\alpha,\beta \in \mathbb{C}$を用いて
$$
a_{n} = \alpha 3^{n} + \beta n3^{n}$$
と表わせる．よって，$n=0,1$として
$$
\begin{dcases}
a_{0} = \alpha \\
a_{1} = 3\alpha+3\beta
\end{dcases} \quad\leadsto\quad \begin{dcases}
\alpha = a_{0} \\
\beta = \frac{a_{1}-3a_{0}}{3}
\end{dcases}$$
を得るので，
$$
a_{n} = a_{0}3^{n} + (a_{1}-3a_{0})n3^{n-1}$$
となる．
4項間漸化式
$$ a_{n+3}-6a_{n+2}+11a_{n+1}-6a_{n}=0.$$
$$
a_{n+3} - (1+2+3)a_{n+2} + (2 \cdot 3 + 3 \cdot 1 + 1 \cdot 2)a_{n+1} - (1 \cdot 2 \cdot 3)a_{n} = 0$$
より
$$
\begin{dcases}
a_{n+3}-(2+3)a_{n+2}+(2 \cdot 3)a_{n+1} = 1(a_{n+2}-(2+3)a_{n+1}+(2 \cdot 3)a_{n}) \\[3pt]
a_{n+3}-(3+1)a_{n+2}+(3 \cdot 1)a_{n+1} = 2(a_{n+2}-(3+1)a_{n+1}+(3 \cdot 1)a_{n}) \\[3pt]
a_{n+3}-(1+2)a_{n+2}+(1 \cdot 2)a_{n+1} = 3(a_{n+2}-(1+2)a_{n+1}+(1 \cdot 2)a_{n})
\end{dcases}$$
となるので，
$$
\begin{dcases}
a_{n+2}-5a_{n+1}+6a_{n} = 1^{n}(a_{2}-5a_{1}+6a_{0}) \\[3pt]
a_{n+2}-4a_{n+1}+3a_{n} = 2^{n}(a_{2}-4a_{1}+3a_{0}) \\[3pt]
a_{n+2}-3a_{n+1}+2a_{n} = 3^{n}(a_{2}-3a_{1}+2a_{0})
\end{dcases}$$
を得，したがって
$$
\begin{dcases}
a_{n+1}-3a_{n} = 2^{n}(a_{2}-4a_{1}+3a_{0})-(a_{2}-5a_{1}+6a_{0}) \\[3pt]
2a_{n+1}-4a_{n} = 3^{n}(a_{2}-3a_{1}+2a_{0})-(a_{2}-5a_{1}+6a_{0})
\end{dcases}$$
を得る．よって
$$
a_{n} = \frac{6a_{0}-5a_{1}+a_{2}}{2}-(3a_{0}-4a_{1}+a_{2})2^{n}+\frac{2a_{0}-3a_{1}+a_{2}}{2}3^{n}$$
となる．
$$
\begin{bmatrix}
a_{n+1} \\ a_{n+2} \\ a_{n+3}
\end{bmatrix} = \underbrace{\begin{bmatrix}
0 & 1 & 0 \\ 0 & 0 & 1 \\ 6 & -11 & 6
\end{bmatrix}}_{\eqqcolon A} \begin{bmatrix}
a_{n} \\ a_{n+1} \\ a_{n+2}
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
a_{n} \\ a_{n+1} \\ a_{n+2}
\end{bmatrix} = A^{n} \begin{bmatrix}
a_{0} \\ a_{1} \\ a_{2}
\end{bmatrix}$$
であるから，$A^{n}$（の第1行）を求めればよい．$A$の固有多項式は
$$
|xE-A| = -6+11x-6x^{2}+x^{3} = (x-1)(x-2)(x-3)$$
であり
$$
A^{2} = \begin{bmatrix}
0 & 0 & 1 \\ \ast & \ast & \ast \\ \ast & \ast & \ast
\end{bmatrix}$$
であるから，sylvより
\begin{align}
A^{n}
&= 1^{n}\frac{A-2E}{1-2}\frac{A-3E}{1-3} + 2^{n}\frac{A-3E}{2-3}\frac{A-1E}{2-1} + 3^{n}\frac{A-1E}{3-1}\frac{A-2E}{3-2} \\
&= \frac{1}{2}(A^{2}-5A+6E) -2^{n}(A^{2}-4A+3E) +\frac{3^{n}}{2}(A^{2}-3A+2E) \\
&= (3-3\cdot 2^{n}+3^{n})E - \left(\frac{5}{2}-2^{n+2}+\frac{3^{n+1}}{2}\right)A + \left(\frac{1}{2}-2^{n}+\frac{3^{n}}{2}\right)A^{2}\\
&= \begin{bmatrix}
3-3 \cdot 2^{n} + 3^{n} & -\frac{5}{2}+2^{n+2}-\frac{3^{n+1}}{2} & \frac{1}{2}-2^{n}+\frac{3^{n}}{2} \\
\ast & \ast & \ast \\ \ast & \ast & \ast
\end{bmatrix}
\end{align}
となる．よって
\begin{align}
a_{n}
&= (3-3\cdot 2^{n}+3^{n})a_{0} - \left(\frac{5}{2}-2^{n+2}+\frac{3^{n+1}}{2}\right)a_{1} + \left(\frac{1}{2}-2^{n}+\frac{3^{n}}{2}\right)a_{2}\\
&= \frac{6a_{0}-5a_{1}+a_{2}}{2}-(3a_{0}-4a_{1}+a_{2})2^{n}+\frac{2a_{0}-3a_{1}+a_{2}}{2}3^{n}
\end{align}
を得る．
$$
T^{3}-6T^{2}+11T-6\id = (T-1\id)(T-2\id)(T-3\id)$$
より$(1^{n})_{n},\,(2^{n})_{n},\,(3^{n})_{n}$は与えられた漸化式を満たす数列であり，
$$
\begin{vmatrix}
1^{0} & 2^{0} & 3^{0} \\ 1^{1} & 2^{1} & 3^{1} \\ 1^{2} & 2^{2} & 3^{2}
\end{vmatrix} = (2-1)(3-1)(3-2) = 2 \neq 0$$
が成り立つことから，適当な$\alpha,\beta,\gamma \in \mathbb{C}$を用いて
$$
a_{n} = \alpha 1^{n} + \beta 2^{n} + \gamma 3^{n}$$
と表わせる．よって，$n=0,1,2$として
$$
\begin{dcases}
a_{0} = \alpha+\beta+\gamma \\
a_{1} = \alpha+2\beta+3\gamma \\
a_{2} = \alpha+4\beta+9\gamma
\end{dcases} \quad\leadsto\quad \begin{bmatrix}
\alpha \\ \beta \\ \gamma
\end{bmatrix} = \begin{bmatrix}
1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9
\end{bmatrix}^{-1} \begin{bmatrix}
a_{0} \\ a_{1} \\ a_{2}
\end{bmatrix} = \frac{1}{2}\begin{bmatrix}
6 & -5 & 1 \\ -6 & 8 & -2 \\ 2 & -3 & 1
\end{bmatrix} \begin{bmatrix}
a_{0} \\ a_{1} \\ a_{2}
\end{bmatrix}$$
を得るので，
$$
a_{n} = \frac{6a_{0}-5a_{1}+a_{2}}{2}-(3a_{0}-4a_{1}+a_{2})2^{n}+\frac{2a_{0}-3a_{1}+a_{2}}{2}3^{n}$$
となる．
$$ \underbrace{\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 6 & -11 & 6 \end{bmatrix}}_{A}\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}.$$
一般に，多項式$c_{0}+c_{1}x+\cdots+c_{n-1}x^{n-1}+x^{n}$の同伴行列（の転置）
$$
A \coloneqq \begin{bmatrix}
0 & 1 && \\
& \ddots & \ddots & \\
&& 0 & 1 \\
-c_{0} & -c_{1} & \cdots & -c_{n-1}
\end{bmatrix}$$
の固有値$\lambda$に対して
$$
A\begin{bmatrix}
1 \\ \lambda \\ \vdots \\ \lambda^{n-1}
\end{bmatrix} = \begin{bmatrix}
\lambda \\ \lambda^{2} \\ \vdots \\ \lambda^{n-1} \\ -c_{0}-c_{1}\lambda -\cdots- c_{n-1}\lambda^{n-1}
\end{bmatrix} = \lambda\begin{bmatrix}
1 \\ \lambda \\ \vdots \\ \lambda^{n-1}
\end{bmatrix}$$
が成り立つ．
連立漸化式
$$ \begin{dcases} a_{n+1} = 2a_{n}-b_{n}, \\ b_{n+1} = a_{n} + 4b_{n}. \end{dcases}$$
- $b$を消去すると
$$ a_{n+2}=2a_{n+1}-(a_{n}+4(2a_{n}-a_{n+1})) = 6a_{n+1}-9a_{n}$$
より
$$ a_{n} = a_{0}3^{n} + (a_{1}-3a_{0})n3^{n-1}$$
となるので，$a_{1}=2a_{0}-b_{0}$と合わせて
\begin{align} b_{n} &= 2a_{n}-a_{n+1}\\ &= 2(a_{0}3^{n}+(a_{1}-3a_{0})n3^{n-1}) - (a_{0}3^{n+1}+(a_{1}-3a_{0})(n+1)3^{n}) \\ &= (2a_{0}-a_{1})3^{n}+(3a_{0}-a_{1})n3^{n-1} \\ &= b_{0}3^{n} + (a_{0}+b_{0})n3^{n-1} \end{align}
を得る． - 辺々足すと
$$ a_{n+1}+b_{n+1} = 3(a_{n}+b_{n}) \quad\leadsto\quad a_{n}+b_{n} = 3^{n}(a_{0}+b_{0})$$
より
$$ \frac{a_{n+1}}{3^{n+1}} - \frac{a_{n}}{3^{n}} = \frac{(2a_{n}-b_{n})-3a_{n}}{3^{n+1}} = -\frac{a_{0}+b_{0}}{3} \quad\leadsto\quad a_{n} = a_{0}3^{n} - (a_{0}+b_{0})n3^{n-1}$$
となり，したがって
$$ b_{n} = 3^{n}(a_{0}+b_{0})-a_{n} = b_{0}3^{n}+(a_{0}+b_{0})n3^{n-1}$$
を得る．
右辺の係数から定まる行列$A\in\mathbb{C}^{2 \times 2}$の固有値を$\lambda,\mu\in\mathbb{C}$とすると
$$
\exists\,P\in\mathrm{GL}_{2}(\mathbb{C}),\ P^{-1}\begin{bmatrix}
a_{n+1} \\ b_{n+1}
\end{bmatrix} = \underbrace{\begin{bmatrix}
\lambda & \ast \\ 0 & \mu
\end{bmatrix}}_{P^{-1}AP} P^{-1}\begin{bmatrix}
a_{n} \\ b_{n}
\end{bmatrix}$$
が成り立つので，数列$a,b$の適当な線型結合が等比数列となる．とくに
$$
A = \begin{bmatrix}
r & s \\ s & r
\end{bmatrix}$$
なるとき，（$A$は直交行列
$$
P \coloneqq \frac{1}{\sqrt{2}}\begin{bmatrix}
1 & 1 \\ 1 & -1
\end{bmatrix} = P^{-1}$$
で対角化できるので，）$a\pm b$が等比数列となる．
$$
\begin{bmatrix}
a_{n+1} \\ b_{n+1}
\end{bmatrix} = \underbrace{\begin{bmatrix}
2 & -1 \\ 1 & 4
\end{bmatrix}}_{\eqqcolon A} \begin{bmatrix}
a_{n} \\ b_{n}
\end{bmatrix} \quad\leadsto\quad \begin{bmatrix}
a_{n} \\ b_{n}
\end{bmatrix} = A^{n} \begin{bmatrix}
a_{0} \\ b_{0}
\end{bmatrix}$$
であるから，$A^{n}$を求めればよい．
- $A$の固有多項式は
$$ |xE-A| = (x-2)(x-4)+1 = x^{2} -6x + 9 = (x-3)^{2}$$
であるから，pow-doubleにより
$$ A^{n} = n3^{n-1}A - (n-1)3^{n}E = \begin{bmatrix} 2n3^{n-1}-(n-1)3^{n} & -n3^{n-1} \\ n3^{n-1} & 4n3^{n-1}-(n-1)3^{n} \end{bmatrix} = \begin{bmatrix} 3^{n}-n3^{n-1} & -n3^{n-1} \\ n3^{n-1} & 3^{n}+n3^{n-1} \end{bmatrix}$$
となる．よって
$$ \begin{dcases} a_{n} = a_{0}3^{n} - (a_{0}+b_{0})n3^{n-1} \\ b_{n} = b_{0}3^{n} + (a_{0}+b_{0})n3^{n-1} \end{dcases}$$
を得る． - ケーリー・ハミルトンの定理より
$$ O = A^{2}-6A+9E = (A-3E)^{2}$$
であり
$$ A-3E = \begin{bmatrix} -1 & -1 \\ 1 & 1 \end{bmatrix},\ (A-3E)\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -1 \\ 1 \end{bmatrix}$$
であるから，
$$ P \coloneqq \begin{bmatrix} -1 & 1 \\ 1 & 0 \end{bmatrix} \quad\leadsto\quad P^{-1}AP = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$$
より
$$ A^{n} = \begin{bmatrix} -1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 3^{n} & n3^{n-1} \\ 0 & 3^{n} \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} -3^{n} & 3^{n}-n3^{n-1} \\ 3^{n} & n3^{n-1} \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 3^{n} - n3^{n-1} & -n3^{n-1}\\ n3^{n-1} & 3^{n}+n3^{n-1} \end{bmatrix}$$
となる．よって
$$ \begin{dcases} a_{n} = a_{0}3^{n} - (a_{0}+b_{0})n3^{n-1} \\ b_{n} = b_{0}3^{n} + (a_{0}+b_{0})n3^{n-1} \end{dcases}$$
を得る．
分数型漸化式
$$ a_{n+1} = \frac{a_{n}-2}{a_{n}+4}.$$
一次分数変換
$$
f(z) \coloneqq \frac{z-2}{z+4}$$
について
$$
f(a_{n})=a_{n+1},\ f(-1)=-1,\ f(-2)=-2$$
が成り立つので，
$$
\frac{a_{n+1}+1}{a_{n+1}+2} = \frac{(a_{n}-2)+1(a_{n}+4)}{(a_{n}-2)+2(a_{n}+4)} = \frac{2}{3}\frac{a_{n}+1}{a_{n}+2}$$
を得る．したがって
$$
\frac{a_{n}+1}{a_{n}+2} = \frac{2^{n}}{3^{n}}\frac{a_{0}+1}{a_{0}+2} \quad\leadsto\quad a_{n} = \frac{2\cdot\frac{2^{n}}{3^{n}}\frac{a_{0}+1}{a_{0}+2}-1}{(-1)\cdot\frac{2^{n}}{3^{n}}\frac{a_{0}+1}{a_{0}+2}+1} = \frac{(a_{0}+1)2^{n+1}-(a_{0}+2)3^{n}}{(a_{0}+2)3^{n}-(a_{0}+1)2^{n}}$$
となる．
一般に，一次分数変換
$$
f(z) \coloneqq \frac{pz+q}{rz+s},\ ps-qr \neq 0,\ r \neq 0$$
が
- 相異なる不動点$\alpha,\beta \in \mathbb{C}$を持つとき，
$$ \frac{f(z)-\alpha}{f(z)-\beta} = \frac{(pz+q)-\alpha(rz+s)}{(pz+q)-\beta(rz+s)} = \frac{(p-r\alpha)z+(q-s\alpha)}{(p-r\beta)z+(q-s\beta)} = \frac{p-r\alpha}{p-r\beta}\frac{z-\alpha}{z-\beta}$$
が成り立つ； - ただ一つの不動点$\alpha\in\mathbb{C}$を持つとき，
$$ f(z)-\alpha = \frac{(pz+q)-\alpha(rz+s)}{rz+s} = \frac{(p-r\alpha)(z-\alpha)}{r(z-\alpha)+(s+r\alpha)}$$
より，
$$ \frac{1}{f(z)-\alpha} = \frac{s+r\alpha}{p-r\alpha}\frac{1}{z-\alpha} + \frac{r}{p-r\alpha}$$
が成り立つ．
$$
a_{n+1} = \underbrace{\begin{bmatrix}
1 & -2 \\ 1 & 4
\end{bmatrix}}_{\eqqcolon A} \cdot a_{n} \quad\leadsto\quad a_{n} = A^{n} \cdot a_{0}$$
であるから，$A^{n}$を求めればよい．
- $A$の固有多項式は
$$ |xE-A| = (x-1)(x-4)+2 = x^{2}-5x+6 = (x-2)(x-3)$$
であるから，pow-distにより
$$ A^{n} = \frac{3^{n}-2^{n}}{3-2}A - \frac{3^{n}\cdot 2-3\cdot 2^{n}}{3-2}E = \begin{bmatrix} 2^{n+1}-3^{n} & 2^{n+1}-2\cdot 3^{n} \\ 3^{n}-2^{n} & 2\cdot 3^{n} - 2^{n} \end{bmatrix}$$
となる．よって
$$ a_{n} = \frac{(2^{n+1}-3^{n})a_{0}+(2^{n+1}-2\cdot 3^{n})}{(3^{n}-2^{n})a_{0}+(2 \cdot 3^{n}-2^{n})} = \frac{(a_{0}+1)2^{n+1}-(a_{0}+2)3^{n}}{(a_{0}+2)3^{n}-(a_{0}+1)2^{n}}$$
を得る． - ケーリー・ハミルトンの定理より
$$ O = A^{2}-5A+6E = (A-2E)(A-3E)=(A-3E)(A-2E)$$
であり
$$ A-3E = \begin{bmatrix} -2 & -2 \\ 1 & 1 \end{bmatrix},\ A-2E = \begin{bmatrix} -1 & -2 \\ 1 & 2 \end{bmatrix}$$
であるから，
$$ P \coloneqq \begin{bmatrix} -2 & -1 \\ 1 & 1 \end{bmatrix} \quad\leadsto\quad P^{-1}AP = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}$$
より
$$ A^{n} = \begin{bmatrix} -2 & -1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 2^{n} & 0 \\ 0 & 3^{n} \end{bmatrix}\begin{bmatrix} -1 & -1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} -2^{n+1} & -3^{n} \\ 2^{n} & 3^{n} \end{bmatrix}\begin{bmatrix} -1 & -1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 2^{n+1}-3^{n} & 2^{n+1}-2\cdot 3^{n} \\ -2^{n}+3^{n} & -2^{n}+2\cdot 3^{n} \end{bmatrix}$$
となる．よって
$$ a_{n} = \frac{(2^{n+1}-3^{n})a_{0}+(2^{n+1}-2\cdot 3^{n})}{(3^{n}-2^{n})a_{0}+(2 \cdot 3^{n}-2^{n})} = \frac{(a_{0}+1)2^{n+1}-(a_{0}+2)3^{n}}{(a_{0}+2)3^{n}-(a_{0}+1)2^{n}}$$
を得る．
