今年の東工大で出題された整数問題は二項係数、特に「カタラン数」に関するものでした。同様の問題が海外の数学コンテストに出題されたこともあり、ひょっとすると東工大を受けるようなハイレベルな受験生の中には解いた経験のある数論マニアが居たかもしれません。
以下の問いに答えよ。
（１）正の整数$n$に対して、二項係数に関する次の等式を示せ。$$n\,{}_{2 n} \mathrm{C}_{n}=(n+1)\,{}_{2 n} \mathrm{C}_{n-1}$$また、これを用いて${}_{2 n} \mathrm{C}_{n}$は $n+1$ の倍数であることを示せ。
（２）正の整数$n$に対して、$$a_{n}=\dfrac{{}_{2 n} \mathrm{C}_{n}}{n+1}$$とおく。このとき、$n \geqq 4$ ならば $a_n>n+2$ であることを示せ。
（３）$a_n$が素数となる正の整数$n$をすべて求めよ。
（2021年東京工業大学 前期第3問）
考え方
（１）は示すべき式が明示されており、数学的帰納法で証明しようとした人がいたかもしれませんが、単純な式変形だけで済んでしまいます。数学的帰納法を使うべきなのは（２）の方です。（３）のポイントは $n \geqq 4$ のときに$a_n$が $n+2$ の倍数になるという部分です。これと（２）の不等式から$a_n$が素数となるような$n$を絞り込むことができます。
解答例
以下、二項係数が整数であることは既知として解答する。
（１）
$$\small \begin{aligned}
n\,{}_{2 n} \mathrm{C}_{n} &= n \cdot \dfrac{(2n)!}{n! \cdot n!} \\
&=(n+1) \cdot \dfrac{(2n)!}{(n+1)! (n-1)!} \\ &= (n+1) \cdot \dfrac{(2n)!}{\{2n-(n-1)\}! (n-1)!} \\ &= (n+1)\,{}_{2 n} \mathrm{C}_{n-1}
\end{aligned}$$となるので成り立つ。これと、$n$と$n+1$は互いに素であることから、$n+1$は${}_{2 n} \mathrm{C}_{n}$を割り切る。即ち${}_{2 n} \mathrm{C}_{n}$は $n+1$ の倍数である。
□
（２）
命題 $(*)$「$n \geqq 4$ ならば $a_n>n+2$ である」を数学的帰納法によって示す。
$n=4$ のとき$$a_4=\dfrac{{}_{8} \mathrm{C}_{4}}{5}=14>4+2$$となるから、$a_n>n+2$ が成り立つ。
$n=k$（$k$は$4$より大きい整数）のとき $a_k>k+2$ が成立していると仮定する。このとき$$\small \begin{aligned}
a_{k+1} &= \dfrac{{}_{2k+2} \mathrm{C}_{k+1}}{k+2} \\
&=\dfrac{(2k+2)!}{(k+2)(k+1)!(k+1)!} \\
&=\dfrac{(2k+2)(2k+1)}{(k+2)(k+1)} \cdot \dfrac{(2k)!}{(k+1)k!k!} \\ &=\dfrac{4k+2}{k+2}a_k \\ &> \dfrac{4k+2}{k+2}\cdot (k+2) \quad (\because \text{仮定}) \\
&= 4k+2 \\ &> (k+1)+2
\end{aligned}$$となるので $n=k+1$ のときも成り立つ。
以上より、数学的帰納法から命題 $(*)$ の成立が示された。
□
（３）
$a_1=1$ となり素数でないので $n=1$ は不適。$a_2=2$、$a_3=5$ は素数となるので $n=2,3$ は求める正の整数$n$である。
以下、$n \geqq 4$ のときを考える。
（２）の途中式より$$\small a_{n+1}=\dfrac{2(2n+1)}{n+2}a_n$$となる。（１）より${}_{2 n} \mathrm{C}_{n}$は $n+1$ の倍数であるから$a_n$は任意の正の整数$n$について整数である。よって $n+2$ は $2$、$2n+1$、$a_n$のいずれかを割り切ることが必要である。
$n$が正の整数のとき $n+2$ が$2$を割り切ることは無い。また、$$\small \begin{aligned}(2n+1)-(n+2) &=n-1 \\ &=(n+2)-3 \end{aligned}$$より、$2n+1$ が $n+2$ で割り切れるときは$3$も $n+2$ で割り切れる必要があるが、$n \geqq 4$ のときこれは不可能。
よって$a_n$は $n+2$ で割り切れることが必要である。また、（２）の結論より $n \geqq 4$ のとき $a_n>n+2$ となるから、ある整数$N$ $(>1)$ を用いて$$a_n=(n+2) \cdot N$$と表される。したがって、$n \geqq 4$ のとき$a_n$は素数にならない。
以上より、求める正の整数は$$n=\color{red}{2,\ 3}$$である。
$a_{n}=\dfrac{{}_{2 n} \mathrm{C}_{n}}{n+1}$ で定まる数列を「カタラン数」と言います。カタラン数は経路の数え上げといった組み合わせ論の問題や母関数の導入などに登場する有名な数列です。
本問はカタラン数が素数になる条件を求める問題でした。誘導設問の意図を上手く汲み取れればスムーズだったと思います。（３）で（２）を利用するところが難しかったかもしれません。$$\small a_{n+1}=\dfrac{2(2n+1)}{n+2}a_n$$という漸化式を利用するところが本問のポイントです。なお、東工大では2016年に階乗の整除性に関する出題があります。
今年の東工大は確率分野の出題が無く、今年で3年連続のお休みとなりました。ここ数年は幾何色の濃いセットが続いています。整数分野も頻出なので論証問題を中心に鍛えておきましょう。