\(N\) 次多項式 \(f(x)\) に対して、数列 \(f(0), f(1), f(2), …\) の母関数を \(\displaystyle F(x) := \sum_{i = 0}^\infty f(i)x^i\) とします。

このとき、ある \(N\) 次多項式 \(P(x)\) が存在して、\(F(x) = \dfrac{P(x)}{(1 - x)^{N+1}}\) と表すことができます。

\(N\) 次多項式 \(f(x)\) を

\[\begin{aligned}f(x) &= a_0 \binom{x}{0} + a_1 \binom{x}{1} + a_2 \binom{x}{2} + \dots + a_N \binom{x}{N} \\ &= \frac{a_0}{0!} +\frac{a_1}{1!} x + \frac{a_2}{2!}x(x-1) + \dots + \frac{a_N}{N!}x(x-1)\cdots(x-N+1) \\ \end{aligned}\]

と Newton 基底に分解したときの係数を \(a_0, a_1, \dots, a_N\) とします。

数列 \(\displaystyle\binom{0}{k}, \binom{1}{k}, \binom{2}{k}, \dots\) の母関数は \(\dfrac{1}{(1 - x)^{k+1}}\) であるので、

\[\begin{aligned} F(x) &= \frac{a_0}{1 - x} + \frac{a_1}{(1 - x)^2} + \dots + \frac{a_N}{(1 - x)^{N+1}} \\ &= \frac{1}{(1 - x)^{N + 1}}(a_0(1 - x)^N + a_1(1 - x)^{N-1} + \dots + a_N)\end{aligned}\]

より、\(P(x) = a_0(1 - x)^N + a_1(1 - x)^{N-1} + \dots + a_N\) であることが分かります。

数列 \(f(0), 2f(1), 4f(2), 8f(3), …\) の母関数は、 \(\displaystyle \sum_{i = 0}^\infty 2^if(i)x^i = \sum_{i = 0}^\infty f(i)(2x)^i = F(2x) = \frac{P(2x)}{(1 - 2x)^{N+1}}\) です。

同様に、数列 \(g(0), g(1), g(2), g(3), …\) の母関数は、\(N\) 次多項式 \(Q(x)\) を用いて \(\dfrac{Q(x)}{(1 - x)^{N+1}}\) と表せます。

\(h(0), h(1), h(2), h(3), …\) の母関数は、\(\displaystyle \frac{P(2x)}{(1 - 2x)^{N+1}} + \frac{Q(x)}{(1 - x)^{N+1}} = \frac{(1 - x)^{N+1}P(2x) + (1 - 2x)^{N+1}Q(x)}{(1 - 2x)^{N+1}(1 - x)^{N+1}}\) であるので、\((1 - 2x)^{N+1}(1 - x)^{N+1}\) を展開したものが \(h(0), h(1), h(2), h(3), …\) の線形漸化式となります。