入試数学演習 大学受験 数学

【入試数学演習No.4】2項係数の上手い扱い方-奈良県立医科大学2018年後期より-

目次

  1. 問題
  2. 方針
  3. (1)解答
  4. (2)解答1
  5. (2)解答2
  6. あとがき

問題

\(n\)を\(1\)より大きい整数とする. このとき以下の条件を満たす\(0\)以上の整数\(r\)がただ一つ定まる:
条件:\(n\)は\(2^r\)で割り切れるが,\(2^{r+1}\)では割り切れない.

(1)\(1\)以上\(n\)以下の任意の整数\(i\)に対して,2項係数\({}_{2n} \mathrm{C} _{2i-1}\)は\(2^{r+1}\)で割り切れることを証明せよ.

(2)\(n\)個の2項係数\({}_{2n} \mathrm{C} _{2i-1}\) (\(i=1,2,\ldots , n\))の最大公約数は\(2^{r+1}\)であることを証明せよ.

(18 奈良県立医科大学・医学部(後期))

方針

(1)まず、2項係数\({}_{2n} \mathrm{C} _{2i-1}\)を書き出してみましょう。定義から、

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

となります。これが\(2^{r+1}\)で割り切れることを示したいのですが、まず、定義よりこの2項係数が整数です。(\(2n\)個のものから\(2i\)個のものを抽出する組み合わせと考えればよいでしょう。)次に、今問題となっているのは素因数\(2\)で何回割り切れるのか?ということであったので、分母にある奇数はとりあえずは無視しておいてもよさそうです。となると、分母にある2つの階乗の項:\((2i)!\)と\((2n-2i)!\)が\(2\)で何回割り切れるかを考えなければなりません。(分子のほうは\(n\)がちょうど\(2\)で\(r\)回割り切れることが判明しているので、素因数\(2\)の個数を特定するのは容易でしょう。)実際、ここから\(i\)が素因数\(2\)で何回割り切れるかを自分で設定することで解き進めることもできなくはなさそうですが、発想がやや難しいです。(解ける方、この方針で解き進めてみてください。)

また、以下のように小さい\(i\)を順に代入していくことで(実験することで規則を発見して数学的帰納法へと落とし込むことも考えてみます。

\begin{eqnarray}
{}_{2n} \mathrm{C} _1 &=& \frac{2n}{1}\\
{}_{2n} \mathrm{C} _3 &=& \frac{2n(2n-1)(2n-2)}{3 \cdot 2 \cdot 1} =\frac{2n}{1} \cdot \frac{(2n-1)(2n-2)}{3 \cdot 2} \\
{}_{2n} \mathrm{C} _5 &=& \frac{2n(2n-1)(2n-2)(2n-3)(2n-4)}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} =\frac{2n(2n-1)(2n-2)}{3 \cdot 2 \cdot 1} \cdot \frac{(2n-3)(2n-4)}{5\cdot 4}
\end{eqnarray}

という感じで1つ前の\(i\)の部分を\(i+1\)番目で再利用することで、考えるべき部分は後ろの単純な分数部分だけでよいことが分かります。このように、1つ前の\(i\)の部分を\(i+1\)番目で再利用することから数学的帰納法へと繋がっていきそうですが、実際に試してみるとうまくいきません。

では、どうしたらよいのでしょうか?本記事のタイトルにもあるように2項係数の関係式を思い出してみてください。2項係数\({}_{2n} \mathrm{C} _{2i-1}\)からただちに条件の強い\(n\)を抽出する方法が思い付きますか?

2項係数の関係式(基本編)

\({}_n \mathrm{C} _k = {}_n \mathrm{C} _{n-k}\)

\({}_n \mathrm{C} _k = {}_{n-1} \mathrm{C} _k + {}_{n-1} \mathrm{C} _{k-1}\)

\(k {}_n \mathrm{C} _k = n {}_{n-1} \mathrm{C} _{k-1} \)

3つとも教科書に載っているレベルの基本的な公式ですので、誰もが一度は目にしたことはあるでしょう。②、③は習った以降使う機会が意外と少なく忘れてしまった方も少なからずいると思います。この際覚えておきましょう!

以上の基本的な2項係数の関係式の証明方法を説明した記事を本記事の一番下に添付しておきます。本記事を読破後、余裕があれば読んでみてください

2項係数の関係式は以上の基本的なものに加えて、2項定理から導かれる恒等式を利用したものも難関大学入試では重要になってきます。ここでは頻出の最も基本的なものを3つだけ書いておきましょう。

\(\sum_{k=0}^{n} {}_n \mathrm{C} _k = 2^n\)

\(\sum_{k=0}^{n} (-1)^{k} {}_n \mathrm{C} _k = 0\)

\(\sum_{k=0}^{n} ({}_n \mathrm{C} _k)^2 = {}_{2n} \mathrm{C} _n\)

①は2項係数を全部足した和が\(2^n\)になることを、②は偶数のものだけの和と奇数のものだけの和が等しくなることを主張しています。③はややマイナーですが別記事にて証明方法から紹介しておきます。

以上の応用的な2項係数の関係式の証明方法を説明した記事も本記事の一番下に添付しておきます。本記事を読破後、余裕があれば読んでみてください

→本問では

③の関係式を用いることで条件の強い\(n\)を2項係数の前に下してくることができますので、議論を進めていくことができそうです。この操作を行ってしまえば、

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

となるので、あとは\(2i-1\)が奇数であるので\(2\)と互いに素になり、証明完了です。このあたりの記述は丁寧に書いておきましょう。

(2)(1)では\(2^{r+1}\)が最大公約数の候補となることを証明しました。次に証明すべきこととしては、最大公約数に奇素数が含まれないことです。小さい\(i\)で実験して候補を絞る方法をまず試してみますが、どうやら上手くいかないようです。(そもそも奇素数はたくさんありすぎます。)

ただ、\(2i-1=1\)とすると、2項係数が\(2n\)に等しくなるので\(\mathrm{gcd} (2,p) =1\)より、\(n \equiv 0 (\mathrm{mod}p)\)を得ます。この情報はさすがに何か有用性がありそうですね。

ですので、最大公約数が奇素数\(p\)で割り切れる、つまり、\(n\)個の2項係数\({}_{2n} \mathrm{C} _{2i-1}\) (\(i=1,2,\ldots , n\))がすべて奇素数\(p\)で割り切れると仮定して矛盾を起こしに行くことを考えます。矛盾を起こすためには、奇素数\(p\)で割り切れないような\(i\)の存在を示せばよいことになりますが、ここではそのような\(i\)を上手く見極めて選ぶ必要があります。

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

となりますから、分子の奇素数\(p\)を分母で全部割ってしまえばいいのですが、どうしたら分母の奇素数\(p\)の数を増やせるのでしょうか?試しに区切りがいいので\(2i-1=p\)としてみると、

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

分子、分母ともに\(p\)で割り切れる項は1つしかなくそれぞれ\(n\)と\(p\)ですので、\(\frac{n}{p}\)が再び\(p\)の倍数かどうかを確かめることになります。ですが、今の状況のままだとまだ何も言えません。(\(n\)が\(p\)で何回も割り切れる場合素因数\(p\)が分子に残ってしまうため)

この失敗を生かして\(2i-1\)がなるべく素因数\(p\)が多く含むように調節してやりましょう。ここからはやや技巧的になりますが\(n\)が\(p\)で割り切れる回数を設定してやって、その回数分\(p\)をかけたものを\(2i-1\)としてやると上手くいきます。

この解法は正直思い付くのが非常に困難ですね。ですので再び2項係数の関係式を用いることを考えます。題意の\(n\)個の2項係数をとりあえず全て足してみてください。すると証明完了まではすぐです!

解答では、2項係数の関係式を用いる方法を解答1、いちばん最初に考えた難しい方法を解答2としておきましょう。

(1)解答

2項係数の関係式により、

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

となる。定義より、\({}_{2n-1} \mathrm{C} _{2i-2}\)が整数であることと、\(2\)と\(2i-1\)が互いに素であることを考えれば、右辺の\(2n\)に含まれる\(r+1\)個の素因数\(2\)はすべて\({}_{2n} \mathrm{C} _{2i-1}\)のほうに含まれることが分かる。

したがって、2項係数\({}_{2n} \mathrm{C} _{2i-1}\)は\(2^{r+1}\)で割り切れる。(証明おわり)

(2)解答1

2項定理より\(x\)についての以下の恒等式が得られる:

\((1+x)^{2n} = {}_{2n} \mathrm{C} _0 + x {}_{2n} \mathrm{C} _1 + x^2 {}_{2n} \mathrm{C} _2 + \cdots + x^{2n} {}_{2n} \mathrm{C} _{2n}\)

この式で\(x=1,-1\)としたものを記述すると以下の2式が得られる:

\((1+1)^{2n} = {}_{2n} \mathrm{C} _0 + {}_{2n} \mathrm{C} _1 + {}_{2n} \mathrm{C} _2 + \cdots + {}_{2n} \mathrm{C} _{2n}\)

\((1+(-1))^{2n} = {}_{2n} \mathrm{C} _0 - {}_{2n} \mathrm{C} _1 + {}_{2n} \mathrm{C} _2 + \cdots + {}_{2n} \mathrm{C} _{2n}\)

さらに、第1式から第2式を引き算することで、偶数の2項係数のみが相殺するから、

\(2^{2n} - 0 =2({}_{2n} \mathrm{C} _1 + {}_{2n} \mathrm{C} _3 + \cdots + {}_{2n} \mathrm{C} _{2n-1})\)

つまり、

\(2^{2n-1} =({}_{2n} \mathrm{C} _1 + {}_{2n} \mathrm{C} _3 + \cdots + {}_{2n} \mathrm{C} _{2n-1})\)

を得る。

このことにより、もし題意の\(n\)個の2項係数の最大公約数がある奇素数\(p\)で割り切れると仮定すると、上式の右辺が\(p\)の倍数の和となるので左辺も\(p\)の倍数となるが、左辺は素因数分解した時に\(2\)以外の素数を含まないのでこれは矛盾。したがって、題意の\(n\)個の2項係数の最大公約数はどのような奇素数\(p\)でも割り切れない。

また、\(i=1\)とすると、\({}_{2n} \mathrm{C} _1=2n\)となるがこれは\(2^{r+2}\)では割り切れない。

これらの事実と(1)で証明したことにより、\(n\)個の2項係数\({}_{2n} \mathrm{C} _{2i-1}\) (\(i=1,2,\ldots , n\))の最大公約数は\(2^{r+1}\)であることが証明された。(証明おわり)

(2)解答2

題意の\(n\)個の2項係数の最大公約数がある奇素数\(p\)で割り切れると仮定する.。さらに、今、\(n\)が\(p\)でちょうど\(m\)回割り切れるとしておく。(\(p\)は自然数)このとき、

\({}_{2n} \mathrm{C} _{p^m} = \frac{2n \cdot (2n-1) \cdot \cdots \cdot (2n-(p^m)+1)}{p^m \cdot (p^m -1) \cdot \cdots \cdot 1}\)

となる。この式の分母は\(p\)の倍数を\(p^{m-1}\)個、…、\(p^m\)の倍数を1個含んでいるので素因数\(p\)の個数は合計で、

\(1+p+p^2+\cdots + p^{m-1} = \frac{p^m -1}{p-1}\)(個)

である。一方分子も連続\(p^m\)個の整数の積であり、最大の数が\(p^m\)の倍数であり、最小の数が\(p^m\)の倍数よりも\(1\)大きいので、この間に素因数\(p\)を\(m+1\)個以上含む整数はなく、分子の素因数\(p\)の数も分母と同じになってしまう。

ゆえに、分子の素因数\(p\)が全て分母によって約分されてしまうのでこれは\(p\)の倍数ではなく不合理。したがって、題意の\(n\)個の2項係数の最大公約数はどのような奇素数\(p\)でも割り切れない。

また、\(i=1\)とすると、\({}_{2n} \mathrm{C} _1=2n\)となるがこれは\(2^{r+2}\)では割り切れない。

これらの事実と(1)で証明したことにより、\(n\)個の2項係数\({}_{2n} \mathrm{C} _{2i-1}\) (\(i=1,2,\ldots , n\))の最大公約数は\(2^{r+1}\)であることが証明された。(証明おわり)

※この証明方法はパスナビ過去問ライブラリーの解答を参考にして作成しました。

あとがき

最後まで閲覧していただきありがとうございました。

最後に冒頭で言及していた記事のURLを貼っておきます。合わせてご覧になってください。

数学では入試問題1問から学ぶべきことが多くあると思います。復習して解法をどんどんと溜めていきましょう!

当サイトについての質問・問い合わせなどは当サイトのフォーラムへコメントまたは自分の個人用のツイッターアカウントにDMをくだされば幸いです。(アカウントは@skrdy0121です。)

最終更新:2021 1/27(Wed.)

  • この記事を書いた人
  • 最新記事

Yuya Sakurada

洛北(中高一貫)→京都大学理学部2回生|元駿台特待, EX生|予備校勤務 |個別指導講師(英数物)|高3時, 京大模試英語で全国15位以内を1年間で7回達成|ポケモン全国3位(2013), 全国Top8(2017), 全国Top4(2018)|大学受験英語・数学や大学の学問紹介の記事を中心に書いています。

-入試数学演習, 大学受験, 数学
-, , ,

Copyright © 2020-2021 Sacramy