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

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

難易度 3期末試験の応用レベル証明問題大学数学離散数学・組合せ論

数列 ${b_{n}}_{n \geq 0}$ を
$b_{0} = 1, b_{1} = 2, b_{n} = 3 b_{n - 1} - b_{n - 2} (n \geq 2)$
で定める。また、0 以上の整数 $n$ に対して
$a_{n} = k = 0 \sum n (2 k n + k)$
とおく。すべての 0 以上の整数 $n$ に対して $a_{n} = b_{n}$ が成り立つことを、母関数（有理数係数の形式的冪級数）を用いて証明せよ。

ただし、形式的冪級数環 $Q [[x]]$ において、0 以上の整数 $m$ に対する等式
$\frac{1}{( 1 - x ) ^{m + 1}} = j = 0 \sum \infty (m j + m) x^{j}$
が成り立つことと、定数項が $0$ でない形式的冪級数は $Q [[x]]$ で逆元をもつことは用いてよい。また、0 以上の整数 $p, r$ が $p < r$ を満たすときは $(r p) = 0$ と約束する。

この問題で使うもの

母関数と係数の取り出し（説明と入口の問題）
母関数による線形漸化式の解法（説明と入口の問題）
剰余の定理・因数定理と高次方程式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$A (x) = \sum a_{n} x^{n}$ と $B (x) = \sum b_{n} x^{n}$ が、同じ多項式を掛けると同じものになることを示す方針で考えます。 $B (x)$ のほうは漸化式から $(1 - 3 x + x^{2}) B (x)$ を直接計算できます。

ヒント 2

$k$ を固定して $\sum_{n} (2 k n + k) x^{n}$ を考えると、 $n = k + j$ とおけば与えられた等式から $\frac{x ^{k}}{( 1 - x ) ^{2 k + 1}}$ になります。これを $k$ について足すと $y = \frac{x}{( 1 - x ) ^{2}}$ の等比級数になります。

ヒント 3

$A (x) = \frac{1}{1 - x} \sum_{k \geq 0} y^{k}$ で、 $y$ は定数項 $0$ なので $\sum y^{k}$ は $(1 - y)^{- 1}$ に等しくなります。あとは $(1 - x) (1 - y)$ を整理して $(1 - 3 x + x^{2}) A (x)$ を求め、 $(1 - 3 x + x^{2}) B (x)$ と比べます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$k > n$ で $(2 k n + k) = 0$ となることに触れ、 $A (x) = \sum_{n} a_{n} x^{n}$ を $k$ ごとの級数の和に分けて（各係数が有限和であることを確認して）書き直している（2 点）
$k$ を固定した級数 $\sum_{n} (2 k n + k) x^{n}$ を、添字のずらし $n = k + j$ と与えられた等式で $\frac{x ^{k}}{( 1 - x ) ^{2 k + 1}}$ と計算している（2 点）
$y = \frac{x}{( 1 - x ) ^{2}}$ の定数項が 0 であることを根拠に、等比級数 $\sum_{k} y^{k} = (1 - y)^{- 1}$ を形式的冪級数として正しく扱い、 $(1 - 3 x + x^{2}) A (x) = 1 - x$ を導いている（3 点）
初期値と漸化式から $(1 - 3 x + x^{2}) B (x) = 1 - x$ を係数ごとに確認している（2 点）
$1 - 3 x + x^{2}$ が逆元をもつこと（または係数比較で同じ漸化式・初期値に帰着すること）から $A = B$ 、すなわち $a_{n} = b_{n}$ を結論している（1 点）

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

模範解答を読む

形式的冪級数環 $Q [[x]]$ で考える。 $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ 、 $B (x) = \sum_{n \geq 0} b_{n} x^{n}$ とおき、どちらも $(1 - 3 x + x^{2}) \times (その級数) = 1 - x$ を満たすことを示す。 $1 - 3 x + x^{2}$ は定数項が $1 \neq = 0$ なので逆元をもち、これから $A = B$ 、すなわち $a_{n} = b_{n}$ が従う。

なお、形式的冪級数の列 $F_{0}, F_{1}, F_{2}, \dots$ で $F_{k}$ が $x^{k}$ で割り切れる（ $k$ 次未満の係数がすべて $0$ ）とき、 $\sum_{k \geq 0} F_{k}$ の $x^{n}$ の係数は $k \leq n$ の有限個の $F_{k}$ の係数の和として定まる。この和は係数ごとの有限和なので、ほかの形式的冪級数 $G$ を掛けても $G \sum_{k} F_{k} = \sum_{k} G F_{k}$ が成り立つ（両辺の $x^{n}$ の係数はどちらも有限和 $\sum_{k \leq n}$ から計算され、一致する）。

ステップ 1: $a_{n}$ の和の範囲を広げる。 $k > n$ のとき $0 \leq n + k < 2 k$ なので約束により $(2 k n + k) = 0$ である。よって
$a_{n} = k \geq 0 \sum (2 k n + k)$
と書け、右辺は各 $n$ について有限和である。

ステップ 2: $k$ を固定した級数を計算する。 0 以上の整数 $k$ を固定し、 $C_{k} (x) = \sum_{n \geq 0} (2 k n + k) x^{n}$ とおく。 $n < k$ のとき $n + k < 2 k$ なので係数は $0$ である。 $n \geq k$ の項で $n = k + j$ （ $j \geq 0$ ）とおくと $n + k = 2 k + j$ なので、与えられた等式を $m = 2 k$ として用いて
$C_{k} (x) = j \geq 0 \sum (2 k j + 2 k) x^{k + j} = x^{k} j \geq 0 \sum (2 k j + 2 k) x^{j} = \frac{x ^{k}}{( 1 - x ) ^{2 k + 1}} .$

ステップ 3: $k$ について和をとる。 $C_{k} (x)$ は $x^{k}$ で割り切れるので、冒頭の注意により $\sum_{k \geq 0} C_{k} (x)$ は定まり、その $x^{n}$ の係数は $\sum_{k \geq 0} (2 k n + k) = a_{n}$ （ステップ 1）である。よって
$A (x) = k \geq 0 \sum \frac{x ^{k}}{( 1 - x ) ^{2 k + 1}} = k \geq 0 \sum \frac{1}{1 - x} y^{k} = \frac{1}{1 - x} k \geq 0 \sum y^{k}, y = \frac{x}{( 1 - x ) ^{2}} .$
ここで $y = x \cdot (1 - x)^{- 2}$ は定数項が $0$ の形式的冪級数で、 $y^{k}$ は $x^{k}$ で割り切れるので、最後の等号は冒頭の注意による。

ステップ 4: 等比級数の和。 $S = \sum_{k \geq 0} y^{k}$ とおく。各 $K \geq 0$ について $(1 - y) \sum_{k = 0}^{K} y^{k} = 1 - y^{K + 1}$ であり、 $y^{K + 1}$ と $(1 - y) \sum_{k > K} y^{k}$ はどちらも $x^{K + 1}$ で割り切れる。 $(1 - y) S = (1 - y) \sum_{k = 0}^{K} y^{k} + (1 - y) \sum_{k > K} y^{k}$ なので、 $(1 - y) S$ と $1$ の $K$ 次以下の係数は一致する。 $K$ は任意なので $(1 - y) S = 1$ である。

ステップ 5: $A (x)$ の満たす式。 ステップ 3, 4 より $(1 - x) (1 - y) A (x) = (1 - y) S = 1$ である。ここで
$(1 - x) (1 - y) = (1 - x) - \frac{x}{1 - x} = \frac{( 1 - x ) ^{2} - x}{1 - x} = \frac{1 - 3 x + x ^{2}}{1 - x}$
なので、両辺に $1 - x$ を掛けて
$(1 - 3 x + x^{2}) A (x) = 1 - x . (1)$

ステップ 6: $B (x)$ の満たす式。 $(1 - 3 x + x^{2}) B (x)$ の係数を計算すると、定数項は $b_{0} = 1$ 、 $x$ の係数は $b_{1} - 3 b_{0} = 2 - 3 = - 1$ 、 $n \geq 2$ のとき $x^{n}$ の係数は $b_{n} - 3 b_{n - 1} + b_{n - 2} = 0$ （漸化式）である。よって
$(1 - 3 x + x^{2}) B (x) = 1 - x . (2)$

ステップ 7: 結論。 $(1)$ , $(2)$ より $(1 - 3 x + x^{2}) (A (x) - B (x)) = 0$ 。 $1 - 3 x + x^{2}$ は定数項が $1 \neq = 0$ なので $Q [[x]]$ で逆元 $(1 - 3 x + x^{2})^{- 1}$ をもつ。これを両辺に掛けて $A (x) = B (x)$ 。形式的冪級数が等しいことは全係数が等しいことなので、すべての 0 以上の整数 $n$ に対して $a_{n} = b_{n}$ である。

（確認: $a_{0} = 1$ , $a_{1} = (0 1) + (2 2) = 2$ , $a_{2} = 1 + 3 + 1 = 5 = 3 \cdot 2 - 1 = b_{2}$ 。）

以上より、すべての 0 以上の整数 $n$ に対して $k = 0 \sum n (2 k n + k) = b_{n}$ が成り立つ。 $■$

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題