多項間漸化式の母関数

調べても出てこないのでメモ。というか基本理念として、調べても出てこないものばかり記事にする。そもそも、収益や閲覧数を目的としていないのでそれは必然的だ。
また、昨日家に出現したゴキブリを退治しようとしたところ、右手中指を骨まで切断。金がないので病院に行けず、応急措置を誤ったため断層が発現し、多分なにもしなければ二度と元どおりには治らない。そのため、４本指のタイピングが上手くなる。

多項間漸化式の解
項間漸化式

\begin{align}
a_{n + k - 1}=\sum^{k - 2}_{m = 0}b_m a_{n + m}
\end{align}

の母関数は

\begin{align}
F(x) &:= \sum^{\infty}_{n = 0}\frac{a_n}{n!}x^n\\
&= \sum^{k - 2}_{m = 0}\frac{P_{k, m + 1}(x)}{P_{k, 0}(x)}a_m x^m
\end{align}

となる。ここで

\begin{align}
P_{k, m}(x)
:=
\begin{cases}
1 - \sum^{k - 2}_{l = m}b_l x^{k - 1 - l} & (m < k - 2)\\
1 & (m = k - 2)
\end{cases}
\end{align}

である。

また、上記ではとしているが、のようにに依存していてもいい。ただにまで依存すると解は別の形になる。（一項間の場合は自明とした。

Proof

まず、級数の中でをくくり出してやる。

\begin{align}
F(x) = \sum^{k - 2}_{n=0}a_n x^n + \sum^{\infty}_{n=k - 1}a_n x^n
\end{align}

右辺第二項は、

\begin{align}
\text{右辺第二項} &= \sum^{\infty}_{n=0}a_{n + k - 1}x^{n + k - 1}\\
&= \sum^{\infty}_{n=0}\sum^{k - 2}_{m=0}b_m a_{n + m}x^{n + k - 1}\\
&= \sum^{k - 2}_{m=0}b_m x^{k - 1 - m}\sum^{\infty}_{n=0}a_{n+m}x^{n+m}\\
&= \sum^{k - 2}_{m=0}b_m x^{k - 1 - m}\left(F(x) - \sum^{m - 1}_{n=0}a_n x^n\right)
\end{align}

であり、これを上式に代入すると

\begin{align}
F(x) = \sum^{k - 2}_{n=0}a_n x^n + \sum^{k - 2}_{m=0}b_m x^{k - 1 - m}\left(F(x) - \sum^{m - 1}_{n=0}a_n x^n\right)
\end{align}

なので右辺のを左辺に移項して係数で割ると

\begin{align}
F(x) = \frac{\sum^{k - 2}_{n=0}a_n x^n - \sum^{k - 2}_{m = 0}\sum^{m - 1}_{n = 0}b_m x^{k - m + n}a_n}{1 - \sum^{k - 2}_{m = 0}b_m x^{k - m}}
\end{align}

となる。であることから、として右辺分子第二項の和を入れ替える。

\begin{align}
F(x) &= \frac{\sum^{k - 2}_{n=0}a_n x^n - \sum^{k - 3}_{n = 0}\sum^{k - 2}_{m = n + 1}b_m x^{k - m + n}a_n}{1 - \sum^{k - 2}_{m = 0}b_m x^{k - m}}\\
&= \frac{a_{k - 2}x^{k - 2} + \sum^{k - 3}_{n = 0}(1 - \sum^{k - 2}_{m = n + 1}b_m x^{k - m})}{1 - \sum^{k - 2}_{m = 0}b_m x^{k - m}}\\
&= \sum^{k - 3}_{m = 0}\frac{P_{k, m + 1}(x)}{P_{k, 0}(x)}a_m x^m
\end{align}

よって題は示された。□