前回では基本操作を組合せることによって多くの母関数が作れることを紹介しました。今回は漸化式から母関数を同様の基本操作で作れることを示します。
漸化式から母関数を作る
【例題 1】 以下の漸化式からなる数列の母関数を求めよ
\begin{align}
&a_0 = 1, a_1 = 3\\
&a_n = 3a_{n-1}-2a_{n-2}
\end{align}
\begin{align}
&ポイントは \\
&a_n -3a_{n-1}+2a_{n-2} = 0 \\
&が成り立つので \\
&元の数列に各項を3倍して１つ右にシフトしたものを引き、\\
&2倍して２つ右にシフトしたものを足すと、\\
&3項目以降はすべてゼロになるはずです。
\end{align}
数列を$a_4$まで求め[1,3,7,15,31]、実際に試してみましょう。
| $x^0$ | $x^1$ | $x^2$ | $x^3$ | $x^4$ | ... | $x^n$ | ... | ||
|---|---|---|---|---|---|---|---|---|---|
| $A$ | $=$ | $1$ | $3$ | $7$ | $15$ | $31$ | ... | $a_{n}$ | ... |
| $-3xA$ | $=$ | $0$ | $-3$ | $-9$ | $-21$ | $-45$ | ... | $-3a_{n-1}$ | ... |
| $+2x^2A$ | $=$ | $0$ | $0$ | $2$ | $6$ | $14$ | ... | $2a_{n-2}$ | ... |
| $(1-3x+2x^2)A$ | $=$ | $1$ | $0$ | $0$ | $0$ | $0$ | ... | 0 | ... |
\begin{align}
&(1-3x+2x^2)A = 1 \\
&となり \\
&母関数\ A = \frac{1}{1-3x+2x^2} \\
&が求まります。
\end{align}
大体やり方は分かったと思うのでいくつか漸化式から母関数を求めてみます。
フィボナッチ数列の母関数を求める
\begin{align}
&フィボナッチ数列の漸化式は \\
&a_0 = 0, a_1 = 1\\
&a_n = a_{n-1}+a_{n-2} \\
&なので \\
&a_n - a_{n-1}-a_{n-2}=0 が成り立つ
\end{align}
| $x^0$ | $x^1$ | $x^2$ | $x^3$ | $x^4$ | ... | $x^n$ | ... | ||
|---|---|---|---|---|---|---|---|---|---|
| $F$ | $=$ | $0$ | $1$ | $1$ | $2$ | $3$ | ... | $a_{n}$ | ... |
| $-xF$ | $=$ | $0$ | $0$ | $-1$ | $-1$ | $-2$ | ... | $-a_{n-1}$ | ... |
| $-x^2F$ | $=$ | $0$ | $0$ | $0$ | $-1$ | $-1$ | ... | $-a_{n-2}$ | ... |
| $(1-x-x^2)A$ | $=$ | $0$ | $1$ | $0$ | $0$ | $0$ | ... | 0 | ... |
\begin{align}
(1-x-x^2)F &= x から \\
母関数\ F &= \frac{x}{1-x-x^2} が求まります。
\end{align}
三角数の漸化式から母関数を求める
\begin{align}
三角数&の漸化式は \\
a_0 &= 1\\
a_n &= a_{n-1}+n \\
な&ので\\
a_n - a_{n-1}&=n が成り立つ
\end{align}
ここで前回の記事で$n=[1,2,3,4,5,...]$の母関数は$\large \frac{1}{(1-x)^2}$であることが分かっているのでこれを使います。
| $x^0$ | $x^1$ | $x^2$ | $x^3$ | $x^4$ | ... | $x^n$ | ... | ||
|---|---|---|---|---|---|---|---|---|---|
| $T$ | $=$ | $1$ | $3$ | $6$ | $10$ | $15$ | ... | $a_{n}$ | ... |
| $-xT$ | $=$ | $0$ | $-1$ | $-3$ | $-6$ | $-10$ | ... | $-a_{n-1}$ | ... |
| $\large \frac{1}{(1-x)^2}$ | $=$ | $1$ | $2$ | $3$ | $4$ | $5$ | ... | $n$ | ... |
\begin{align}
(1-x)T &= \frac{1}{(1-x)^2} から \\
母関数 T &=\frac{1}{(1-x)^3} が求まります。
\end{align}
ちなみに三角数は$\large \frac{1}{(1-x)^2}$をもう一度微分する方法でも求める事が出来ます。
\begin{align}
\frac{1}{(1-x)^2} &= 1+2x+3x^2+4x^3+5x^4 \cdots \\
&両辺を微分すると \\
\frac{2}{(1-x)^3} &= 2+6x+12x^2+20x^3+30x^4 \cdots \\
&両辺を2で割る \\
\frac{1}{(1-x)^3} &= 1+3x+6x^2+10x^3+15x^4 \cdots \\
\end{align}
これで色々な数列に関して母関数を求めることが出来るようになったような気がしませんか？
ところで母関数を求めると、どんな良いことがあるのでしょうか。次回の（その３）ではSageamthを使って母関数から色々な問題を解く方法を紹介したいと思います。