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

更新日時 2021/03/07
母関数

数列 ana_n に対して,

f(x)=k=0akxkf(x)=\displaystyle\sum_{k=0}^{\infty}a_kx^k

を母関数と呼ぶことがある。

数列に対する母関数の定義はいくつかありますが,この記事では上記の通常型母関数を考えます。

目次
  • 母関数とは

    1. カタラン数の母関数をなんとかして求める
  • 母関数から一般項を求める

母関数とは

母関数は数列に関する情報を全て含んだ関数です。数列の一般項が分かれば母関数を構成できます(ただし,無限級数 k=0akxk\displaystyle\sum_{k=0}^{\infty}a_kx^k がすべての xx について収束するとは限りません)。

母関数の例

全ての項が1である数列 an=1a_n=1 の母関数は,

1+x+x2+1+x+x^2+\cdots

である。これは,1<x<1-1<x<1 という条件のもとで

11x\dfrac{1}{1-x}

に収束する(シンプルな形で表現できる)。

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

逆に,母関数から数列の一般項を求められる場合があります。つまり,以下の手順を踏むことで難しい数列の一般項を求められる場合があります。

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

もちろん,数列の母関数を求めるのも一般的には難しいので万能な方法ではありません。

以下では,母関数を用いて漸化式を解く例を紹介します(けっこう難しいです)。

例題

c0=1,cn+1=i=0ncicnic_0=1,\:c_{n+1}=\displaystyle\sum_{i=0}^nc_{i}c_{n-i} という漸化式を解いて数列の一般項 cnc_n を求めよ。

これは,「カタラン数」の漸化式です。→カタラン数の意味と漸化式

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

方針

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

カタラン数の母関数を f(x)=k=0ckxkf(x)=\displaystyle\sum_{k=0}^{\infty}c_kx^k とおく。

f(x)2f(x)^2xnx^n の係数は i=0ncicni\displaystyle\sum_{i=0}^nc_{i}c_{n-i} となるので漸化式が使える:

f(x)2=n=0(i=0ncicni)xn=n=0cn+1xn=n=0cn+1xn+1x=f(x)1xf(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)f(x) についての2次方程式

f(x)2xf(x)+1=0f(x)^2x-f(x)+1=0

を得る。これを x0x \neq 0 の範囲で解いて,

f(x)=1±14x2xf(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}

ただし,初期条件 f(0)=c0=1f(0)=c_0=1 であり,x=0x=0 で関数が連続になる必要があるため符号がマイナスの方が採用される。

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

方針

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

14x\sqrt{1-4x}n+1n+1 回微分係数 f(n+1)(0)f^{(n+1)}(0) を求める:

f(n+1)(0)=(4)n+112(12)(32)(2n12)=2n+1(2n1)(2n3)31=2(2n)!n!f^{(n+1)}(0)\\ =(-4)^{n+1}\dfrac{1}{2}\left(-\dfrac{1}{2}\right)\left(-\dfrac{3}{2}\right)\cdots\left(-\dfrac{2n-1}{2}\right)\\ =-2^{n+1}(2n-1)(2n-3)\cdots 3\cdot 1\\ =-2\dfrac{(2n)!}{n!}

よって,14x\sqrt{1-4x} をマクローリン展開した時の n+1n+1 乗の係数は 2(2n)!(n+1)!n!-2\dfrac{(2n)!}{(n+1)!n!} となり,

f(x)f(x) を展開したときの xnx^n の係数は,

(2n)!(n+1)!n!=1n+12nCn\dfrac{(2n)!}{(n+1)!n!}=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_n

となりカタラン数の一般項となる。

※上記ではマクローリン展開を用いており,級数の収束について厳密な議論ができていません(正当化できそうですが,すぐには分からず…)。気になる方は「母関数を用いた議論は漸化式の解の候補を見つけるもの」「厳密には,実際にその候補が漸化式を満たすことを確認した方がよい(けど大変)」と考えてください。

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

Tag:マクローリン展開の応用例まとめ

Tag:漸化式の解き方11パターンと応用例まとめ