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

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

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

0 以上の整数 $n$ に対して、数列 ${a_{n}}$ を
$a_{0} = 2, a_{1} = 1, a_{n} = a_{n - 1} + 6 a_{n - 2} (n \geq 2)$
で定める。母関数 $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ を用いて、一般項 $a_{n}$ を $n$ の式で求めよ。

この問題で使うもの

母関数による線形漸化式の解法（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

母関数 $A (x) = \sum a_{n} x^{n}$ を使う技能（漸化式に $x^{n}$ を掛けて $n \geq 2$ で和をとる）を使いましょう。

ヒント 2

$\sum_{n \geq 2} a_{n} x^{n} = A (x) - a_{0} - a_{1} x$ 、 $\sum_{n \geq 2} a_{n - 1} x^{n} = x (A (x) - a_{0})$ 、 $\sum_{n \geq 2} a_{n - 2} x^{n} = x^{2} A (x)$ を使うと、 $A (x)$ の 1 次方程式が得られます。

ヒント 3

$(1 - x - 6 x^{2}) A (x) = 2 - x$ より $A (x) = \frac{2 - x}{( 1 - 3 x ) ( 1 + 2 x )}$ です。これを $\frac{α}{1 - 3 x} + \frac{β}{1 + 2 x}$ と部分分数分解しましょう。

答えと解説

答えを見る

3^{n} + (- 2)^{n}

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

解説を読む

母関数による線形漸化式の解法を使います。

手順 1：漸化式に $x^{n}$ を掛けて和をとる。
漸化式 $a_{n} = a_{n - 1} + 6 a_{n - 2}$ の両辺に $x^{n}$ を掛け、 $n \geq 2$ について和をとると
$n = 2 \sum \infty a_{n} x^{n} = n = 2 \sum \infty a_{n - 1} x^{n} + 6 n = 2 \sum \infty a_{n - 2} x^{n} .$

手順 2：各和を $A (x)$ で表す。
- 左辺： $n = 2 \sum \infty a_{n} x^{n} = A (x) - a_{0} - a_{1} x = A (x) - 2 - x$
- 右辺第 1 項： $n = 2 \sum \infty a_{n - 1} x^{n} = x m = 1 \sum \infty a_{m} x^{m} = x (A (x) - a_{0}) = x (A (x) - 2)$
- 右辺第 2 項： $6 n = 2 \sum \infty a_{n - 2} x^{n} = 6 x^{2} m = 0 \sum \infty a_{m} x^{m} = 6 x^{2} A (x)$

よって
$A (x) - 2 - x = x A (x) - 2 x + 6 x^{2} A (x) .$

手順 3： $A (x)$ を有理式で表す。
$A (x)$ を含む項を左辺に集めると
$(1 - x - 6 x^{2}) A (x) = 2 + x - 2 x = 2 - x .$
$1 - x - 6 x^{2} = (1 - 3 x) (1 + 2 x)$ と因数分解できるので
$A (x) = \frac{2 - x}{( 1 - 3 x ) ( 1 + 2 x )} .$

手順 4：部分分数分解する。
$\frac{2 - x}{( 1 - 3 x ) ( 1 + 2 x )} = \frac{α}{1 - 3 x} + \frac{β}{1 + 2 x}$
とおき、分母を払うと
$α (1 + 2 x) + β (1 - 3 x) = 2 - x .$
両辺の係数を比べると
$α + β = 2, 2 α - 3 β = - 1.$
$β = 2 - α$ を代入すると $2 α - 6 + 3 α = - 1$ より $5 α = 5$ です。よって $α = 1, β = 1$ となり
$A (x) = \frac{1}{1 - 3 x} + \frac{1}{1 + 2 x} .$

手順 5：等比級数に展開して係数を読む。
$∣ x ∣$ が十分小さいとき
$\frac{1}{1 - 3 x} = n = 0 \sum \infty 3^{n} x^{n}, \frac{1}{1 + 2 x} = n = 0 \sum \infty (- 2)^{n} x^{n}$
です。 $x^{n}$ の係数を比べると
$a_{n} = 3^{n} + (- 2)^{n} .$

検算
- $a_{0} = 1 + 1 = 2$ 、 $a_{1} = 3 - 2 = 1$ で、初期条件に一致します。
- 漸化式から $a_{2} = 1 + 6 \cdot 2 = 13$ です。式からは $9 + 4 = 13$ となり、一致します。
- 漸化式から $a_{3} = 13 + 6 \cdot 1 = 19$ です。式からは $27 - 8 = 19$ となり、一致します。

別解

漸化式 $a_{n} = a_{n - 1} + 6 a_{n - 2}$ $(n \geq 2)$ の両辺に $x^{n}$ を掛けて $n \geq 2$ で和をとると、
$A (x) - a_{0} - a_{1} x = x (A (x) - a_{0}) + 6 x^{2} A (x)$ 。
$a_{0} = 2, a_{1} = 1$ を代入して $(1 - x - 6 x^{2}) A (x) = 2 + x - 2 x = 2 - x$ 。
よって $A (x) = \frac{2 - x}{1 - x - 6 x ^{2}} = \frac{2 - x}{( 1 - 3 x ) ( 1 + 2 x )}$ 。
部分分数分解を $\frac{2 - x}{( 1 - 3 x ) ( 1 + 2 x )} = \frac{p}{1 - 3 x} + \frac{q}{1 + 2 x}$ とおく。
$p (1 + 2 x) + q (1 - 3 x) = 2 - x$ 。
$x = 1/3$ のとき $p \cdot \frac{5}{3} = \frac{5}{3}$ より $p = 1$ 。
$x = - 1/2$ のとき $q \cdot \frac{5}{2} = \frac{5}{2}$ より $q = 1$ 。
よって $A (x) = \frac{1}{1 - 3 x} + \frac{1}{1 + 2 x}$ となり、 $a_{n} = 3^{n} + (- 2)^{n}$ 。
検算： $a_{0} = 2$ 、 $a_{1} = 3 - 2 = 1$ 、 $a_{2} = 9 + 4 = 13$ であり、漸化式から $a_{2} = a_{1} + 6 a_{0} = 1 + 12 = 13$ で一致。 $a_{3} = 27 - 8 = 19$ で、 $a_{2} + 6 a_{1} = 13 + 6 = 19$ で一致。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題