今回は、東工大の過去問です。２項係数に関する問題です。
２項係数の問題苦手だな、、、と感じる人は多いのではないでしょうか。
しかし、慣れてくるとパターンがある事がわかります。
ぜひ、挑戦して苦手意識を克服してみましょう。
問 以下の問いに答えよ。
（１）正の整数nに対して、二項係数に関する次の等式を示せ。$${}_{2n}\mathrm{C}_{n}=(n+1){}_{2n}\mathrm{C}_{n-1}$$であることを示せ。
また、これを用いて\({}_{2n}\mathrm{C}_{n}\)はn+1の倍数であることを示せ。
（２）正の整数nに対して、\(a_{n}=\frac{{}_{2n}\mathrm{C}_{n}}{n+1}\)とおく。このとき、\(n \geq{4}\)ならば\(a_{n}\gt{n+1}\)であることを示せ。
（３）\(a_{n}\)が素数となる正の整数nを全て求めよ。
（21 東工大）
思考のポイント
- 二項係数は書き下して考えてみる
- 分子と分母の積の個数や約分に注意
解説
（１）正の整数nに対して、二項係数に関する次の等式を示せ。$${}_{2n}\mathrm{C}_{n}=(n+1){}_{2n}\mathrm{C}_{n-1}$$であることを示せ。
また、これを用いて\({}_{2n}\mathrm{C}_{n}\)はn+1の倍数であることを示せ。
まず、左辺を書き下してみて考えよう。
前半解答
\(\require{cancel}\)$$n{}_{2n}\mathrm{C}_{n}$$
$$=n\frac{2n(2n-1)\cdots(n+3)(n+2)(n+1)}{n(n-1)\cdots3\cdot2\cdot1}$$
nを約分し、(n+1)を取り出すと、
$$=(n+1)\cancel{n}\frac{2n(2n-1)\cdots(n+3)(n+2)}{\cancel{n}(n-1)\cdots3\cdot2\cdot1}$$
$$=(n+1){}_{2n}\mathrm{C}_{n-1}$$
\(\require{cancel}\)
後半は、「互いに素」を使えば、すぐに証明できますね。
後半解答
$$n{}_{2n}\mathrm{C}_{n}=(n+1){}_{2n}\mathrm{C}_{n-1}$$
nとn+1は互いに素より \({}_{2n}\mathrm{C}_{n}\)はn+1の倍数である
（２）正の整数nに対して、\(a_{n}=\frac{{}_{2n}\mathrm{C}_{n}}{n+1}\)とおく。このとき、\(n \geq{4}\)ならば\(a_{n}\gt{n+1}\)であることを示せ。
これも\(a_{n}\)を書き下して考えてみよう。
解答
$$a_{n}=\frac{{}_{2n}\mathrm{C}_{n}}{n+1}$$
$$=\frac{1}{n+1}\frac{2n(2n-1)(2n-2)\cdots(n+3)(n+2)(n+1)}{n(n-1)(n-2)\cdots3\cdot2\cdot1}$$
（２）\(n \geq{4}\)のとき、(n+1)と2nをそれぞれ約分して
$$=\frac{1}{\cancel{n+1}}\frac{\cancel{2n}(2n-1)(2n-2)\cdots(n+3)(n+2)\cancel{(n+1)}}{\cancel{n}(n-1)(n-2)\cdots3\cdot\cancel{2}\cdot1}$$
分母と分子の積の個数に注意すると
$$=\frac{2n-1}{n-1}\frac{2n-2}{n-2}\cdots\frac{n+4}{4}\frac{n+3}{3}(n+2)$$
と(n-3)個の積の形で表せる。
分母の中で1番大きいのは(n-1)、分子の中で1番小さいのは(n+3)なので、
$$>\frac{(2n-1)^{n-3}}{(n-1)^{n-3}}(n+2)$$
\((\frac{n-1}{n+3})^{n-3}>1\)より
$$>n+2$$
どこを約分して式を整理するかがポイントでした。
他にも、数学的帰納法を使って解く方法もあります。
それでは、(３)です。
（２）を利用できるか意識しながら解きましょう。
（３）\(a_{n}\)が素数となる正の整数nを全て求めよ。
まずは、実験からn=1,2,3,4,5位まですぐ試してみましょう。
実験
\(a_{1}=\frac{2}{2}=1\) \(a_{2}=\frac{6}{3}=2\) \(a_{3}=\frac{20}{4}=5\) \(a_{4}=\frac{70}{5}=12\) \(a_{5}=\frac{252}{6}=42\)
n=2,3で素数となるのはすぐに分かります。
n≥4に関しては、素数にはならなそうです。
(2)の条件からも予想できますね。
解答
\(a_{n}=p\)とする。（pは素数）
\(n\geq4\)のとき
$$\frac{1}{\cancel{n+1}}\frac{\cancel{2n}(2n-1)(2n-2)\cdots(n+3)(n+2)\cancel{(n+1)}}{\cancel{n}(n-1)(n-2)\cdots3\cdot\cancel{2}\cdot1}=p$$
ここで、(2)より\(p>n+2\)なので\(2p>2n+4\)、\(2n+4\)以下の整数でpの倍数は、pのみ
よって、分子の積の形で表されたいずれかの整数がpである。
$$p=p\frac{p以外の(n-2)個の整数の積}{(n-1)(n-2)\cdots3}$$
(2)と同様にして
$$p=p\frac{p以外の(n-2)個の整数の積}{(n-1)(n-2)\cdots3}>p\cdot1$$
これは矛盾なので、\(a_{n}\)は素数にはならない。
\(a_{1}=\frac{2}{2}=1\) 、 \(a_{2}=\frac{6}{3}=2\) 、\(a_{3}=\frac{20}{4}=5\) より
\(a_{n}\)が素数となる正の整数nは\(n=2,3\)
n４以上で素数となるものが存在しないことを証明することが
問題の肝でした。
まとめ
ポイントは以下の４点です。
- ２項係数は書き下して考える
- 互いに素を利用して、倍数の証明
- ２項係数を書き下した際、整数の積の個数に注意
- 素数でないことの証明は、背理法を利用
今回の\(a_{n}=\frac{{}_{2n}\mathrm{C}_{n}}{n+1}\)は、カタラン数と言います。
トーナメントの総数、最短経路問題、多角形の三角形分割問題などに登場します。
コメント