§B4.17母関数入門

最終更新

数列を係数として一つの形式的なべき級数へまとめ、係数の比較によって場合の数と漸化式を扱います。xxは値を代入する変数ではなく、次数ごとの係数を区別する不定元として扱います。

1 定義

定義 1.1 (通常母関数). 数列(an)n≥0(a_n)_{n\ge0}に対して、形式的なべき級数

A(x)=∑n≥0anxnA(x)=\sum_{n\ge0}a_nx^n

を数列の通常母関数といいます。本記事では収束を仮定せず、同じ次数の係数を比較します。

例 1.2 (選び方を積で表す). 赤玉を0個から2個、青玉を0個から3個選ぶとします。合計nn個を選ぶ方法の個数は

(1+x+x2)(1+x+x2+x3)(1+x+x^2)(1+x+x^2+x^3)

のxnx^nの係数です。各因子で選んだ次数の和が合計個数を表します。

2 漸化式を方程式へ変える

フィボナッチ数列をF0=0,F1=1,Fn+2=Fn+1+FnF_0=0,F_1=1,F_{n+2}=F_{n+1}+F_nで定めます。

定理 2.1 (フィボナッチ数列の母関数). 形式的なべき級数F(x)=∑n≥0FnxnF(x)=\sum_{n\ge0}F_nx^nは

F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}

を満たします。

証明. 漸化式へxn+2x^{n+2}を掛けてn≥0n\ge0について足すと、

∑n≥0Fn+2xn+2=x∑n≥0Fn+1xn+1+x2∑n≥0Fnxn\sum_{n\ge0}F_{n+2}x^{n+2} =x\sum_{n\ge0}F_{n+1}x^{n+1} +x^2\sum_{n\ge0}F_nx^n

です。F0=0,F1=1F_0=0,F_1=1を用いると

F(x)−x=xF(x)+x2F(x)F(x)-x=xF(x)+x^2F(x)

なので、(1−x−x2)F(x)=x(1-x-x^2)F(x)=xを得ます。形式的べき級数1−x−x21-x-x^2の定数項は1なので逆数が存在し、結論を得ます。▨

3 一般項まで導く

α=(1+5)/2\alpha=(1+\sqrt5)/2、β=(1−5)/2\beta=(1-\sqrt5)/2とします。このとき1−x−x2=(1−αx)(1−βx)1-x-x^2=(1-\alpha x)(1-\beta x)です。

定理 3.1 (フィボナッチ数列の Binet 型公式). すべての非負整数nnについて、

Fn=αn−βn5F_n=\frac{\alpha^n-\beta^n}{\sqrt5}

が成り立ちます。

証明. 部分分数分解により

x(1−αx)(1−βx)=15(11−αx−11−βx)\frac{x}{(1-\alpha x)(1-\beta x)} =\frac1{\sqrt5}\left(\frac1{1-\alpha x}-\frac1{1-\beta x}\right)

です。形式的等比級数

11−cx=∑n≥0cnxn\frac1{1-cx}=\sum_{n\ge0}c^nx^n

を用いると、

F(x)=∑n≥0αn−βn5xn.F(x)=\sum_{n\ge0}\frac{\alpha^n-\beta^n}{\sqrt5}x^n.

同じ次数の係数を比較すると結論を得ます。▨

4 演習

  1. a0=1a_0=1、an+1=2ana_{n+1}=2a_nの母関数を求めます。
  2. 1/(1−x)21/(1-x)^2のxnx^nの係数がn+1n+1であることを、1/(1−x)1/(1-x)の形式的等比級数を二つ掛けて示します。
  3. フィボナッチ数列の母関数の証明で、初期条件がどの項に現れたかを説明します。
  4. a0=2a_0=2、an+1=3ana_{n+1}=3a_nで定める数列の通常母関数A(x)=∑n≥0anxnA(x)=\sum_{n\ge0}a_nx^nを求め、係数から一般項を示します。

1の答えは1/(1−2x)1/(1-2x)です。2では係数はi+j=ni+j=nを満たす非負整数の組の個数なのでn+1n+1です。3では左辺の添字をずらしたときにF0F_0とF1xF_1xが分離し、F0=0,F1=1F_0=0,F_1=1から左辺がF(x)−xF(x)-xになります。4では漸化式へxn+1x^{n+1}を掛けて足すとA(x)−2=3xA(x)A(x)-2=3xA(x)なので、A(x)=2/(1−3x)A(x)=2/(1-3x)です。形式的等比級数を用いるとA(x)=2∑n≥03nxnA(x)=2\sum_{n\ge0}3^nx^nなので、an=2⋅3na_n=2\cdot3^nです。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

母関数（数列 a_0, a_1, … を係数に並べた式 Σ\Sigma a_n xnx^n、確率変数 X に対しては G(s) == E[sXs^X] ==Σ\Sigma P(X ==k)skk)s^k）を用いて答えよ。G′(1) == E[X]、G″(1) == E[X(X−1)] を使ってよい。

数列 a_n は a_0 == 0、a_1 == 1、および n ≥\ge 2 で a_n == a_(n−1) + 2a_(n−2) を満たす。母関数 A(x) ==Σ\Sigma a_n xnx^n を求め、部分分数分解して一般項 a_n を求めよ。

解法の型選び方を因子に翻訳して掛け合わせ、xkx^k の係数を読む。独立な和の母関数は積。期待値は G′(1)、分散は G″(1) + G′(1) − G′(1)²

  1. 例題 1

    a0=0,a1=1,an=an−1+2an−2 (n≥2),A(x)=∑n≥0anxn= ?,an= ?a_0 = 0,\quad a_1 = 1,\quad a_n = a_{n-1} + 2a_{n-2} \ (n \ge 2),\qquad A(x) = \sum_{n \ge 0} a_n x^n = \ ?,\quad a_n = \ ?

演習

問題を解いてから「解答・解説」を開けます。

母関数（数列 a_0, a_1, … を係数に並べた式 Σ\Sigma a_n xnx^n、確率変数 X に対しては G(s) == E[sXs^X] ==Σ\Sigma P(X ==k)skk)s^k）を用いて答えよ。G′(1) == E[X]、G″(1) == E[X(X−1)] を使ってよい。

演習を読み込み中…

前提記事