定数係数線形漸化式の演算子的解法

𝟙,𝟚,𝟛は省略。
𝟜は$\begin{eqnarray} f(S)=\sum_{i=0}^{k}C_i S^i {\large(}C_i\in\mathbb{C}(i=0,1,\cdots ,k){\large)}\end{eqnarray}$として、$\left\lbrace(S-\lambda)f(S)\right\rbrace a_n=(S-\lambda)\left\lbrace f(S)a_n\right\rbrace \quad (\lambda\in\mathbb{C})$を示せばよい。
$$ \begin{eqnarray} \left\lbrace(S-\lambda)f(S)\right\rbrace a_n&=&\left\lbrace(S-\lambda)\sum_{i=0}^{k}C_i S^i\right\rbrace a_n\\&=&\left(\sum_{i=0}^{k}C_i S^{i+1}-\lambda\sum_{i=0}^{k}C_i S^i\right)a_n\\&=&\sum_{i=0}^{k}C_i a_{n+i+1}-\lambda\sum_{i=0}^{k}C_i a_{n+i}\\&=&(S-\lambda)\left(\sum_{i=0}^{k}C_i a_{n+i}\right)\\&=&(S-\lambda)\left\lbrace\sum_{i=0}^{k}C_i S^i a_n\right\rbrace\\&=&(S-\lambda)\left\lbrace f(S)a_n\right\rbrace \end{eqnarray}$$

$$ f(S)= \sum_{i=0}^{k}c_i S^i$$とおくと
$$\begin{eqnarray} f(S)\lambda^n&=&\left(\sum_{i=0}^{k}c_i S^i\right)\lambda^n &=&\sum_{i=0}^{k}c_i \lambda^{n+i}&=&\left(\sum_{i=0}^{k}c_i\lambda^i\right)\lambda^n &=&f(\lambda)\lambda^n\end{eqnarray}$$
となるから、
$$ f(S)\left(\frac{1}{f(\lambda)}\lambda^n\right)=\frac{1}{f(\lambda)}f(S)\lambda^n=\frac{1}{f(\lambda)} f(\lambda)\lambda^n=\lambda^n$$

$$ f(S)P_i (n)=g_i (n)\quad(i=1,2,\cdots ,k)$$
であるから、
$$\begin{eqnarray} f(S)\left(\sum_{i=1}^{k}C_i P_i (n)\right)&=&\sum_{i=1}^{k}C_i f(S)P_i (n)\\ &=&\sum_{i=1}^{k}C_i g_i (n) \end{eqnarray}$$

全ての自然数$k$で成り立つことを数学的帰納法で示す。
[1]$k=1$の場合は前に証明しているので省略します。
[2]$k=m(m\geq 1)$で成り立つと仮定すると、
$$　(S-\lambda_1)(S-\lambda_2)\cdots(S-\lambda_m)a_n=0$$の一般解は
$$ a_n=C_1 \lambda^n_1+C_2 \lambda^n_2+\cdots +C_m \lambda^n_m$$であるから、
$$　(S-\lambda_1)(S-\lambda_2)\cdots(S-\lambda_m)(S-\lambda_{m+1})a_n=0$$は
$$ (S-\lambda_{m+1})a_n=C_1 \lambda^n_1+C_2 \lambda^n_2+\cdots +C_m \lambda^n_m\quad\cdots(A)$$
と変形できる。同次解は$C_{m+1}\lambda^n_{m+1}$である。
補題３から、$$ (S-\lambda_{m+1})a_n=\lambda^n_i\quad(i=1,2,\cdots,m)$$の特殊解は
$$　a_n=\frac{1}{\lambda_i-\lambda_{m+1}}\lambda_i^n$$で与えられるから、補題４より$(A)$の一般解は
$$ a_n=C'_1 \lambda^n_1+C'_2 \lambda^n_2+\cdots +C'_m \lambda^n_m+C_{m+1} \lambda^n_{m+1}\quad\left(C'_i=\frac{C_i}{\lambda_i-\lambda_{m+1}}\right)$$
である。よって$k=m+1$でも成り立つ。
[1],[2]より、全ての自然数$k$で成り立つ。

二項係数は$\begin{eqnarray}\binom{n}{k}\end{eqnarray}$ $\left(={}_n\mathrm{C}_k\right)$で書きます。
$$\begin{eqnarray} (S-\lambda)^k a_n &=& \sum_{i=0}^{k}\binom{k}{i}(-\lambda)^{k-i}S^i a_n\\ &=& \sum_{i=0}^{k}\binom{k}{i}(-1)^{k-i} \lambda^{k-i}a_{n+i}\\ &=& \lambda^{n+k}\sum_{i=0}^{k}\binom{k}{i}(-1)^{k-i}\frac{a_{n+i}}{\lambda^{n+i}}\\ &=& \lambda^{n+k}\sum_{i=0}^{k}\binom{k}{i}(-1)^{k-i}S^i\frac{a_n}{\lambda^n}\\ &=&\lambda^{n+k}(S-1)^k\frac{a_n}{\lambda^n}\\ &=&\lambda^{n+k}\Delta^k (\lambda^{-n}a_n) \end{eqnarray}$$

$\begin{eqnarray}g(n)\in G(\lambda,m)\end{eqnarray}$ならば$g(n)=(C_0 +C_1 n+C_2 n^2+\cdots +C_{m-1} n^{m-1})\lambda^n$とおけて、
$$\begin{eqnarray}　\Delta g(n)&=&(C_0 +C_1 (n+1)+C_2 (n+1)^2+\cdots +C_{m-1} (n+1)^{m-1})\lambda^{n+1}-(C_0 +C_1 n+C_2 n^2+\cdots +C_{m-1} n^{m-1})\lambda^n\\ &=&(C_0\lambda-C_0 +C_1 \lambda(n+1)-C_1 n+C_2\lambda (n+1)^2-C_2 n^2+\cdots +C_{m-1}\lambda (n+1)^{m-1}-C_{m-1} (n+1)^{m-1})\lambda^n \end{eqnarray}$$
であるので、常に$\begin{eqnarray}\Delta g(n)\in G(\lambda,m)\end{eqnarray}$
また、$i$次の係数は$C_j(j=i,i+1,\cdots ,m-1)$で表されるので、任意の$\begin{eqnarray}f(n)\in G(\lambda,m)\end{eqnarray}$で$\Delta g(n)=f(n)$となるような定数$C_i(i=0,1,\cdots ,k-1)$は一意に決定される。
これを$k$回繰り返せば、題意が従う。

全ての自然数$k$で成り立つことを数学的帰納法で示す。
[1]$k=1$のときは補題7より成立する。
[2]$k=N(\geq 1)$で成り立つと仮定すると、
$$ (S-\lambda_1)^{m_1}(S-\lambda_2)^{m_2}\cdots (S-\lambda_N)^{m_N}a_n=0$$の一般解は$$ a_n= \sum_{i=1}^{N}\left(\lambda_i^n\sum_{j=0}^{m_i-1}C_{i,j}n^j\right) $$であるから、$$ (S-\lambda_1)^{m_1}(S-\lambda_2)^{m_2}\cdots (S-\lambda_N)^{m_N}(S-\lambda_{N+1})^{m_{N+1}}a_n=0\quad \cdots (B)$$は$$ (S-\lambda_{N+1})^{m_{N+1}}a_n=\sum_{i=1}^{N}\left(\lambda_i^n\sum_{j=0}^{m_i-1}C_{i,j}n^j\right) $$と変形できる。これの同次解は$$ \lambda_{N+1}^n\sum_{j=0}^{m_{N+1}-1}C_{{N+1},j}n^j$$である。
ここで、$$ (S-\lambda_{N+1})^{m_{N+1}}a_n=\lambda_i^n\sum_{j=0}^{m_i-1}C_{i,j}n^j\quad (i=1,2,\cdots,m)\quad \cdots(C)$$は補題6より$$\begin{eqnarray} \lambda_{N+1}^{n+m_{N+1}}\Delta^{m_{N+1}} (\lambda_{N+1}^{-n}a_n)&=&\lambda_i^n\sum_{j=0}^{m_i-1}C_{i,j}n^j\\ \Delta^{m_{N+1}} (\lambda_{N+1}^{-n}a_n)&=&\lambda_{N+1}^{m_{N+1}}\left(\frac{\lambda_i}{\lambda_{N+1}}\right)^n \cdot \sum_{j=0}^{m_i-1}C_{i,j}n^j\quad\cdots(D)\end{eqnarray}$$と変形でき、補題7より、漸化式$(S-\lambda)^m a_n=0$の一般解を$a_n=g(\lambda,m)$とすると、$$ g\left(\frac{\lambda_i}{\lambda_{N+1}},m_i\right)=\left(\frac{\lambda_i}{\lambda_{N+1}}\right)^n\cdot\sum_{j=0}^{m_i-1}C_{i,j}n^j$$であるので、$$ \Delta^{m_{N+1}} (\lambda_{N+1}^{-n}a_n)=g\left(\frac{\lambda_i}{\lambda_{N+1}},m_i\right)\quad\cdots(E)$$
よって補題8より、$(E)$の特殊解であって$\begin{eqnarray}G\left(\frac{\lambda_i}{\lambda_{N+1}},m_i\right)\end{eqnarray}$に属するものが存在するから、適切に定数$C'_{i,j}$を取って、$$ \lambda_{N+1}^{-n}a_n=\left(\frac{\lambda_i}{\lambda_{N+1}}\right)^n\sum_{j=0}^{m_i-1}C'_{i,j}n^j$$とすれば、これは(E)を満たす。また、補題8より、$C'_{i,j}$は任意定数としてよい。
ゆえに、$$ \lambda_i^n\sum_{j=0}^{m_i-1}C'_{i,j}n^j$$が(C)の特殊解となるので、補題4より、$$\sum_{i=1}^{N}\left(\lambda_i^n\sum_{j=0}^{m_i-1}C'_{i,j}n^j\right)$$は(B)の特殊解となるから、(B)の一般解は、$$ a_n=\lambda_{N+1}^n\sum_{j=0}^{m_{N+1}-1}C_{{N+1},j}n^j+\sum_{i=1}^{N}\left(\lambda_i^n\sum_{j=0}^{m_i-1}C'_{i,j}n^j\right)$$である。
$C_{{N+1},j}=C'_{{N+1},j}$とおけば、$$ a_n=\sum_{i=1}^{N+1}\left(\lambda_i^n\sum_{j=0}^{m_i-1}C'_{i,j}n^j\right)$$よって$k=N+1$でも成り立つ。
[1],[2]より、全ての自然数$k$で成り立つ。