実践演習 整数系

カタラン数が素数となるための条件【2021年度 東京工業大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)

今回設定されている \(a_{n}=\displaystyle \frac {{}_{2n}\mathrm{C}_n}{n+1}\)  はカタラン数と呼ばれる有名な形の数であり、場合の数や確率の分野でよく登場する数です。

本問は「カタラン数だから何かあるのか?」と変に身構えてしまいかねませんが、「二項係数についての整数問題」と割り切って考えた方がいいでしょう。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

(1) について

式的に証明することもできますし、左辺、右辺の式に「場合の数としての意味付け」を与えて考えることもできます。

試験場的には式で証明するのが明快でしょう。

(2) について

\(a_{n}=\displaystyle \frac {{}_{2n}\mathrm{C}_n}{n+1}\)  を書き下していき、直接証明することもできますが、適切に式変形をしたり、急所を見抜く「目」が必要です。

また、帰納法による証明も十分有力な路線です。

その場合、前段仮定との結びつきを考えるにあたり、\(a_{n+1}\) ,  \(a_{n}\) についての漸化式を考えることになるでしょう。

一般項から攻めるのか、漸化式として扱うのかという選択はレベルが高い問題になると方針決定上大きな選択になりますが、本問もそれが実感できる問題だと思います。

(3) について

地味な難問と言ってよいでしょう。

誘導をどのように活用するのかがパッと見えるわけではなさそうです。

(1) の誘導は \(a_{n}\) が整数であるということを保証するためのものだと言えると思います。

(2) がどこで効いてくるかですが、とりあえずは「 \(n \geq 4\) のとき」というのが気になるところです。

少し邪推なのですが、「全て求めよ」ということは「求まりきる」のでしょう。

恐らく、 \(n \geq 4\) のときは \(a_{n}\) は素数にならないのだろうということを身構えて背理法で仕留めにいきます。

今回設定されているカタラン数 \(\displaystyle \frac {{}_{2n}\mathrm{C}_n}{n+1}\) の場合の数としての意味付けについては

参考カタラン数【最短経路の応用問題】【2008年度 九州大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。) (1) ,  (2) について 最短経路の問題として (1) ,  (2)  についてはきっちりと確保したいレベルの基本問題です。 (3 ...

続きを見る

で取り扱っていますので、適宜ご活用ください。

解答はコチラ

-実践演習, 整数系
-

© 2022 MathClinic