漸化式と母関数 ― 数列を「関数」にすると何が見えるか

母関数は数列の「名刺」です．掛け算が畳み込みになること，フィボナッチ数列の閉じた形（ビネの公式）が母関数から自然に導かれることを解説します．漸化式を解く強力な手段としての母関数を体験してください．

2026年2月27日

漸化式を立てたはいいものの，一般項が求められない ― そんな経験はありませんか？ 母関数（generating function）は，数列を1つの関数にまとめることで，漸化式を「代数方程式」に変換してしまう魔法のような道具です．

1 母関数とは ― 数列の名刺

定義 1 (通常型母関数).

数列

{a_{n}}_{n = 0}^{\infty}

の通常型母関数（OGF: Ordinary Generating Function）とは，形式的べき級数

A (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots

のことです．

注意 2.

「形式的」とは，収束を気にしないということです．

x

は具体的な値を代入するための変数ではなく，係数

a_{n}

を整理して並べるための「棚」のようなものです．この割り切りが母関数の使いやすさの源です．

2 基本的な母関数

例 3 (等比級数).

数列

a_{n} = 1

（

n \geq 0

）の母関数は

n = 0 \sum \infty x^{n} = \frac{1}{1 - x}

です．等比級数の和の公式そのものです．

例 4 (

(1 + x)^{n}

と二項係数).

数列

a_{k} = (k n)

（

k = 0, 1, \dots, n

，それ以上は

0

）の母関数は

k = 0 \sum n (k n) x^{k} = (1 + x)^{n}

です．これは二項定理の

y = 1

の場合です．

3 掛け算＝畳み込みの意味

母関数の最も強力な性質は，積が畳み込みに対応することです．

定理 5 (母関数の積と畳み込み).

A (x) = \sum a_{n} x^{n}

と

B (x) = \sum b_{n} x^{n}

の積

C (x) = A (x) B (x)

の係数は

c_{n} = k = 0 \sum n a_{k} b_{n - k}

つまり

{a_{n}}

と

{b_{n}}

の畳み込み（convolution）です．

注意 6.

畳み込みが自然に現れるのは「2段階の選択」を行う場面です．例えば，

a_{k}

を「硬貨の組合せで

k

円を作る方法の数」，

b_{j}

を「紙幣の組合せで

j

円を作る方法の数」とすると，

c_{n} = \sum_{k} a_{k} b_{n - k}

は「硬貨と紙幣で合計

n

円を作る方法の数」です．母関数では

C (x) = A (x) B (x)

と掛けるだけで済みます．

4 フィボナッチ数列の母関数

定義 7 (フィボナッチ数列).

F_{0} = 0

，

F_{1} = 1

，

F_{n} = F_{n - 1} + F_{n - 2}

（

n \geq 2

）で定義される数列をフィボナッチ数列と呼びます．

母関数 $F (x) = \sum_{n = 0}^{\infty} F_{n} x^{n}$ を漸化式から求めましょう．

定理 8.

フィボナッチ数列の母関数は

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

です．

証明.

F_{n} = F_{n - 1} + F_{n - 2}

の両辺に

x^{n}

を掛けて

n \geq 2

で和を取ります：

n = 2 \sum \infty F_{n} x^{n} = n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n}

左辺は

F (x) - F_{0} - F_{1} x = F (x) - x

です．右辺の第1項は

x (F (x) - F_{0}) = x F (x)

，第2項は

x^{2} F (x)

です．

よって

F (x) - x = x F (x) + x^{2} F (x)

を解いて

F (x) = x / (1 - x - x^{2})

です． □

5 ビネの公式 ― 母関数から一般項へ

$F (x) = x / (1 - x - x^{2})$ を部分分数分解します． $1 - x - x^{2} = - (x - α) (x - β)$ と因数分解すると（ここで $α, β$ は $x^{2} + x - 1 = 0$ の根），

α = \frac{- 1 + 5}{2}, β = \frac{- 1 - 5}{2}

部分分数分解と等比級数展開から，

定理 9 (ビネの公式).

F_{n} = \frac{1}{5} [(\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}]

注意 10.

整数列

F_{n}

の一般項に

5

が現れるのは驚きです．しかし

(1 - 5) /2

の絶対値は1未満なので

n \to \infty

で消え，

F_{n}

は黄金比

φ = (1 + 5) /2

の

n

乗にほぼ等しくなります．具体的には

F_{n} = ⌊ φ^{n} / 5 + 1/2 ⌋

です．

6 漸化式を解く手段としての母関数

母関数による漸化式の解法は，以下のパターンに集約されます：

漸化式の両辺に $x^{n}$ を掛けて和を取る
既知の母関数 $A (x)$ について代数方程式を立てる
$A (x)$ を閉じた形で求める
部分分数分解や既知の展開を使って係数 $a_{n}$ を読み取る

注意 11.

この手順は「漸化式（離散の世界）を代数方程式（連続の世界）に翻訳し，連続の世界で解いてから離散に戻す」というものです．母関数は離散と連続の架け橋です．

7 まとめ

母関数は数列を形式的べき級数にまとめたもの（数列の「名刺」）です
母関数の積は畳み込みに対応し，多段階の数え上げを自動化します
フィボナッチ数列の母関数は $x / (1 - x - x^{2})$ で，ビネの公式が導かれます
漸化式を代数方程式に変換して解くのが母関数の基本戦略です

次の記事では，母関数から自然に現れるカタラン数の不思議な遍在性について解説します．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

1 母関数とは ― 数列の名刺

2 基本的な母関数

3 掛け算＝畳み込みの意味

4 フィボナッチ数列の母関数

5 ビネの公式 ― 母関数から一般項へ

6 漸化式を解く手段としての母関数

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

素数の分布 ― 素数定理への道