母関数を用いた種々の技法(その 1) - Red cat の数学よもやま話・新装開店

${ g_0 = 1,\\ g_n = ng_{n-1}\ (n\geqslant 1) }$
なる漸化式を見たとき, 数学が得意な方であればこれが ${g_n = n!}$ であることはすぐにわかると思う. しかし, ここでは母関数を用いた解法を紹介したい.

上の式は一行で書くと
${g_n = ng_{n-1} + [n = 0]}$
となる. 系列 ${\langle g_n\rangle}$ の指数母関数
$\hat{G}(z) = \sum_{n\geqslant 0}g_n\frac{z^n}{n!}$
を考えると
${\begin{align} \hat{G}(z) &= \sum_{n\geqslant 0}ng_{n-1}\frac{z^n}{n!} + 1 \\ &= z\sum_{n\geqslant 1}g_{n-1}\frac{z^{n-1}}{(n-1)!} + 1 \\ &= z\sum_{n\geqslant 0}g_n\frac{z^n}{n!} + 1 \\ &= z\hat{G}(z) + 1 \end{align}}$
故,
$\hat{G}(z) = \frac{1}{1 - z} = \sum_{n\geqslant 0}z^n$
が求まる. 従って ${g_n = n!}$ である.

これは簡単な例であるが, 次回以降, もう少し複雑な式の求め方を紹介する.