2014/04/12

数列の母関数とその応用例

分野: 数列  レベル: 最難関大学

数列 $a_n$ に対して,その母関数を
$f(x)=\displaystyle\sum_{k=0}^{\infty}a_kx^k$
と定義する。


数列に対する母関数の定義はいくつかありますが,上記の定義が一般的で,通常型母関数とも言います。

母関数とは

母関数とは数列に関する情報を全て含んだ関数です。つまり,数列の一般項が分かれば母関数を構成することができますし,母関数が分かればその数列の一般項を求めることもできます。母関数と数列は一対一に対応しているのです。数列を生み出す関数という意味で「母関数」と呼ばれます。

全ての項が1である数列 $a_n=1$ の母関数は,
$1+x+x^2+\cdots=\dfrac{1}{1-x}$

このように,数列が与えられたときにその母関数を求めることは簡単ですが,逆に母関数が与えられたときに数列の一般項を求めることも簡単にできます。

そこで,以下の手順を踏むことで難しい数列の一般項を求めることができる場合があります。

1,一般項を求めたい数列の母関数をなんとかして求める
2,母関数から一般項を求める

もちろん,数列の母関数を求めるのも一般的には難しいので万能な方法ではありませんが,漸化式を解く問題ではこの方法が使える場合があります。

母関数を用いて漸化式を解く例として以下のカタラン数の漸化式を解きます:
$c_0=1, c_{n+1}=\displaystyle\sum_{i=0}^nc_{i}c_{n-i}$
→カタラン数の意味と漸化式

1,カタラン数の母関数をなんとかして求める

方針:漸化式をうまく用いてカタラン数の母関数を求めます。漸化式が畳み込みっぽい形をしているのでとりあえず母関数を二乗してみます。

カタラン数の母関数を $f(x)=\displaystyle\sum_{k=0}^{\infty}c_kx^k$ とおく。
$f(x)^2$ の $x^n$ の係数は $\displaystyle\sum_{i=0}^nc_{i}c_{n-i}$ となるので漸化式が使える:
$f(x)^2=\displaystyle\sum_{n=0}^{\infty}(\sum_{i=0}^nc_{i}c_{n-i})x^n\\
=\displaystyle\sum_{n=0}^{\infty}c_{n+1}x^n\\
=\dfrac{\displaystyle\sum_{n=0}^{\infty}c_{n+1}x^{n+1}}{x}\\
=\dfrac{f(x)-1}{x}$
よって,$f(x)$ についての2次方程式
$f(x)^2x-f(x)+1=0$
を得るので $x \neq 0$ の範囲でこれを解いて,
$f(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}$
ただし,初期条件 $f(0)=c_0=1$ であり,$x=0$ で関数が連続になる必要があるため符号がマイナスの方が採用される。

母関数から一般項を求める

母関数から一般項を求めるためには,$\sqrt{1-4x}$ を多項式(べき級数)で表してやる必要があります。そこで、関数をべき級数に展開する方法:マクローリン展開を用います。

$\sqrt{1-4x}$ の $n+1$ 回微分係数 $f^{(n+1)}(0)$ を求める:
$f^{(n+1)}(0)=(-4)^{n+1}\dfrac{1}{2}(-\dfrac{1}{2})(-\dfrac{3}{2})\cdots(-\dfrac{2n-1}{2})\\
=-2^{n+1}(2n-1)(2n-3)\cdots 3\cdot 1\\
=-2\dfrac{(2n)!}{n!}$
よって,$\sqrt{1-4x}$ をマクローリン展開した時の $n+1$ 乗の係数は$-2\dfrac{(2n)!}{(n+1)!n!}$ となり,
$f(x)$ を展開したときの $x^n$ の係数は,
$\dfrac{(2n)!}{(n+1)!n!}=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_n$
となりカタラン数の一般項となる。

カタラン数の漸化式を解くのはなかなかけわしかったです。

Tag: マクローリン展開の応用例まとめ
Tag: 漸化式の解き方と応用例まとめ

分野: 数列  レベル: 最難関大学