母関数による線形漸化式の解法

$a_{n} = 3 a_{n - 1} + 2^{n}$ のような定数係数線形漸化式の両辺に $x^{n}$ を掛けて和をとり、母関数 $A (x)$ を有理式で表して部分分数分解し、一般項 $a_{n}$ を求められる

前提

母関数と係数の取り出し（大学数学離散数学・組合せ論）
分数関数の積分（部分分数分解）（数学III 積分法）

この技能までの道筋（63 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）
無限等比級数と無限級数（数学III 極限）
べき級数と収束半径（大学数学微分積分）
母関数と係数の取り出し（大学数学離散数学・組合せ論）
多項式の不定積分（数学II 微分法と積分法）
基本的な関数の不定積分（数学III 積分法）
分数関数の積分（部分分数分解）（数学III 積分法）

説明

定数係数の線形漸化式（例: $a_{n} = 3 a_{n - 1} + 2^{n}$ 、 $a_{n} = a_{n - 1} + 6 a_{n - 2}$ ）から一般項 $a_{n}$ を求める方法です。数列全体を1つの関数 $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ （母関数）にまとめると、漸化式は $A (x)$ についての1次方程式になります。これを解くと $A (x)$ は有理式になるので、部分分数分解して各項を等比級数に展開すれば、 $x^{n}$ の係数として $a_{n}$ が読み取れます。特殊解の形を推測する必要がなく、手順が機械的に決まるのが長所です。

なぜそうしてよいのか

鍵は「添字のずれ」が「 $x$ を掛けること」に変わる点です。 $A (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots$ に $x$ を掛けると $x A (x) = a_{0} x + a_{1} x^{2} + \dots$ となり、 $x^{n}$ の係数は $a_{n - 1}$ です。つまり $\sum_{n \geq 1} a_{n - 1} x^{n} = x A (x)$ 、同様に $\sum_{n \geq 2} a_{n - 2} x^{n} = x^{2} A (x)$ です。また $\sum_{n \geq 1} a_{n} x^{n} = A (x) - a_{0}$ のように、初めの数項を引けば和の範囲の違いも $A (x)$ で表せます。さらに $\sum_{n \geq 0} r^{n} x^{n} = \frac{1}{1 - r x}$ （無限等比級数）なので、 $2^{n}$ のような項も有理式になります。よって漸化式の両辺に $x^{n}$ を掛けて足し合わせると $A (x)$ の1次方程式が得られ、 $A (x) = \frac{P ( x )}{Q ( x )}$ （ $P, Q$ は多項式）と解けます。

分母の形も決まっています。 $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ なら、 $A (x)$ の係数は $1 - c_{1} x - \dots - c_{k} x^{k}$ となり、これに非斉次項（ $2^{n}$ なら $1 - 2 x$ ）の分母が掛かります。 $1 - c_{1} x - \dots - c_{k} x^{k}$ は特性多項式 $χ (t) = t^{k} - c_{1} t^{k - 1} - \dots - c_{k}$ の係数を逆順に並べたもので、 $x^{k} χ (1/ x)$ に等しいです。 $χ (t) = (t - r_{1}) \dots (t - r_{k})$ と因数分解できれば $x^{k} χ (1/ x) = (1 - r_{1} x) \dots (1 - r_{k} x)$ となり、欲しい $(1 - r x)$ 型の因数がそのまま得られます。例えば $t^{2} - t - 6 = (t - 3) (t + 2)$ から $1 - x - 6 x^{2} = (1 - 3 x) (1 + 2 x)$ です。

係数の取り出しには部分分数分解を使います。 $\frac{c}{1 - r x} = \sum_{n \geq 0} c r^{n} x^{n}$ なので $x^{n}$ の係数は $c r^{n}$ 、重なった因数には前提の公式で $y = r x$ とおいた $[x^{n}] \frac{1}{( 1 - r x ) ^{k}} = (k - 1 n + k - 1) r^{n}$ を使います。ただし部分分数分解は分子の次数が分母より低いときの操作なので、 $de g P \geq de g Q$ なら先に割り算 $P = S Q + R$ （ $de g R < de g Q$ ）をして $A (x) = S (x) + \frac{R ( x )}{Q ( x )}$ とします。多項式 $S (x)$ は $n \leq de g S$ の係数にしか効きません。これらの変形が正しいのは、漸化式から $∣ a_{n} ∣ \leq C M^{n}$ （ $C, M$ は定数）となり $A (x)$ が $∣ x ∣ < \frac{1}{M}$ で収束し、 $x = 0$ の近くで等しい2つのべき級数は係数がすべて一致する（テイラー展開の一意性）からです。

手順

母関数を $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ とおく。
漸化式が成り立つ範囲（例: $n \geq 1$ ）で両辺に $x^{n}$ を掛けて和をとり、各和を $A (x)$ で書き直す: $\sum_{n \geq 1} a_{n} x^{n} = A (x) - a_{0}$ 、 $\sum_{n \geq 1} a_{n - 1} x^{n} = x A (x)$ 、 $\sum_{n \geq 1} r^{n} x^{n} = \frac{r x}{1 - r x}$ など。
得られた1次方程式を解き、 $A (x) = \frac{P ( x )}{Q ( x )}$ の形にする。 $de g P \geq de g Q$ なら割り算で $A (x) = S (x) + \frac{R ( x )}{Q ( x )}$ （ $de g R < de g Q$ ）と多項式部分 $S (x)$ を分離しておく。
分母を $(1 - r x)$ 型の因数に分解する。 $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ から来る部分 $1 - c_{1} x - \dots - c_{k} x^{k}$ は、特性多項式 $t^{k} - c_{1} t^{k - 1} - \dots - c_{k}$ の係数を逆順にしたもの。その根 $r_{i}$ を求めれば $\prod (1 - r_{i} x)$ と書ける（例: $t^{2} - t - 6 = (t - 3) (t + 2)$ より $1 - x - 6 x^{2} = (1 - 3 x) (1 + 2 x)$ ）。
部分分数分解する。重なった因数 $(1 - r x)^{k}$ には $\frac{1}{1 - r x}, \dots, \frac{1}{( 1 - r x ) ^{k}}$ の項をすべて用意する。
各項の $x^{n}$ の係数を読む: $[x^{n}] \frac{c}{1 - r x} = c r^{n}$ 、 $[x^{n}] \frac{1}{( 1 - r x ) ^{k}} = (k - 1 n + k - 1) r^{n}$ 。最後に $n = 0, 1, 2$ を代入し、漸化式から直接計算した値と一致するか確かめる。

例題

数列 ${a_{n}}$ （ $n$ は 0 以上の整数）が $a_{0} = 1$ 、 $a_{n} = 3 a_{n - 1} + 2^{n}$ （ $n \geq 1$ ）を満たすとき、一般項 $a_{n}$ を求めよ。

例題の解答

【手順1】 $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ とおく。
【手順2】漸化式は $n \geq 1$ で成り立つので、両辺に $x^{n}$ を掛けて $n \geq 1$ で和をとる:
$n \geq 1 \sum a_{n} x^{n} = 3 n \geq 1 \sum a_{n - 1} x^{n} + n \geq 1 \sum 2^{n} x^{n} .$
左辺は $A (x) - 1$ 、右辺第1項は $3 x A (x)$ 、第2項は $\frac{1}{1 - 2 x} - 1 = \frac{2 x}{1 - 2 x}$ 。よって $A (x) - 1 = 3 x A (x) + \frac{2 x}{1 - 2 x}$ 。
【手順3】 $(1 - 3 x) A (x) = 1 + \frac{2 x}{1 - 2 x} = \frac{1}{1 - 2 x}$ より $A (x) = \frac{1}{( 1 - 2 x ) ( 1 - 3 x )}$ 。分子は定数（0次）、分母は2次なので多項式部分はない。
【手順4】分母のうち $1 - 3 x$ は漸化式 $a_{n} = 3 a_{n - 1}$ の部分（特性多項式 $t - 3$ の係数を逆順にしたもの）、 $1 - 2 x$ は非斉次項 $2^{n}$ から来た因数で、すでに $(1 - r x)$ 型に分解されている。
【手順5】 $\frac{1}{( 1 - 2 x ) ( 1 - 3 x )} = \frac{α}{1 - 3 x} + \frac{β}{1 - 2 x}$ とおくと $1 = α (1 - 2 x) + β (1 - 3 x)$ 。 $x = \frac{1}{3}$ を代入して $α = 3$ 、 $x = \frac{1}{2}$ を代入して $1 = - \frac{β}{2}$ より $β = - 2$ 。よって $A (x) = \frac{3}{1 - 3 x} - \frac{2}{1 - 2 x}$ 。
【手順6】 $x^{n}$ の係数を読むと $a_{n} = 3 \cdot 3^{n} - 2 \cdot 2^{n} = 3^{n + 1} - 2^{n + 1}$ 。確認: $a_{0} = 3 - 2 = 1$ 、 $a_{1} = 9 - 4 = 5$ （漸化式: $3 \cdot 1 + 2 = 5$ ）、 $a_{2} = 27 - 8 = 19$ （漸化式: $3 \cdot 5 + 4 = 19$ ）で一致する。
答え: $a_{n} = 3^{n + 1} - 2^{n + 1}$

答え: $3^{n + 1} - 2^{n + 1}$

よくある誤り

漸化式が $n \geq 1$ でしか成り立たないのに、左辺の和 $\sum_{n \geq 1} a_{n} x^{n}$ を $A (x)$ としてしまう誤り。正しくは $\sum_{n \geq 1} a_{n} x^{n} = A (x) - a_{0}$ で、初期値の分を引く（3項間で $n \geq 2$ なら $A (x) - a_{0} - a_{1} x$ ）。
$\sum_{n \geq 1} 2^{n} x^{n}$ を $\frac{1}{1 - 2 x}$ としてしまう誤り。 $\frac{1}{1 - 2 x}$ は $n = 0$ の項 $1$ を含むので、正しくは $\sum_{n \geq 1} 2^{n} x^{n} = \frac{1}{1 - 2 x} - 1 = \frac{2 x}{1 - 2 x}$ 。
$Q (x) = 1 - x - 6 x^{2}$ の根 $x = \frac{1}{3}, - \frac{1}{2}$ をそのまま公比と思い、 $a_{n}$ に $(\frac{1}{3})^{n}$ が現れてしまう誤り。公比は $Q$ の根の逆数、つまり特性多項式 $t^{2} - t - 6$ の根 $3, - 2$ で、 $Q (x) = (1 - 3 x) (1 + 2 x)$ と $(1 - r x)$ 型に直してから $[x^{n}] \frac{c}{1 - r x} = c r^{n}$ を読む。
$de g P \geq de g Q$ のまま多項式部分を落として係数を読む誤り。例えば $A (x) = \frac{x ^{2}}{1 - x}$ を「 $\frac{1}{1 - x}$ 型だから $a_{n} = 1$ 」としてはいけない。正しくは割り算して $A (x) = - 1 - x + \frac{1}{1 - x}$ とし、 $a_{0} = a_{1} = 0$ 、 $n \geq 2$ で $a_{n} = 1$ 。部分分数から得た式は $n > de g S$ でのみ全項を表す。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

母関数による線形漸化式の解法

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題