隣接n項間漸化式の線形的アプローチ(2)

　隣接n項間漸化式の線形的アプローチの続き
c-and-a.hatenablog.com

　特性方程式が $P(\lambda)$ になる漸化式の解の集合を $W(P)$ と表す。
${\{g_m\}_{m\in\mathbb{N}}\in W(P)\wedge\{g_m\}_{m\in\mathbb{N}}\in W(Q)}$ を ${\{g_m\}_{m\in\mathbb{N}}}$ が満たすとする。剰余の定理から $\deg P\geq \deg Q$ とすると

${P(\lambda)=A_1(\lambda)Q(\lambda)+B_1(\lambda)}$

を満たす ${\deg P -\deg Q}$ 次多項式 ${A_1(\lambda)}$ と高々 ${\deg Q -1}$ 次多項式 ${B_1(\lambda)}$ の存在が保証される。ここで、

$P(\lambda)=\sum_{i=0}^{\deg P}{p_i \lambda^i},\quad Q(\lambda)=\sum_{i=0}^{\deg Q}{q_i \lambda^i}$
$A_1(\lambda)=\sum_{i=0}^{\deg P -\deg Q}{a_{1,i} \lambda^i},\quad B_1(\lambda)=\sum_{i=0}^{\deg B_1}{b_{1,i} \lambda^i}$

と表すと

${\begin{align}\displaystyle \sum_{l=0}^{deg P}{p_l\lambda^{l}}&=\sum_{i=0}^{\deg P -\deg Q}{a_{1,i} \lambda^i}\sum_{l'=0}^{\deg Q}{q_{l'}\lambda^{l'}}+\sum_{i=0}^{\deg B_1}{b_{1,i} \lambda^i}\\&=\sum_{i=0}^{\deg P -\deg Q}{a_{1,i}}\sum_{l'=0}^{\deg Q}{q_{l'}\lambda^{i+l'}}+\sum_{i=0}^{\deg B_1}{b_{1,i}\lambda^i}\end{align}}$

となり、漸化式は

$\forall m\in\mathbb{N}\quad\sum_{l=0}^{\deg P}{p_{l}g_{m+l}}=\sum_{i=0}^{\deg P -\deg Q}{a_{1,i}}\sum_{l'=0}^{\deg Q}{q_{l'}g_{m+i+l'}}+\sum_{i=0}^{\deg B_1}{b_{1,i} g_{m+i}}$

と変形できる。 ${\{g_m\}_{m\in\mathbb{N}}\in W(P)\wedge\{g_m\}_{m\in\mathbb{N}}\in W(Q)}$ から ${\{g_m\}_{m\in\mathbb{N}}}$ は

${\displaystyle\forall m\in\mathbb{N}\quad\sum_{i=0}^{\deg B_1}{b_{1,i} g_{m+i}}=0}$

を満たす。よって

${\displaystyle\begin{align}\{g_m\}_{m\in\mathbb{N}}\in W(P)\wedge\{g_m\}_{m\in\mathbb{N}}\in W(Q)&\iff\{g_m\}_{m\in\mathbb{N}}\in W(P)\cap W(Q)\\ & \implies\{g_m\}_{m\in\mathbb{N}}\in W(B_1)\end{align}}$

つまり、 ${W(P)\cap W(Q)\subset W(B_1)}$ がいえる。
同様にして

$Q(\lambda)=A_2(\lambda) B_1(\lambda)+B_2(\lambda)$
$W(B_2)\supset W(Q)\cap W(B_1)\supset W(Q)\cap W(P)$
$B_1(\lambda)=A_3(\lambda) B_2(\lambda)+B_3(\lambda)$
$W(B_3)\supset W(B_1)\cap W(B_2)\supset W(B_1)\cap W(Q)$
$\vdots$
$B_s(\lambda)=A_{s+2}(\lambda) B_{s+1}(\lambda)+B_{s+2}(\lambda)$
$W(B_{s+2})\supset W(B_s)\cap W(B_{s+1})\supset W(B_s)\cap W(B_{s-1})$

と、順に多項式 ${A_s(\lambda),B_s(\lambda)(s\in\mathbb{N})}$ を求めることが出来る。また、これにより、 $W(P)\cap W(Q)\subset W(B_s)$ がいえる。この操作はユークリッドの互除法として知られ、それによると、ある $s'$ で $B_{s'}$ が $P(\lambda)$ と $Q(\lambda)$ の最大公約元 $\text{GCD}(P,Q)$ に一致することが分かる( $P$ が $Q$ で割り切れたときは最大公約元は $Q$ )。つまり

$\displaystyle W(P)\cap W(Q)\subset W(\text{GCD(P,Q)})$

を満たす。
　
　 $k\neq k'$ のとき、既約多項式であるので、 ${\text{GCD} \left(\left(P_k(\lambda)\right)^{h_k},(P_{k'}(\lambda))^{h_{k'}}\right)=1}$ より、 $U_k\cap U_{k'}\subset W(1)$ となる。特性方程式が $1$ である漸化式は

${\displaystyle\forall m\in\mathbb{N}\quad f_m=0}$

であるので、項が全て $0$ である数列を ${\{o_m\}_{m\in\mathbb{N}}}$ と書くと、 $W(1)=\{\{o_m\}_{m\in\mathbb{N}}\}$ である。また、 $\{o_m\}_{m\in\mathbb{N}}\in U_k,U_{k'}$ でもあるので $U_k\cap U_{k'}\supset W(1)$ がいえ、
$U_k\cap U_{k'}= W(1)=\{\{o_m\}_{m\in\mathbb{N}}\}$ である。