畳み込み型の漸化式と母関数の積

$a_{n} = \sum_{k = 1}^{n} b_{k} a_{n - k}$ を $A (x) = 1 + B (x) A (x)$ と母関数の積で表して $A (x) = \frac{1}{1 - B ( x )}$ を求め、収束半径の内側の $x_{0}$ を代入して $\sum a_{n} x_{0}^{n}$ の値を求められる（例: $B (x) = \sum k^{2} x^{k} = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}$ ）

前提

母関数と係数の取り出し（大学数学離散数学・組合せ論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学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 極限）
べき級数と収束半径（大学数学微分積分）
母関数と係数の取り出し（大学数学離散数学・組合せ論）

説明

各項が、それまでのすべての項に重み $b_{k}$ を掛けて足し合わせた形で決まる漸化式 $a_{n} = \sum_{k = 1}^{n} b_{k} a_{n - k}$ （畳み込み型）を、1 項ずつ計算せずにまとめて扱う方法です。母関数 $A (x) = \sum a_{n} x^{n}$ と $B (x) = \sum b_{k} x^{k}$ を使うと、漸化式全体が $A (x) = 1 + B (x) A (x)$ という 1 本の式になり、 $A (x) = \frac{1}{1 - B ( x )}$ が得られます。さらに、級数が収束する $x_{0}$ を代入すれば、無限級数 $\sum a_{n} x_{0}^{n}$ の値がすぐに求まります。「最初の部分が $k$ 個で重み $b_{k}$ 、残りは元と同じ問題」という分け方をする数え上げでよく現れる形です。

なぜそうしてよいのか

鍵になるのは、「2 つのべき級数の積の $x^{n}$ の係数は、係数の畳み込みになる」ことです。定数項が $0$ の $B (x) = \sum_{k \geq 1} b_{k} x^{k}$ と $A (x) = \sum_{m \geq 0} a_{m} x^{m}$ を掛けます。 $x^{n}$ の項は $x^{k} \cdot x^{n - k}$ の組から出てくるので、 $[x^{n}] B (x) A (x) = \sum_{k = 1}^{n} b_{k} a_{n - k}$ となります（ $b_{0} = 0$ なので $k = 0$ の項はありません）。これは漸化式の右辺そのものです。漸化式が成り立つのは $n \geq 1$ のときだけなので、 $A (x)$ の $n \geq 1$ の部分は $B (x) A (x)$ と一致し、残るのは定数項 $a_{0}$ だけです。したがって $A (x) = a_{0} + B (x) A (x)$ となり、 $a_{0} = 1$ なら $A (x) = 1 + B (x) A (x)$ 、つまり $A (x) = \frac{1}{1 - B ( x )}$ です。

数を代入するには、級数が収束していなければなりません。ここで注意したいのは、 $A$ の収束半径は前もってわからず、ふつうは $B$ の収束半径より小さいことです。例題の $B (x) = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}$ は半径 $1$ ですが、 $A$ は $1 - B (x) = 0$ となる $x \approx 0.28$ で分母が $0$ になるので、 $A$ の半径はそれ以下です。そこで、 $b_{k} \geq 0$ 、 $a_{0} > 0$ 、 $x_{0} > 0$ の場合に「 $x_{0}$ が $B$ の収束半径の内側にあり、かつ $B (x_{0}) < 1$ なら、 $\sum a_{n} x_{0}^{n}$ は収束して和は $\frac{a _{0}}{1 - B ( x _{0} )}$ になる」ことを直接示します。まず、帰納法により $a_{n} \geq 0$ です。部分和を $S_{N} = \sum_{n = 0}^{N} a_{n} x_{0}^{n}$ とおきます。漸化式を代入し、 $1 \leq k \leq n \leq N$ の組について $m = n - k$ とおいて和の順序を入れ替えると、
$S_{N} = a_{0} + n = 1 \sum N k = 1 \sum n b_{k} x_{0}^{k} a_{n - k} x_{0}^{n - k} = a_{0} + k = 1 \sum N b_{k} x_{0}^{k} m = 0 \sum N - k a_{m} x_{0}^{m} = a_{0} + k = 1 \sum N b_{k} x_{0}^{k} S_{N - k}$
となります。 $S_{N - k} \leq S_{N}$ なので $S_{N} \leq a_{0} + B (x_{0}) S_{N}$ 、すなわち $S_{N} \leq \frac{a _{0}}{1 - B ( x _{0} )}$ です。 $S_{N}$ は増加して上に有界なので、ある値 $S$ に収束し、 $S \leq \frac{a _{0}}{1 - B ( x _{0} )}$ です。

次に、逆向きの不等式を示します。 $M$ を固定し、 $N \geq M$ とします。上の式で $k \leq M$ の項だけを残すと $S_{N} \geq a_{0} + \sum_{k = 1}^{M} b_{k} x_{0}^{k} S_{N - k}$ です。ここで $N \to \infty$ とすると、各 $S_{N - k} \to S$ なので、 $S \geq a_{0} + B_{M} (x_{0}) S$ が得られます（ $B_{M} (x_{0}) = \sum_{k = 1}^{M} b_{k} x_{0}^{k}$ ）。さらに $M \to \infty$ とすると $S \geq a_{0} + B (x_{0}) S$ 、すなわち $S \geq \frac{a _{0}}{1 - B ( x _{0} )}$ です。両方の不等式から $S = \frac{a _{0}}{1 - B ( x _{0} )}$ となります。なお、符号が混じる場合は、 $\sum ∣ b_{k} ∣∣ x_{0} ∣^{k} < 1$ であれば、 $∣ b_{k} ∣$ で作った数列 $c_{n}$ （ $c_{0} = ∣ a_{0} ∣$ ）が帰納法で $∣ a_{n} ∣ \leq c_{n}$ を満たすので、 $\sum a_{n} x_{0}^{n}$ は絶対収束します。そのうえで、絶対収束する級数どうしの積がコーシー積（係数の畳み込みで並べた級数）の和に等しいことを使えば、同じ式が成り立ちます。

手順

$a_{0}$ と $b_{k}$ を確認し、 $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ 、 $B (x) = \sum_{k \geq 1} b_{k} x^{k}$ （定数項なし）とおく
漸化式の両辺に $x^{n}$ を掛けて $n \geq 1$ について足す。右辺が $B (x) A (x)$ になるので $A (x) = a_{0} + B (x) A (x)$ を得る
$A (x)$ について解き、 $A (x) = \frac{a _{0}}{1 - B ( x )}$ （ $a_{0} = 1$ なら $\frac{1}{1 - B ( x )}$ ）とする
$B (x)$ を閉じた式で表す（例： $\sum x^{k} = \frac{1}{1 - x}$ を微分して $x$ を掛ける操作をくり返すと、 $\sum k x^{k} = \frac{x}{( 1 - x ) ^{2}}$ 、 $\sum k^{2} x^{k} = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}$ ）
収束を確かめる。 $b_{k} \geq 0$ 、 $x_{0} > 0$ なら、 $x_{0}$ が $B$ の収束半径の内側にあり、かつ $B (x_{0}) < 1$ であることを確認する（ $A$ の半径は $B$ より小さくなりうるので、 $B (x_{0}) < 1$ の確認が必要）
$x_{0}$ を代入して $\sum a_{n} x_{0}^{n} = \frac{a _{0}}{1 - B ( x _{0} )}$ を計算する

例題

数列 ${a_{n}}$ を $a_{0} = 1$ 、 $n \geq 1$ に対して $a_{n} = \sum_{k = 1}^{n} k^{2} a_{n - k}$ で定める。無限級数 $\sum_{n = 0}^{\infty} \frac{a _{n}}{5 ^{n}}$ の値を求めよ。

例題の解答

【手順 1】 $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ 、 $B (x) = \sum_{k \geq 1} k^{2} x^{k}$ とおく。 $a_{0} = 1$ である。
【手順 2】 $n \geq 1$ では $[x^{n}] B (x) A (x) = \sum_{k = 1}^{n} k^{2} a_{n - k} = a_{n}$ なので、 $A (x) = 1 + B (x) A (x)$ となる。
【手順 3】 $A (x) = \frac{1}{1 - B ( x )}$ 。
【手順 4】 $∣ x ∣ < 1$ で $\sum_{k \geq 0} x^{k} = \frac{1}{1 - x}$ である。微分して $x$ を掛けると $\sum k x^{k} = \frac{x}{( 1 - x ) ^{2}}$ 。もう一度微分して $x$ を掛けると $\sum k^{2} x^{k} = x \cdot \frac{( 1 - x ) ^{2} + 2 x ( 1 - x )}{( 1 - x ) ^{4}} = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}$ 。よって $B (x) = \frac{x ( 1 + x )}{( 1 - x ) ^{3}}$ （収束半径 $1$ ）。
【手順 5】 $x_{0} = \frac{1}{5}$ は $B$ の収束半径 $1$ の内側にある。また $B (\frac{1}{5}) = \frac{\frac{1}{5} \cdot \frac{6}{5}}{( \frac{4}{5} ) ^{3}} = \frac{6}{25} \cdot \frac{125}{64} = \frac{15}{32} < 1$ である。 $b_{k} = k^{2} \geq 0$ 、 $a_{0} = 1 > 0$ 、 $x_{0} > 0$ なので、級数は収束し、和は $\frac{1}{1 - B ( x _{0} )}$ に等しい。
【手順 6】 $\sum_{n = 0}^{\infty} \frac{a _{n}}{5 ^{n}} = \frac{1}{1 - \frac{15}{32}} = \frac{32}{17}$ 。
（確認： $a_{1} = 1, a_{2} = 5, a_{3} = 18, a_{4} = 63$ なので、部分和は $1 + 0.2 + 0.2 + 0.144 + 0.1008 + \dots$ となり、 $\frac{32}{17} \approx 1.88$ に向かって増えていく。）

答え: $\frac{32}{17}$

よくある誤り

定数項を落として $A (x) = B (x) A (x)$ としてしまう誤り。漸化式は $n \geq 1$ でしか成り立たないので $n = 0$ の項 $a_{0}$ が残る。正しくは $A (x) = a_{0} + B (x) A (x)$ 。
$a_{0}$ が $1$ でないのに $A (x) = \frac{1}{1 - B ( x )}$ を使ってしまう誤り。例えば $a_{0} = 3$ なら、正しくは $A (x) = \frac{3}{1 - B ( x )}$ 。
$B (x)$ に $k = 0$ の項を含めてしまう誤り。和は $k = 1$ から始まるので $B (x) = \sum_{k \geq 1} b_{k} x^{k}$ で、 $B (0) = 0$ である。 $b_{k} = k^{2}$ なら $k = 0$ の項は $0$ なので影響はないが、 $b_{k} = k + 1$ では正しくは $B (x) = \sum_{k \geq 1} (k + 1) x^{k} = \frac{1}{( 1 - x ) ^{2}} - 1$ と、 $k = 0$ の分を引く必要がある。
$B$ の収束半径の内側なら代入してよいと考えてしまう誤り。例題で $x_{0} = \frac{1}{2}$ は $B$ の半径 $1$ の内側だが、 $B (\frac{1}{2}) = \frac{\frac{1}{2} \cdot \frac{3}{2}}{\frac{1}{8}} = 6 > 1$ である。このとき $\frac{1}{1 - 6} = - \frac{1}{5}$ が出てくるが、正の項の級数 $\sum \frac{a _{n}}{2 ^{n}}$ は発散しており、この値は和ではない。正しくは $B (x_{0}) < 1$ も確かめる。

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

畳み込み型の漸化式と母関数の積

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題