二項係数の問題が解ける!解けるぞ!! – 2021年東工大 数学 第3問
2021年東工大 数学 第3問 は二項係数に関する問題です。問題文は以下の通りです。
以下の問いに答えよ．
(1) 正の整数 n に対して，二項係数に関する次の等式を示せ．
n {}_{2n} \mathrm{C}_n = (n+1) {}_{2n} \mathrm{C}_{n-1}
また，これを用いて {}_{2n} \mathrm{C}_n は n+1 の倍数であることを示せ．
(2) 正の整数 n に対して，
a_n = \displaystyle\frac{{}_{2n} \mathrm{C}_n}{n+1}
とおく．このとき， n \geqq 4 ならば a_n > n+2 であることを示せ．
(3) a_n が素数となる正の整数 n をすべて求めよ．
問題文が簡潔なので、割とすっきり解けそうな気がします。早速見ていきましょう。
なお、以下の内容は、東工大が公表したものではありません。
2021年東工大 数学 第3問 小問1の解法
まずは定義に従って、左辺を変形してみます。すると、
\begin{aligned}
n {}_{2n} \mathrm{C}_n &= n \cdot \frac{(2n)!}{n!n!} \\
& =\frac{(2n)!}{(n-1)!n!} \\
& = (n+1) \cdot\frac{(2n)!}{(n-1)!(n+1)!} \\
& = (n+1){}_{2n} \mathrm{C}_{n-1}
\end{aligned}と、等式をあっさり証明することが出来ました。
次のお題である「 {}_{2n} \mathrm{C}_n は n+1 の倍数である」ですが、証明した等式の両辺を n で割ると、
{}_{2n} \mathrm{C}_n = (n+1) \cdot \frac{{}_{2n} \mathrm{C}_{n-1}}{n} \cdots(1)なので、証明すべき命題は
\displaystyle\frac{{}_{2n} \mathrm{C}_{n-1} }{n} は整数である
と言い換えることが出来ます。
ところが、式(1) を
{}_{2n} \mathrm{C}_n = (1+ \frac{1}{n}) \cdot {}_{2n} \mathrm{C}_{n-1}と変形することを思いつければ、これから直ちに
\frac{{}_{2n} \mathrm{C}_{n-1}}{n} = {}_{2n} \mathrm{C}_n - {}_{2n} \mathrm{C}_{n-1}が導出できます。すなわち \frac{{}_{2n} \mathrm{C}_{n-1}}{n} が整数であることが示せました。ゆえに、 {}_{2n} \mathrm{C}_n は n+1 の倍数です。
2021年東工大 数学 第3問 小問2の解法
a_n を定義に従って、数字の積で書き下してみます。すると n \geqq 4 のとき、
\begin{aligned}
a_n &= \frac{{}_{2n} \mathrm{C}_n}{n+1} \\
& = \frac{1}{n+1} \cdot \frac{(2n)!}{n!n!} \\
& = \frac{2n (2n-1) \cdots(n+2)(n+1)}{(n+1) n (n-1)\cdot \cdots3 \cdot 2 \cdot 1} \\
& = \frac{(2n-1) (2n-2) \cdots (n+2)}{(n-1) (n-2) \cdots 3} \\
& = (n+2) \frac{\prod\limits_{k=1}^{n-3}(2n-k)}{\prod\limits_{k=1}^{n-3}(n-k)} \\
& = (n+2)\prod_{k=1}^{n-3} \left ( 1 + \frac{n}{n-k} \right ) \\
& > n+2
\end{aligned}と、比較的あっさり証明できました。
2021年東工大 数学 第3問 小問3の解法
このような「すべて求めよ」的な設問の場合、2016年京大数学第2問のように、 n が十分に大きくなると素数ではなくなると予想されます。そこで実際はどうなのか、計算してみます。
n = 1 のとき
a_1 = \frac{{}_2 \mathrm{C}_1}{2} = 1なので素数ではありません。
n = 2 のとき
a_2 = \frac{{}_4 \mathrm{C}_2}{3} = 2なので素数です。
n = 3 のとき
a_3 = \frac{{}_6 \mathrm{C}_3}{4} = 5なので素数です。
n = 4 のとき
a_4 = \frac{{}_8 \mathrm{C}_4}{5} = 14なので素数ではありません。
そもそも n \geqq 4 のとき、小問2で示したように
\begin{aligned}
a_n &=
(n+2) \frac{\prod\limits_{k=1}^{n-3}(2n-k)}{\prod\limits_{k=1}^{n-3}(n-k)} \\
\end{aligned}です。分母の因数が n-3 個なのに対し、分子の因数は n-2 と1つ多く、しかも分母のすべての因数が分子のどの因数より小さいので、約分によってたった一つの素因数だけが残る、などと言うことは起こりそうにありません。
背理法による証明
そこで n \geqq 4 のとき、 a_n が素数でないことを、背理法によって証明します。
まず、
\begin{aligned}
\frac{\prod\limits_{k=1}^{n-3}(2n-k)}{\prod\limits_{k=1}^{n-3}(n-k)}= \frac{p}{q}\\
\end{aligned}と既約分数表現したとします。ここで、 p,q は互いに素な自然数で、 p > q です。
このとき、 a_n が素数ならば、
a_n = (n+2)\frac{p}{q}なので、 p は n+2 と素な素数、かつ q = n+2 です。
もし q \ne n+2 ならば、 q は n+2 を割り切るか割り切らないかのどちらかですが、割り切る場合は a_n は複数の素因数を持つので素数ではありません。また、割り切らないのなら a_n は整数ですらなくなります。
したがって q = n+2 なので a_n = p であり、 a_n が素数なのだから p も素数です。
仮定の矛盾を導出する
よって a_n が素数ならば、
\begin{aligned}
\frac{\prod\limits_{k=1}^{n-3}(2n-k)}{\prod\limits_{k=1}^{n-3}(n-k)}= \frac{p}{n+2}\\
\end{aligned}が成り立ちます。ここに p は n+2 と素な素数です。
左辺の分母を払うと
\begin{aligned}
\prod\limits_{k=1}^{n-3}(2n-k)= \frac{p}{n+2}\prod\limits_{k=1}^{n-3}(n-k) \cdots (2)
\end{aligned}ですが、 p は素数なので n+2 で割り切れたりしません。よって、 \prod\limits_{k=1}^{n-3}(2n-k) は p を素因数に持つことがわかります。
したがって、ある自然数 1 \leqq k_0 \leqq n -3 および m_0 \geqq 1 が存在して、
2n -k_0 = m_0p
が成り立ちます。
これを式(2) に代入して
\begin{aligned}
m_0 p\prod_{\substack{k=1 \\ k \ne k_0}}^{n-3}(2n-k)= \frac{p}{n+2}\prod_{k=1}^{n-3}(n-k)
\end{aligned}よって、
\begin{aligned}
m_0 &= \frac{\prod\limits_{k=1}^{n-3}(n-k)}{(n+2) \prod\limits_{\substack{k=1 \\ k \ne k_0}}^{n-3}(2n-k)} \\
& < \frac{(n-1)^{n-3}}{(n+2)^{n-3}} < 1
\end{aligned}となりますが、これは m_0 が自然数であることに矛盾します。
ゆえに、 n \geqq 4 のとき、 a_n は素数でないことが証明できました。
以上をまとめると、 a_n が素数になる正の整数は、 n=2,3 です。
解法のポイント
本問は二項係数 {}_n \mathrm{C}_k の定義に従って素直に計算していけば、比較的容易に回答できます。
小問3がやっかいですが、これも、
\begin{aligned}
a_n &=
(n+2) \frac{\prod\limits_{k=1}^{n-3}(2n-k)}{\prod\limits_{k=1}^{n-3}(n-k)} \\
\end{aligned}と a_n を具体的に書き下してみれば、こんなにたくさんの数の積で出来ていて、しかもすべての分子の因数が分母の因数より大きいのに、約分の結果たった1つの素因数になってしまうなどと言うことがありそうにないことは、直感的に明らかだと思います。
2項係数の問題は2021年東大第4問もそうでしたが、積の形に具体的に書き下してみると、回答に向けたヒントを得られることがあります。まずはバラバラと書き下してみましょう。