COMPASS

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

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

二項定理

二項定理

定理≪二項定理≫

 すべての正の整数 $n$ に対して, \[ (x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_kx^{n-k}y^k\] が成り立つ.

証明

 左辺 $(x+y)^n = (x+y)\cdots (x+y)$ を展開すると, 各かっこ $(x+y)$ において $x,$ $y$ のいずれかを選んで掛け合わせることで $x^{n-k}y^k$ ($0 \leqq k \leqq n$)の形の項が得られ, 逆にこの形以外の項は出てこない. $x^{n-k}y^k$ の形の項は, $n$ 個のかっこのうち $k$ 個から $y$ を選ぶ方法の総数 ${}_n\mathrm C_k$ だけあるから, 同類項をまとめると求める等式が得られる.

問題≪二項係数の関係式とフェルマーの小定理≫

 $p$ を素数とし, $k$ を $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)!\{ (p-1)-(k-1)\} !} \\ &= p\,{}_{p-1}\mathrm C_{k-1} \end{align*} が成り立つ.
(2)
(1) から, $k\,{}_p\mathrm C_k$ は $p$ の倍数である.
$p$ は素数であり, $1 \leqq k \leqq p-1$ であるから, $p,$ $k$ は互いに素である.
よって, ${}_p\mathrm C_k$ は $p$ の倍数である.
(3)
(I)
$a \geqq 0$ のとき. $a$ に関する数学的帰納法で示す.
(i)
$a = 0$ のとき. $0^p-0 = 0$ から, $a^p-a$ は $p$ の倍数である.
(ii)
与えられた非負整数 $a$ に対して $a^p-a$ が $p$ の倍数であるとする. このとき, (2) から \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*} は $p$ の倍数となる.
(i), (ii) から, $a \geqq 0$ のとき $a^p-a$ は $p$ の倍数である.
(II)
$a < 0,$ $p \geqq 3$ のとき. $p$ は奇数であるから $(-a)^p-(-a) = -(a^p-a)$ であり, これは (i) から $p$ の倍数である. よって, $a^p-a$ も $p$ の倍数である.
(III)
$a < 0,$ $p = 2$ のとき. $a^2-a = a(a-1)$ は偶数であるから, $a^p-a$ は $p$ の倍数である.
(I)~(III) から, 各整数 $a$ に対して $a^p-a$ は $p$ の倍数である.

別解

(1)
$p$ 人から $k$ 人を選び, その $k$ 人からリーダー $1$ 人を選ぶ方法は, 全部で ${}_p\mathrm C_k\cdot k$ 通りある. 同様にするには, $p$ 人からリーダー $1$ 人 L を選んでおき, L を除く $p-1$ 人から残りの $k-1$ 人を選ぶこともできるから, これは $p{}_{p-1}\mathrm C_{k-1}$ に等しい. よって, $k\,{}_p\mathrm C_k = p\,{}_{p-1}\mathrm C_{k-1}$ が成り立つ.

背景

  • (3) で示した命題は,「フェルマーの小定理」(Fermat's little theorem)と呼ばれ, 整数論の諸定理の証明に使われている.
  • この定理の対偶から, ある整数 $a$ に対して $a^n-a$ が $n$ の倍数とならないような $1$ より大きい整数 $n$ は合成数であることが言える. これは, 素数の候補の絞り込みに利用されている.

問題≪フロベニウス準同型≫

 整数 $a,$ $b$ と素数 $p$ に対して, $(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^{n-k}b^k\] は $p$ で割り切れる.

背景

 整数を素数 $p$ で割った余りの集合として定義される「$p$ 元体」(field of order $p$)という数の世界において, 関数 $f(x) = x^p$ は「フロベニウス準同型」(Frobenius homomorphism)と呼ばれ, 基本的な役割を果たす. 本問で示したことは, 加法に関して「準同型」(homomorphism)であるという $f$ の性質 \[ f(x+y) = f(x)+f(y)\] に対応している.

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

 二項係数について
(1) $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k = 2^n$  (2) $\displaystyle\sum_{k = 0}^n(-1)^k{}_n\mathrm C_k = 0$
が成り立つことを示せ.

解答例

(1)
二項定理の公式 \[(x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_kx^ky^{n-k} \quad \cdots [*]\] に $x = y = 1$ を代入すると \[ 2^n = (1+1)^n = \sum_{k = 0}^n{}_n\mathrm C_k\cdot 1^k\cdot 1^{n-k} = \sum_{k = 0}^n{}_n\mathrm C_k\] となる.
(2)
$[*]$ に $x = -1,$ $y = 1$ を代入すると \[ 0 \!=\! (-1\!+\!1)^n \!=\! \sum_{k = 0}^n{}_n\mathrm C_k\!\cdot\!(-1)^k\!\cdot\!1^{n-k} \!=\! \sum_{k = 0}^n(-1)^k{}_n\mathrm C_k\] となる.

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

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

解答例

(1)
\[ (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$ にわたる和を意味する. 両辺の各項の係数を比較すると, 求める等式が得られる.
(2)
(1) において $m = n = r$ とすると, \begin{align*} \sum_{k = 0}^n({}_n\mathrm C_k\cdot {}_n\mathrm C_{n-k}) &= {}_{n+n}\mathrm C_n \\ \sum_{k = 0}^n{}_n\mathrm C_k{}^2 &= {}_{2n}\mathrm C_n \end{align*} が得られる.

背景

 (1)の等式は「ファンデルモンドの畳み込み」(Vandermonde's convolution)として知られている.