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

更新日時 2023/09/04
母関数

数列 ana_n に対して, f(x)=k=0akxk f(x)=\displaystyle\sum_{k=0}^{\infty} a_k x^k を母関数と呼ぶことがある。

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

これは通常型母関数と呼ばれます。他にも指数型母関数なども存在します。

母関数とは

母関数は数列に関する情報を全て含んだ関数です。数列の一般項が分かれば母関数を構成できます(ただし,無限級数 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. 母関数から一般項を求める

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

母関数の性質

母関数の性質

ff を数列 {an}\{ a_n \} の母函数,gg を数列 {bn}\{ b_n \} の母函数とする。このとき

  1. f+gf + g{anbn}\{ a_n b_n \} の母函数である
  2. fgfg{anbn}\{ a_n * b_n \} の母函数である

なお {anbn}\{ a_n * b_n \} は畳み込みである。→ 合成積(畳み込み)の意味と応用3つ

実践:カタラン数の母関数

以下では,母関数を用いて漸化式を解く例を紹介します。

例題

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

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

漸化式から計算する

方針

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

カタラン数の母関数を f(x)=k=0ckxkf(x)=\displaystyle\sum_{k=0}^{\infty} c_k x^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)1x\begin{aligned} f(x)^2 &= \sum_{n=0}^{\infty} \left( \sum_{i=0}^nc_{i}c_{n-i} \right) x^n\\ &= \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} \end{aligned}

よって,f(x)f(x) についての2次方程式

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

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

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

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

よって,カタラン数の母函数は 114x2x \dfrac{1 - \sqrt{1-4x}}{2x} である。

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

方針

母関数から一般項を求めるためには,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!\begin{aligned} &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!} \end{aligned}

よって,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

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

収束性について

母関数の級数展開を考えました。

母函数はあくまでも形式的な冪級数です。そのため収束性の議論をする必要はないです。

ただし,収束半径の内側にある十分小さい xx に対しては冪級数が収束します。よって十分小さい xx に対しては関数として扱うことができることに注意しましょう。

様々な母関数

n2n^2 の母関数

形式的に微分して母関数を計算してみましょう。

例1

bn=n+1b_n = n+1 の母函数を計算しよう。

(xn+1)=(n+1)xn(x^{n+1})' = (n+1) x^n であるため, n=0xn \sum_{n=0}^{\infty} x^n の微分が bnb_n の母函数である。

an=1a_n = 1 である数列の母函数は 11x\dfrac{1}{1-x} であった。(前述の例)

よって 1(1x)2\dfrac{1}{(1-x)^2} が母関数である。

例2

cn=n+2C2c_n = {}_{n+2} \mathrm{C}_2 の母函数を計算しよう。

n+2C2=12(n+2)(n+1){}_{n+2} \mathrm{C}_2 = \dfrac{1}{2} (n+2)(n+1) である。

例1と同じように考えると 11x\dfrac{1}{1-x} を2回微分して 22 で割ったものが母関数である。

よって 1(1x)3\dfrac{1}{(1-x)^3} が母関数である。

母関数の性質を用いて計算をしてみましょう。

例3

dn=n2d_n = n^2 の母関数を計算しよう。

n2=n2+3n+2(3n+3)+1=2n+2C23(n+1)+1=2cn3bn+an\begin{aligned} n^2 &= n^2 + 3n + 2 - (3n + 3) + 1\\ &= 2 {}_{n+2} \mathrm{C}_2 - 3 (n+1) + 1\\ &= 2 c_n - 3 b_n + a_n \end{aligned} であるため,母関数の性質より 2(1x)33(1x)2+11x=x(x+1)(1x)3 \dfrac{2}{(1-x)^3} - \dfrac{3}{(1-x)^2} + \dfrac{1}{1-x} = \dfrac{x(x+1)}{(1-x)^3} が母関数である。

リュカ数の母関数

リュカ数 とは,

  • L0=0L_0 = 0
  • L1=1L_1 = 1
  • Ln+2=Ln+1+LnL_{n+2} = L_{n+1} + L_n

を満たす数列です。

一般項は Ln=(1+52)n(152)n L_n = \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \left( \dfrac{1-\sqrt{5}}{2} \right)^n となります。

例4

n=0Lnxn=x2x2+x1 \sum_{n=0}^{\infty} L_n x^n = \dfrac{x-2}{x^2+x-1}

証明

α=152\alpha = \dfrac{1-\sqrt{5}}{2}β=1+52\beta = \dfrac{1+\sqrt{5}}{2} とおく。

α+β=1\alpha + \beta = 1αβ=1\alpha \beta = 1 である。

n=0Lnxn=n=0(βnxnαnxn)=11βx+11αx=2(α+β)x1(α+β)x+αβx2=2xx2+x1\begin{aligned} &\sum_{n=0}^{\infty} L_n x^n\\ &= \sum_{n=0}^{\infty} (\beta^n x^n - \alpha^n x^n)\\ &= \dfrac{1}{1-\beta x} + \dfrac{1}{1-\alpha x}\\ &= \dfrac{2 - (\alpha + \beta) x}{1-(\alpha + \beta) x + \alpha \beta x^2}\\ &= \dfrac{2-x}{x^2 + x - 1} \end{aligned}

微分・積分をすると面白い母関数が得られます。

例5

n=1Lnnxn=logx2+x1 \sum_{n=1}^{\infty} \dfrac{L_n}{n} x^n = - \log |x^2+x-1|

証明

(n=1Lnnxn)=n=1Lnxn1=1xn=0LnxnL0x=1xx2x2+x12x=2x+1x2+x1\begin{aligned} \left( \sum_{n=1}^{\infty} \dfrac{L_n}{n} x^n \right)' &= \sum_{n=1}^{\infty} L_n x^{n-1}\\ &= \dfrac{1}{x} \sum_{n=0}^{\infty} L_n x^n - \dfrac{L_0}{x}\\ &= \dfrac{1}{x} \dfrac{x-2}{x^2+x-1} - \dfrac{2}{x}\\ &= -\dfrac{2x+1}{x^2+x-1} \end{aligned} より n=1Lnnxn=2x+1x2+x1dx=logx2+x1+C\begin{aligned} \sum_{n=1}^{\infty} \dfrac{L_n}{n}x^n &= -\int \dfrac{2x+1}{x^2+x-1} dx\\ &= - \log |x^2+x-1| + C \end{aligned} となる。

x=0x=0 のとき,C=0C = 0 であるため,

n=1Lnnxn=logx2+x1 \sum_{n=1}^{\infty} \dfrac{L_n}{n} x^n = - \log |x^2+x-1|

を得る。

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

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

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