トップ› 東京工業大学› 2021年› 理系第3問

東京工業大学 2021年理系第3問解説

方針・初手

(1) は二項係数を階乗の形に直して計算することで等式を示す。後半の倍数の証明は、導いた等式と「$n$ と $n+1$ が互いに素である」という性質を利用する。 (2) は数列の大小比較に関する問題である。階乗を含む数列の不等式は、隣接項の比 $\frac{a_{n+1}}{a_n}$ を計算し、数学的帰納法を用いるのが定石である。 (3) は (2) の結果と (1) の関係式を組み合わせる。$a_n$ が素数 $p$ であると仮定し、階乗の素因数の性質（最大の素因数は $2n$ 以下であること）と、(2) で評価した $a_n$ の増加スピードを比較することで、$n \geqq 4$ の場合に解が存在しないことを示す。

解法1

(1)

二項係数の定義より、

$$ {}_{2n}\mathrm{C}_{n} = \frac{(2n)!}{n!n!} $$

$$ {}_{2n}\mathrm{C}_{n-1} = \frac{(2n)!}{(n-1)!(n+1)!} $$

である。これらを用いて与式の両辺をそれぞれ計算する。左辺は、

$$ n {}_{2n}\mathrm{C}_{n} = n \cdot \frac{(2n)!}{n!n!} = \frac{(2n)!}{(n-1)!n!} $$

右辺は、

$$ (n+1) {}_{2n}\mathrm{C}_{n-1} = (n+1) \cdot \frac{(2n)!}{(n-1)!(n+1)!} = \frac{(2n)!}{(n-1)!n!} $$

よって、左辺と右辺が一致するため、

$$ n {}_{2n}\mathrm{C}_{n} = (n+1) {}_{2n}\mathrm{C}_{n-1} $$

が成り立つ。

次に、この等式を用いて ${}_{2n}\mathrm{C}_{n}$ が $n+1$ の倍数であることを示す。 ${}_{2n}\mathrm{C}_{n-1}$ は整数であるから、等式の右辺 $(n+1) {}_{2n}\mathrm{C}_{n-1}$ は $n+1$ の倍数である。したがって、等式の左辺 $n {}_{2n}\mathrm{C}_{n}$ も $n+1$ の倍数である。ここで、$n$ と $n+1$ は連続する整数であるため、互いに素である。（$\gcd(n+1, n) = \gcd(1, n) = 1$ より） $n {}_{2n}\mathrm{C}_{n}$ が $n+1$ の倍数であり、かつ $n$ と $n+1$ が互いに素であることから、${}_{2n}\mathrm{C}_{n}$ は $n+1$ の倍数でなければならない。よって示された。

(2)

まず、$a_{n+1}$ と $a_n$ の比を計算する。

$$ \frac{a_{n+1}}{a_n} = \frac{{}_{2n+2}\mathrm{C}_{n+1}}{n+2} \cdot \frac{n+1}{{}_{2n}\mathrm{C}_{n}} $$

$$ \frac{a_{n+1}}{a_n} = \frac{(2n+2)!}{(n+1)!(n+1)!} \cdot \frac{n!n!}{(2n)!} \cdot \frac{n+1}{n+2} $$

$$ \frac{a_{n+1}}{a_n} = \frac{(2n+2)(2n+1)}{(n+1)(n+1)} \cdot \frac{n+1}{n+2} $$

$$ \frac{a_{n+1}}{a_n} = \frac{2(2n+1)}{n+1} \cdot \frac{n+1}{n+2} = \frac{4n+2}{n+2} $$

これを用いて、数学的帰納法により $n \geqq 4$ のとき $a_n > n+2$ であることを示す。

(i)

$n=4$ のとき

$$ a_4 = \frac{{}_8\mathrm{C}_{4}}{5} = \frac{70}{5} = 14 $$

$n+2 = 6$ であるから、$14 > 6$ となり成立する。

(ii)

$n=k$ ($k \geqq 4$) のとき成立すると仮定する。

すなわち、$a_k > k+2$ であるとする。 $n=k+1$ のとき、$a_{k+1}$ を評価する。先ほど求めた比より、

$$ a_{k+1} = a_k \cdot \frac{4k+2}{k+2} $$

帰納法の仮定より $a_k > k+2$ であるから、

$$ a_{k+1} > (k+2) \cdot \frac{4k+2}{k+2} = 4k+2 $$

ここで、$4k+2$ と示すべき目標である $(k+1)+2 = k+3$ の差をとると、

$$ (4k+2) - (k+3) = 3k - 1 $$

$k \geqq 4$ より $3k-1 \geqq 11 > 0$ であるから、$4k+2 > k+3$ が成り立つ。したがって、

$$ a_{k+1} > k+3 $$

となり、$n=k+1$ のときも成立する。

（i）, （ii）より、$n \geqq 4$ を満たすすべての整数 $n$ について $a_n > n+2$ が成り立つ。

(3)

$a_n$ が素数 $p$ に等しいと仮定する。すなわち $a_n = p$ とおく。

$n \geqq 4$ のとき、 (2) の結果より $a_n > n+2$ であるから、$p > n+2$ が成り立つ。また、(1) で示した等式 $n {}_{2n}\mathrm{C}_{n} = (n+1) {}_{2n}\mathrm{C}_{n-1}$ の両辺を $n(n+1)$ で割ると、

$$ \frac{{}_{2n}\mathrm{C}_{n}}{n+1} = \frac{{}_{2n}\mathrm{C}_{n-1}}{n} $$

左辺は $a_n$ の定義そのものであるから、

$$ a_n = \frac{{}_{2n}\mathrm{C}_{n-1}}{n} $$

よって、$n \cdot a_n = {}_{2n}\mathrm{C}_{n-1}$ と表せる。$a_n = p$ を代入して、

$$ n \cdot p = {}_{2n}\mathrm{C}_{n-1} = \frac{(2n)!}{(n-1)!(n+1)!} $$

分母を払うと、

$$ n \cdot p \cdot (n-1)!(n+1)! = (2n)! $$

右辺の $(2n)! = 1 \cdot 2 \cdot 3 \cdots (2n)$ は、左辺の素因数 $p$ を持たなければならない。したがって、素数 $p$ は $2n$ 以下でなければならない。すなわち $p \leqq 2n$ である。

一方で、(2) の証明中で求めた隣接項の比に着目する。$n \geqq 4$ のとき、

$$ \frac{a_{n+1}}{a_n} = \frac{4n+2}{n+2} = 4 - \frac{6}{n+2} \geqq 4 - \frac{6}{6} = 3 $$

よって、$n \geqq 4$ において $a_{n+1} \geqq 3a_n$ が成り立つ。これを繰り返し用いると、$n \geqq 4$ のとき、

$$ a_n \geqq 3^{n-4} a_4 = 14 \cdot 3^{n-4} $$

$a_n = p$ であったから、素数 $p$ について以下の不等式が成り立つ必要がある。

$$ 14 \cdot 3^{n-4} \leqq p \leqq 2n $$

すなわち、$7 \cdot 3^{n-4} \leqq n$ が必要となる。しかし、$n=4$ のときは $7 \leqq 4$ となり不成立。 $n \geqq 5$ のときも、指数関数 $3^{n-4}$ の増加が一次関数 $n$ よりはるかに早いため、常に $7 \cdot 3^{n-4} > n$ となり成立しない。（厳密には $n=5$ で $21 > 5$、以降帰納法等で容易に示される）

以上より、$n \geqq 4$ の範囲に $a_n$ が素数となるような正の整数 $n$ は存在しない。残る $n=1, 2, 3$ について具体的に調べる。

$n=1$ のとき

$$ a_1 = \frac{{}_2\mathrm{C}_{1}}{2} = 1 $$

1は素数ではない。

$n=2$ のとき

$$ a_2 = \frac{{}_4\mathrm{C}_{2}}{3} = \frac{6}{3} = 2 $$

2は素数である。

$n=3$ のとき

$$ a_3 = \frac{{}_6\mathrm{C}_{3}}{4} = \frac{20}{4} = 5 $$

5は素数である。

よって、$a_n$ が素数となるのは $n=2, 3$ のときのみである。

解説

本問で登場する $a_n$ は「カタラン数」と呼ばれる有名な数列である。(1) ではそのカタラン数が整数であることを誘導形式で証明させている。 (2) の不等式評価では、階乗を含む数列の常套手段である「隣接項の比をとる」という手法が有効である。 (3) は整数問題の傑作とも言える小問である。「階乗 $(2n)!$ の素因数は $2n$ 以下の素数に限られる」という性質と、(2) で求めた漸化式からの指数関数的な増大スピードをぶつけることで、$n \geqq 4$ をあっさりと切り捨てることができる。