読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

母関数を用いた種々の技法(その 1)

{
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} の指数母関数
{\displaystyle \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}}
故,
{\displaystyle \hat{G}(z) = \frac{1}{1 - z} = \sum_{n\geqslant 0}z^n}
が求まる. 従って {g_n = n!} である.

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