この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

離散数学・組合せ論の問題

難易度 1教科書の例題レベル大学数学離散数学・組合せ論

数列 ${a_{n}}_{n \geq 0}$ を
$a_{0} = 1, a_{n} = k = 1 \sum n k a_{n - k} (n \geq 1)$
で定める。無限級数
$n = 0 \sum \infty \frac{a _{n}}{4 ^{n}}$
は収束する。その和を求めよ。

この問題で使うもの

畳み込み型の漸化式と母関数の積（説明と入口の問題）

この問題を解けるようになるまで（61 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

技能「畳み込み型の漸化式と母関数の積」を使います。 $A (x) = \sum a_{n} x^{n}$ と $B (x) = \sum_{k \geq 1} k x^{k}$ を考えます。

ヒント 2

$\sum_{k = 1}^{n} k a_{n - k}$ は $B (x) A (x)$ の $x^{n}$ の係数です。定数項 $a_{0} = 1$ に注意すると $A (x) = 1 + B (x) A (x)$ となります。また $B (x) = \frac{x}{( 1 - x ) ^{2}}$ です。

ヒント 3

$A (x) = \frac{1}{1 - B ( x )} = \frac{( 1 - x ) ^{2}}{1 - 3 x + x ^{2}}$ です。収束半径は $\frac{3 - 5}{2} > \frac{1}{4}$ なので、 $x = \frac{1}{4}$ を代入できます。

答えと解説

答えを見る

\frac{9}{5}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

方針：母関数 $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ を考え、漸化式を母関数の積で表します。そのうえで $x = \frac{1}{4}$ を代入します。

1. 係数の列 $b_{k} = k$ の母関数

$∣ x ∣ < 1$ のとき $\frac{1}{1 - x} = \sum_{k = 0}^{\infty} x^{k}$ です。これを項別微分すると $\frac{1}{( 1 - x ) ^{2}} = \sum_{k = 1}^{\infty} k x^{k - 1}$ となります。両辺に $x$ を掛けて
$B (x) = k = 1 \sum \infty k x^{k} = \frac{x}{( 1 - x ) ^{2}} .$

2. 漸化式を母関数の式にする

$B (x) A (x)$ の $x^{n}$ の係数は、 $b_{0} = 0$ なので $\sum_{k = 1}^{n} k a_{n - k}$ です。
- $n \geq 1$ のとき、この係数は漸化式よりちょうど $a_{n}$ です。
- 定数項は $0$ です。

一方、 $A (x)$ の定数項は $a_{0} = 1$ です。よって
$A (x) = 1 + B (x) A (x)$
が成り立ち、
$A (x) = \frac{1}{1 - B ( x )} = \frac{( 1 - x ) ^{2}}{( 1 - x ) ^{2} - x} = \frac{( 1 - x ) ^{2}}{1 - 3 x + x ^{2}} .$

（確認）漸化式から $a_{1} = 1$ 、 $a_{2} = 1 \cdot a_{1} + 2 \cdot a_{0} = 3$ 、 $a_{3} = a_{2} + 2 a_{1} + 3 a_{0} = 8$ です。右辺を展開しても $1 + x + 3 x^{2} + 8 x^{3} + \dots$ となり、一致します。

3. 収束半径の確認

分母 $1 - 3 x + x^{2} = 0$ の解は $x = \frac{3 \pm 5}{2}$ です。分子 $(1 - x)^{2}$ はこれらの点で $0$ にならないので、分母と約分されません。よって $A (x)$ のべき級数の収束半径は、原点に近いほうの解までの距離
$\frac{3 - 5}{2} \approx 0.382$
です。 $x_{0} = \frac{1}{4} = 0.25$ はこの内側にあるので、級数は収束し、その和は $A (\frac{1}{4})$ に等しくなります。

4. 代入

$n = 0 \sum \infty \frac{a _{n}}{4 ^{n}} = A (\frac{1}{4}) = \frac{( \frac{3}{4} ) ^{2}}{1 - \frac{3}{4} + \frac{1}{16}} = \frac{\frac{9}{16}}{\frac{5}{16}} = \frac{9}{5} .$

（別の計算） $B (\frac{1}{4}) = \frac{1/4}{( 3/4 ) ^{2}} = \frac{4}{9}$ なので、 $A (\frac{1}{4}) = \frac{1}{1 - \frac{4}{9}} = \frac{9}{5}$ としても求められます。

答え： $\frac{9}{5}$

別解

$A (x) = \sum_{n \geq 0} a_{n} x^{n}$ とおく。漸化式 $a_{n} = \sum_{k = 1}^{n} k a_{n - k}$ $(n \geq 1)$ と $a_{0} = 1$ から、 $A (x) = 1 + K (x) A (x)$ が成り立つ。ここで $K (x) = \sum_{k \geq 1} k x^{k} = \frac{x}{( 1 - x ) ^{2}}$ である。

よって
$A (x) = \frac{1}{1 - K ( x )} = \frac{( 1 - x ) ^{2}}{( 1 - x ) ^{2} - x} = \frac{( 1 - x ) ^{2}}{1 - 3 x + x ^{2}} .$

分母の根は $x = \frac{3 \pm 5}{2}$ で、原点に最も近い根は $\frac{3 - 5}{2} \approx 0.382$ である。 $A (x)$ は有理関数なので収束半径はこの値になり、 $x = \frac{1}{4} < 0.382$ では級数は収束する。

$x = \frac{1}{4}$ を代入すると
$A (\frac{1}{4}) = \frac{( 3/4 ) ^{2}}{1 - 3/4 + 1/16} = \frac{9/16}{5/16} = \frac{9}{5} .$

検算として、 $a_{0}, \dots, a_{5} = 1, 1, 3, 8, 21, 55$ を使い第 5 項までの部分和を求めると約 $1.698$ になる。以降の項は公比が約 $0.65$ の等比的に減少し、残りの和は約 $0.1$ なので、全体は約 $1.8$ となり $\frac{9}{5}$ と一致する。

離散数学・組合せ論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題