カタラン数が素数になる条件（2021年東京工業大学前期数学第3問）

解答例

 

以下、二項係数が整数であることは既知として解答する。

 

（１）

$$\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$のときも成り立つ。

 

以上より、数学的帰納法から命題 $(*)$ の成立が示された。

□

 

 

（３）

(1)より$$a_n=\dfrac{n\,{}_{2 n} \mathrm{C}_{n}}{n+1}$$は整数である。

 

数列$\{a_n\}$の隣接項の比を取ると$$\begin{aligned}
\dfrac{a_n}{a_{n-1}}
&=\dfrac{{}_{2 n} \mathrm{C}_{n}}{n+1}\cdot\dfrac{n}{{}_{2n-2} \mathrm{C}_{n-1}} \\
&=\dfrac{n}{n+1}\cdot\dfrac{(2n)(2n-1)}{n^2} \\
&=\dfrac{4n-2}{n+1}
\end{aligned}$$
より、
$$\boxed{\,a_n=\dfrac{4n-2}{n+1}\,a_{n-1}\,}\qquad (n\geqq2)$$
を得る。

 

ここで係数の分子・分母の最大公約数について、$$\begin{aligned} \gcd(4n-2,n+1)&=\gcd(4n-2-4(n+1),\,n+1) \\ &=\gcd(-6,n+1) \\ &=\gcd(6,n+1) \end{aligned}$$となるから、$$d:=\gcd(4n-2,n+1)\in\{1,2,3,6\}$$が成り立ち、特に $d\leqq 6$ である。

 

ここで互いに素である整数 $\gcd(j,k)=1$ を用いて$$4n-2=dj,\ n+1=dk$$とおくと、漸化式は$$a_n=\dfrac{dj}{dk}\,a_{n-1}=\dfrac{j}{k}\,a_{n-1}$$となる。左辺は整数であり $\gcd(j,k)=1$ なので$k$は$a_{n-1}$を割り切ることが必要である。よってある整数 $l$ を用いて$$a_{n-1}=kl$$と書ける。これを代入すると$$a_n=jl$$を得る。

 

$n\geqq5$ とすると $n-1\geqq4$ より (2)から$$a_{n-1}>(n-1)+2=n+1$$である。一方 $k=\dfrac{n+1}{d} \leqq n+1$ である。また $n\geqq5$ のとき$$j=\dfrac{4n-2}{d}\geqq\dfrac{4n-2}{6}\geqq\dfrac{18}{6}=3$$より $j>1$ が成り立つ。したがって、$a_n$ が素数だと仮定すると、$$l=1$$でなければならない。このとき$$a_{n-1}=kl=\dfrac{n+1}{d}\leqq n+1$$となるが、これは $a_{n-1}>n+1$ に矛盾する。よって$n\geqq5$のとき$a_n$は素数ではないから、$n \leqq 4$ の範囲で調べればよい。実際に計算すると、$$a_1=\frac{{}_{2} \mathrm{C}_{1}}{2}=1$$ $$a_2=\frac{{}_{4} \mathrm{C}_{2}}{3}=2$$ $$a_3=\frac{{}_{6} \mathrm{C}_{3}}{4}=5$$ $$a_4=\frac{{}_{8} \mathrm{C}_{4}}{5}=14$$となるから、求める正の整数は$$n=\color{red}{2,\ 3}$$である。