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

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

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

カタラン数 $C_{0}, C_{1}, C_{2}, \dots$ を
$C_{0} = 1, C_{n + 1} = i = 0 \sum n C_{i} C_{n - i} (n は 0 以上の整数)$
で定める。0 以上の整数 $n$ について、 $C_{n}$ が奇数であるための必要十分条件は、ある 0 以上の整数 $j$ を用いて $n = 2^{j} - 1$ と表されることであることを証明せよ（ $2^{0} = 1$ とし、 $n = 0$ は $j = 0$ の場合にあたる）。

この問題で使うもの

カタラン数（説明と入口の問題）
合同式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

漸化式を 2 を法として考え、 $C_{n}$ の偶奇が添字の偶奇とどう関係するかを調べます。最後は $n$ についての強い帰納法でまとめます。

ヒント 2

和 $\sum_{i = 0}^{n} C_{i} C_{n - i}$ では $i$ 番目と $n - i$ 番目の項が等しいので、組にすると 2 倍になります。組にならずに残る項があるかどうかは $n$ の偶奇で決まります。

ヒント 3

$n$ が奇数のとき $C_{n + 1}$ は偶数、 $n = 2 m$ のとき $C_{2 m + 1} \equiv C_{m}^{2} \equiv C_{m} (mod 2)$ となります。あとは $n = 2 m + 1$ が $2^{j} - 1$ 型であることと $m$ が $2^{j} - 1$ 型であることの関係を調べます。

採点の観点と模範解答

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

採点の観点を見る

漸化式の和で $i$ と $n - i$ の項を組にする（対合 $i \mapsto n - i$ を使う）考え方を示している（2 点）
$n$ が奇数のとき固定される添字がないことから、 $m \geq 1$ で $C_{2 m}$ が偶数であることを導いている（2 点）
$n = 2 m$ のとき中央の項 $C_{m}^{2}$ だけが残り、 $C_{m}^{2} \equiv C_{m} (mod 2)$ の理由も付けて $C_{2 m + 1} \equiv C_{m} (mod 2)$ を導いている（2 点）
強い帰納法の枠組み（何を仮定して何を示すか）と $n = 0$ の場合、 $n \geq 1$ の偶数が $2^{j} - 1$ 型でないことを確認している（2 点）
$n = 2 m + 1$ について「 $n$ が $2^{j} - 1$ 型 $⟺$ $m$ が $2^{j} - 1$ 型」を両方向示し、帰納法の仮定と合わせて結論している（2 点）

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

模範解答を読む

方針: 漸化式を 2 を法として調べ、(A) $m \geq 1$ のとき $C_{2 m}$ は偶数、(B) $m \geq 0$ のとき $C_{2 m + 1} \equiv C_{m} (mod 2)$ を示す。これを使って $n$ についての強い帰納法で命題を示す。

以下、 $n$ が「 $2^{j} - 1$ 型」であるとは、ある 0 以上の整数 $j$ で $n = 2^{j} - 1$ と書けることとする。また、すべての $C_{n}$ は整数である（ $C_{0} = 1$ で、漸化式の右辺は整数の積の和だから、 $n$ についての帰納法で分かる）ので、偶奇を考えることができる。

補題 (A): $m \geq 1$ のとき $C_{2 m}$ は偶数。 $n = 2 m - 1 (\geq 1)$ とおくと $C_{2 m} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ 。添字の集合 ${0, 1, \dots, n}$ 上の写像 $i \mapsto n - i$ は 2 回施すと元に戻り、 $n$ が奇数なので $i = n - i$ となる $i$ （ $2 i = n$ ）は存在しない。よってこの集合は ${i, n - i}$ （ $0 \leq i \leq \frac{n - 1}{2}$ ）という 2 元の組に分かれ、各組の 2 項は $C_{i} C_{n - i} = C_{n - i} C_{i}$ で等しい。したがって
$C_{2 m} = 2 i = 0 \sum (n - 1) /2 C_{i} C_{n - i}$
は偶数である。

補題 (B): $m \geq 0$ のとき $C_{2 m + 1} \equiv C_{m} (mod 2)$ 。 $n = 2 m$ とおくと $C_{2 m + 1} = \sum_{i = 0}^{2 m} C_{i} C_{2 m - i}$ 。写像 $i \mapsto 2 m - i$ で固定される添字は $i = m$ だけで、残りの添字は ${i, 2 m - i}$ （ $0 \leq i \leq m - 1$ ）の組に分かれ、各組の 2 項は等しい（ $m = 0$ のときは組がなく、和は $C_{0}^{2}$ だけである）。よって
$C_{2 m + 1} = C_{m}^{2} + 2 i = 0 \sum m - 1 C_{i} C_{2 m - i} \equiv C_{m}^{2} (mod 2) .$
さらに $C_{m}^{2} - C_{m} = C_{m} (C_{m} - 1)$ は連続する 2 整数の積なので偶数であり、 $C_{m}^{2} \equiv C_{m} (mod 2)$ 。したがって $C_{2 m + 1} \equiv C_{m} (mod 2)$ 。

本証明（強い帰納法）。 「 $C_{n}$ が奇数 $⟺$ $n$ は $2^{j} - 1$ 型」を $P (n)$ とし、0 以上の整数 $n$ について、 $0 \leq n^{'} < n$ のすべての $n^{'}$ で $P (n^{'})$ が成り立つと仮定して $P (n)$ を示す。

$n = 0$ のとき: $C_{0} = 1$ は奇数で、 $0 = 2^{0} - 1$ は $2^{j} - 1$ 型。よって $P (0)$ は成り立つ。
$n \geq 1$ で $n$ が偶数のとき: $n = 2 m (m \geq 1)$ と書け、補題 (A) より $C_{n}$ は偶数。一方、 $2^{j} - 1$ 型の数は $j = 0$ のとき $0$ 、 $j \geq 1$ のとき $2^{j}$ が偶数なので奇数であり、 $n \geq 1$ の偶数 $n$ は $2^{j} - 1$ 型ではない。よって両辺とも偽で $P (n)$ は成り立つ。
$n$ が奇数のとき: $n = 2 m + 1 (m \geq 0)$ と書け、 $m < n$ である。補題 (B) より $C_{n}$ と $C_{m}$ の偶奇は一致し、帰納法の仮定 $P (m)$ より「 $C_{m}$ が奇数 $⟺$ $m$ は $2^{j} - 1$ 型」。ここで
$m = 2^{j} - 1$ ならば $n = 2 m + 1 = 2^{j + 1} - 1$ で、 $n$ は $2^{j} - 1$ 型。
逆に $n = 2^{j} - 1$ （ $n$ は奇数なので $n \geq 1$ 、よって $j \geq 1$ ）ならば $m = \frac{n - 1}{2} = 2^{j - 1} - 1$ で、 $m$ は $2^{j} - 1$ 型（ $j - 1 \geq 0$ ）。

よって「 $m$ は $2^{j} - 1$ 型 $⟺$ $n$ は $2^{j} - 1$ 型」であり、まとめると「 $C_{n}$ が奇数 $⟺$ $C_{m}$ が奇数 $⟺$ $m$ は $2^{j} - 1$ 型 $⟺$ $n$ は $2^{j} - 1$ 型」。 $P (n)$ が成り立つ。

$n$ は $0$ 、 $1$ 以上の偶数、奇数のいずれかなので場合分けは尽くされており、強い帰納法によりすべての 0 以上の整数 $n$ で $P (n)$ が成り立つ。

（確認: $C_{0}, \dots, C_{7} = 1, 1, 2, 5, 14, 42, 132, 429$ で、奇数は $n = 0, 1, 3, 7$ のとき。）

以上より、 $C_{n}$ が奇数であることと、 $n = 2^{j} - 1$ （ $j$ は 0 以上の整数）と表されることは同値である。 $■$

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題