COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

二項定理

理論

二項定理・多項定理

定理≪二項定理・多項定理≫

 任意の非負整数 $n,$ 正の整数 $r$ に対して, \[ (x_1+\cdots +x_r)^n = \sum_{\begin{array}{cc} k_1+\cdots +k_r = n, \\ \{ k_1,\cdots,k_r\} \subset \{ 0,\cdots,n\} \end{array}}\frac{n!}{k_1!\cdots k_r!}x_1{}^{k_1}\cdots x_r{}^{k_r}\] が成り立つ. 特に, \[ (x+y)^2 = \sum _{k = 0}^n{}_n\mathrm C_kx^{n-k}y^k\] が成り立つ.

問題

二項係数の和

問題≪ベルヌーイの不等式≫

 すべての正の整数 $n$ に対して, \[ (1+x)^n \geqq 1+nx\ (x \geqq 0) \quad \cdots [\ast ]\] が成り立つことを示せ.

解答例

 二項定理により, \[ (1+x)^n = 1+nx+\cdots +x^n\] であり, $x \geqq 0$ のとき $\cdots$ 以下の項は $0$ 以上であるから, $[\ast ]$ が成り立つ.

問題≪二項係数の交代和≫

 ${}_{2n}\mathrm C_0+\cdots +{}_{2n}\mathrm C_{2n} = {}_{2n}\mathrm C_1+\cdots +{}_{2n}\mathrm C_{2n-1} = 2^{2n-1}$ を示せ.

解答例

 二項定理より, \begin{align*} (x+y)^{2n} &= {}_{2n}\mathrm C_0x^{2n}+{}_{2n}\mathrm C_1x^{2n-1}y+\cdots \\ &\qquad +{}_{2n}\mathrm C_{2n-1}xy^{2n-1}+{}_{2n}\mathrm C_{2n}y^{2n} \quad \cdots [1]. \end{align*} $[1]$ に $x = 1,$ $y = -1$ を代入すると, $$0 = (1-1)^{2n} = {}_{2n}\mathrm C_0-{}_{2n}\mathrm C_1+\cdots -{}_{2n}\mathrm C_{2n-1}+{}_{2n}\mathrm C_{2n}.$$ よって, $${}_{2n}\mathrm C_0+\cdots +{}_{2n}\mathrm C_{2n} = {}_{2n}\mathrm C_1+\cdots +{}_{2n}\mathrm C_{2n-1} \quad \cdots [2].$$ この両辺の値を $S$ とおく.
$[1]$ に $x = y = 1$ を代入すると, \begin{align*} (1+1)^{2n} &= {}_{2n}\mathrm C_0+{}_{2n}\mathrm C_1+\cdots +{}_{2n}\mathrm C_{2n-1}+{}_{2n}\mathrm C_{2n}. \\ \therefore 2^{2n} &= ({}_{2n}\mathrm C_0+\cdots +{}_{2n}\mathrm C_{2n}) \\ &\qquad +({}_{2n}\mathrm C_1+\cdots +{}_{2n}\mathrm C_{2n-1}). \end{align*} よって, \begin{align*} 2S &= 2^{2n}. \\ \therefore S &= 2^{2n-1} \quad \cdots [3]. \end{align*} $[2],$ $[3]$ より, 求める等式が得られた.

問題≪山型の順列≫

 $1$ 以上 $n$ 以下の $n$ 個の整数を横 $1$ 列に並べるとき, $1 \leqq m \leqq n$ なるある整数 $m$ に対して左から $m$ 番目までが単調増加で $m$ 番目以降が単調減少となるような場合の数を求めよ.

解答例

 題意の順列について $m$ 番目までが単調増加で $m$ 番目以降が単調減少であるとき, $m-1$ 番目までに現れるの値の決め方は ${}_{n-1}\mathrm C_{m-1}$ 通りあり, その各々に応じて順列は自動的に決まる.
ゆえに, 求める場合の数は, 二項定理より, \[\sum\limits_{m = 1}^n{}_{n-1}\mathrm C_{m-1} = (1+1)^{n-1} = 2^{n-1}.\]

別解

 題意の条件の下で $n$ 以下の $n-1$ 個の整数について $n$ の左か右かの $2$ 通りが選択可能であり, それらが決まると $n$ 個の整数の順列は自動的に決まるから, 求める場合の数は $2^{n-1}.$

問題≪円周上の点を結ぶ凸多角形の個数≫

 円周上に配置された $n$ 個の点のうち $3$ 個以上の点を結んで凸多角形を作る方法の総数を求めよ.

解答例

 準備中.

問題≪二項係数の平方和≫

 次の等式が成り立つことを示せ. \[\sum\limits_{k = 0}^n{}_n\mathrm C_k{}^2 = {}_{2n}\mathrm C_n.\]

解答例

 $(1+x)^n,$ $(x+1)^n$ を二項定理により展開すると, \begin{align*} (1+x)^n &= \sum\limits_{k = 0}^n{}_n\mathrm C_kx^k, \\ (x+1)^n &= \sum\limits_{k = 0}^n{}_n\mathrm C_kx^{n-k}. \end{align*} これらの積 $(1+x)^{2n}$ の $x^n$ の係数は, 二項定理により ${}_{2n}\mathrm C_n$ である. これを右辺の積から計算すると, \[ {}_{2n}\mathrm C_n = \sum\limits_{k = 0}^n{}_n\mathrm C_k{}^2.\]

別解

 $n$ 人の A クラスと $n$ 人の B クラスから合計 $n$ 人を選ぶ方法の総数 ${}_{2n}\mathrm C_n$ を, A クラスから何人選ぶかで場合分けして数える.
$0 \leqq k \leqq n$ なる整数 $k$ について, A クラスから $k$ 人を選ぶとき, B クラスからは $n-k$ 人を選ぶから, この場合の選び方の総数は, \[ {}_n\mathrm C_k\cdot{}_n\mathrm C_{n-k} = {}_n\mathrm C_k{}^2.\] これらを $k$ について足し合わせると, 求める等式が得られる.

問題≪ファンデルモンドの畳み込み≫

 $m,$ $n$ を正整数とし, $r$ を $0 \leqq r \leqq m+n$ なる整数とする. $(x+1)^{m+n}$ の展開式を考えることにより, 次の公式が成り立つことを示せ. \[\sum\limits_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k} = {}_{m+n}\mathrm C_r.\]

解答例

\[ (x+1)^{m+n} = (x+1)^m(x+1)^n\] の各べきを展開すると \begin{align*} \sum\limits_{r = 0}^{m+n}{}_{m+n}\mathrm C_r\,x^r &= \left(\sum\limits_{k = 0}^m{}_m\mathrm C_k\,x^k\right)\left(\sum\limits_{\ell = 0}^n{}_n\mathrm C_{\ell}\,x^{\ell}\right) \\ &= \sum\limits_{r = 0}^{m+n}\sum\limits_{k+\ell = r}{}_m\mathrm C_k\cdot {}_n\mathrm C_{\ell}\,x^r \\ &= \sum\limits_{r = 0}^{m+n}\sum\limits_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k}\,x^r \end{align*} となる. ただし, この数式の第 $2$ 行, 第 $2$ のシグマ記号は $k+\ell = r,$ $0 \leqq k \leqq m,$ $0 \leqq \ell \leqq n$ なる整数 $k,$ $\ell$ にわたる和を意味する. 両辺の各項の係数を比較すると, 求める等式が得られる.

整数の剰余

問題≪倍数の条件≫

 $n$ を正の整数とする. $a_n = 1^n+2^n+3^n+4^n$ が $6$ の倍数であるための必要十分条件を求めよ.

解答例

 $2^n,$ $4^n$ は偶数で, 奇数の和 $1^n+3^n$ も偶数だから, 任意の正の整数 $n$ に対して $$a_n = 1^n+2^n+3^n+4^n$$ は偶数である.
よって, $a_n$ が $3$ の倍数であるため条件を求める.
$3^n$ は $3$ の倍数だから, $1^n+2^n+4^n$ が $3$ の倍数であるための条件を求める.
二項定理より \begin{align*} 2^n &= (3-1)^n = \sum\limits _{i = 0}^{n-1}{}_n\mathrm C_i3^{n-i}(-1)^i +(-1)^n, \\ 4^n &= (3+1)^n = \sum\limits _{i = 0}^{n-1}{}_n\mathrm C_i3^{n-i}+1 \end{align*} だから, ある整数 $q,$ $q'$ を用いて \begin{align*} 2^n &= 3q+(-1)^n, \\ 4^n &= 3q'+1 \end{align*} と書ける. このとき, \begin{align*} 1^n+2^n+4^n &= 1+3q+(-1)^n+3q'+1 \\ &= 3(q+q')+(-1)^n+2. \end{align*} よって, 求める条件は, $(-1)^n+2$ が $3$ の倍数となること.
(i)
$n$ が偶数のとき, $(-1)^n+2 = 1+2 = 3$ は $3$ の倍数.
(ii)
$n$ が奇数のとき, $(-1)^n+2 = -1+2 = 1$ は $3$ の倍数でない.
ゆえに, $a_n$ が $6$ の倍数となるための必要十分条件は, $n$ が偶数であること.

問題≪フェルマーの小定理≫

 $p$ を素数とし, $k$ を $1$ 以上 $p-1$ 以下の整数とする.
(1)
$k{}_p\mathrm C_k = p{}_{p-1}\mathrm C_{k-1}$ を示せ.
(2)
${}_p\mathrm C_k$ は $p$ の倍数であることを示せ.
(3)
任意の整数 $a$ に対して, $a^p-a$ は $p$ の倍数であることを示せ.

解答例

(1)
\begin{align*} &k{}_p\mathrm C_k = k\cdot\frac{p!}{k!(p-k)!} \\ &= k\cdot\frac{p}{k}\cdot\frac{(p-1)!}{(k-1)!\big( (p-1)-(k-1)\big) !} = p{}_{p-1}\mathrm C_{k-1}. \end{align*}
(2)
(1) より, $k{}_p\mathrm C_k$ は $p$ の倍数である.
$1 \leqq k \leqq p-1$ より, $k$ は $p$ と互いに素だから, ${}_p\mathrm C_k$ は $p$ の倍数である.
(3)
(I)
$a > 0$ のとき. $a$ に関する帰納法で示す.
(i)
$a = 1$ のとき, $1^p-1 = 0$ より, $a^p-a$ は $p$ の倍数である.
(ii)
与えられた正整数 $a$ に対して $a^p-a$ が $p$ の倍数であるとすると, \begin{align*} &(a+1)^p-(a+1) \\ &= \left( a^p+\sum\limits _{k = 1}^{p-1}{}_p\mathrm C_ka^{p-k}+1\right) -(a+1) \\ &= (a^p-a)+\sum\limits _{k = 1}^{p-1}{}_p\mathrm C_ka^{p-k} \end{align*} の右辺について, $a^p-a$ は $p$ の倍数で, (2) より残りの項も $p$ の倍数だから, $(a+1)^p-(a+1)$ は $p$ の倍数である.
(i), (ii) より, 任意の正整数 $a$ に対して, $a^p-a$ は $p$ の倍数である.
(II)
$a = 0$ のとき. $0^p-0 = 0$ より $a^p-a$ は $p$ の倍数である.
(III)
$a < 0,$ $p \geqq 3$ のとき. $p$ は奇数だから $(-a)^p-(-a) = -(a^p-a)$ であり, これは (I) より $p$ の倍数である. よって, $a^p-a$ も $p$ の倍数である.
(IV)
$p = 2$ のとき. $a^2-a = a(a-1)$ は偶数だから, $a^p-a$ は $p$ の倍数である.
(I)~(IV) より, 任意の整数 $a$ に対して $a^p-a$ は $p$ の倍数である.

問題≪素数によるべきの性質: フロベニウス準同型≫

 $p$ を素数とする. 任意の整数 $a,$ $b$ に対して $(a+b)^p-a^p-b^p$ は $p$ で割り切れることを示せ.

解答例

 $0 < k < p$ なる整数 $k$ に対して, $k!$ と $(p-k)!$ は $p$ で割り切れないから, ${}_p\mathrm C_k = \dfrac{p!}{k!(p-k)!}$ は $p$ で割り切れる. よって, \[ (a+b)^p-a^p-b^p = \sum _{k = 1}^{p-1}{}_p\mathrm C_ka^kb^{p-k}\] は $p$ で割り切れる.

解説

 この性質は, 素数 $p$ に関する現象を研究する整数論で中心的な役割を果たす.

その他

問題≪累乗数の下位≫

 十進法において, $101^{100}$ の下 $5$ 桁の値を求めよ.

解答例

\begin{align*} &101^{100} \\ &= (100+1)^{100} \\ &= 100^{100}+\cdots \\ &\qquad +{}_{100}\mathrm C_3100^3+{}_{100}\mathrm C_2100^2+{}_{100}\mathrm C_1100+1 \\ &= 10^{200}+\cdots \\ &\qquad +{}_{100}\mathrm C_310^6+4950\cdot 10^4+100\cdot 100+1 \\ &= 10^5(10^{195}+\cdots +{}_{100}\mathrm C_310+495)+10001. \end{align*} ゆえに, $101^{100}$ の下 $5$ 桁は, $10001.$