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

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

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

0 以上の整数 $n$ に対して、数列 ${a_{n}}$ を
$a_{0} = 2, a_{1} = 5, a_{n} = 5 a_{n - 1} - 6 a_{n - 2} (n \geq 2)$
で定める。母関数 $A (x) = n = 0 \sum \infty a_{n} x^{n}$ を $x$ の有理式で表し、部分分数分解することで、一般項 $a_{n}$ を $n$ の式で求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

母関数による線形漸化式の解法を使います。漸化式の両辺に $x^{n}$ を掛けて $n \geq 2$ で和をとり、 $A (x)$ の式を作りましょう。

ヒント 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)$ と書き換えられます。

ヒント 3

整理すると $A (x) (1 - 5 x + 6 x^{2}) = 2 - 5 x$ 、つまり $A (x) = \frac{2 - 5 x}{( 1 - 2 x ) ( 1 - 3 x )}$ となります。これを $\frac{α}{1 - 2 x} + \frac{β}{1 - 3 x}$ の形に分解しましょう。

答えと解説

答えを見る

2^{n} + 3^{n}

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

解説を読む

手順 1：漸化式に $x^{n}$ を掛けて和をとる。

漸化式 $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ の両辺に $x^{n}$ を掛け、 $n \geq 2$ について和をとると
$n = 2 \sum \infty a_{n} x^{n} = 5 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 - 5 x$
右辺の第 1 項： $n = 2 \sum \infty a_{n - 1} x^{n} = x m = 1 \sum \infty a_{m} x^{m} = x (A (x) - 2)$
右辺の第 2 項： $n = 2 \sum \infty a_{n - 2} x^{n} = x^{2} m = 0 \sum \infty a_{m} x^{m} = x^{2} A (x)$

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

手順 3： $A (x)$ について解く。

$A (x)$ を含む項を左辺に集めると
$A (x) (1 - 5 x + 6 x^{2}) = 2 + 5 x - 10 x = 2 - 5 x .$
$1 - 5 x + 6 x^{2} = (1 - 2 x) (1 - 3 x)$ と因数分解できるので
$A (x) = \frac{2 - 5 x}{( 1 - 2 x ) ( 1 - 3 x )} .$

手順 4：部分分数分解する。

$\frac{2 - 5 x}{( 1 - 2 x ) ( 1 - 3 x )} = \frac{α}{1 - 2 x} + \frac{β}{1 - 3 x}$
とおき、分母を払うと $2 - 5 x = α (1 - 3 x) + β (1 - 2 x)$ 。係数を比べて
$α + β = 2, 3 α + 2 β = 5.$
これを解くと $α = 1, β = 1$ 。したがって
$A (x) = \frac{1}{1 - 2 x} + \frac{1}{1 - 3 x} .$

手順 5：係数を取り出す。

無限等比級数の和の公式 $\frac{1}{1 - r x} = n = 0 \sum \infty r^{n} x^{n}$ （ $∣ r x ∣ < 1$ ）より
$A (x) = n = 0 \sum \infty (2^{n} + 3^{n}) x^{n} .$
$x^{n}$ の係数を比べて
$a_{n} = 2^{n} + 3^{n} .$

確認： $a_{0} = 1 + 1 = 2$ 、 $a_{1} = 2 + 3 = 5$ 、 $a_{2} = 4 + 9 = 13$ であり、漸化式からも $a_{2} = 5 \cdot 5 - 6 \cdot 2 = 13$ となって一致する。

別解

漸化式から $A (x) - a_{0} - a_{1} x = 5 x (A (x) - a_{0}) - 6 x^{2} A (x)$ が成り立つ。
$(1 - 5 x + 6 x^{2}) A (x) = a_{0} + a_{1} x - 5 a_{0} x = 2 + 5 x - 10 x = 2 - 5 x$ 。
よって $A (x) = \frac{2 - 5 x}{( 1 - 2 x ) ( 1 - 3 x )}$ 。
部分分数分解して $\frac{2 - 5 x}{( 1 - 2 x ) ( 1 - 3 x )} = \frac{P}{1 - 2 x} + \frac{Q}{1 - 3 x}$ とおく。
$2 - 5 x = P (1 - 3 x) + Q (1 - 2 x)$ 。 $x = 1/2$ を代入すると $- 1/2 = P (- 1/2)$ より $P = 1$ 。 $x = 1/3$ を代入すると $1/3 = Q (1/3)$ より $Q = 1$ 。
よって $A (x) = \frac{1}{1 - 2 x} + \frac{1}{1 - 3 x} = \sum (2^{n} + 3^{n}) x^{n}$ 。
ゆえに $a_{n} = 2^{n} + 3^{n}$ 。
検算: $a_{0} = 2$ , $a_{1} = 5$ , $a_{2} = 4 + 9 = 13 = 5 \cdot 5 - 6 \cdot 2 = 13$ 。 $a_{3} = 8 + 27 = 35 = 5 \cdot 13 - 6 \cdot 5 = 35$ 。一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題