有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

二項定理

二項定理

定理≪二項定理≫

 すべての正の整数 $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$ だけあるから, 同類項をまとめると求める等式が得られる.

別証明: 数学的帰納法(数学 B)と「パスカルの法則」を利用

(i)
$(x+y)^1 = x+y = {}_1\mathrm C_0x^1y^0+{}_1\mathrm C_1x^0y^1$ から, $n = 1$ のとき等式が成り立つ.
(ii)
$n = m$ ($m$: 正の整数)のとき等式が成り立つとすると, \begin{align*} &(x+y)^{m+1} = (x+y)(x+y)^m \\ &= x(x+y)^m+y(x+y)^m \\ &= x\sum_{k = 0}^m{}_m\mathrm C_kx^ky^{m-k}+y\sum_{k = 0}^m{}_m\mathrm C_kx^ky^{m-k} \\ &= \sum_{k = 0}^m{}_m\mathrm C_kx^{k+1}y^{m-k}+\sum_{k = 0}^m{}_m\mathrm C_kx^ky^{m+1-k} \\ &= x^{m+1}+\sum_{k = 1}^m({}_m\mathrm C_{k-1}+{}_m\mathrm C_k)x^ky^{m+1-k}+y^{m+1} \\ &= \sum_{k = 0}^{m+1}{}_{m+1}\mathrm C_kx^ky^{m+1-k} \end{align*} となるから, $n = m+1$ のとき等式が成り立つ. ここで, 最後の等号は「パスカルの法則」${}_n\mathrm C_r+{}_n\mathrm C_{r+1} = {}_{n+1}\mathrm C_{r+1}\ (0 \leqq r < n)$ により従う.
(i), (ii) から, すべての正の整数 $n$ に対して求める等式が成り立つ.

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

 $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$ の倍数である.
(参考: 1998 奈良女子大)

解答例

(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 map)と呼ばれ, 基本的な役割を果たす. 本問で示したことは, 加法に関して「準同型写像」(homomorphism)であるという $f$ の性質 \[ f(x+y) = f(x)+f(y)\] に対応している.

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

 $n$ を正の整数とする. 二項係数について
(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$
(3) $\displaystyle\sum_{k = 0}^nk\,{}_n\mathrm C_k = n\cdot 2^{n-1}$
が成り立つことを示せ.

解答例

(1)
二項定理の等式 \[ (x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_kx^{n-k}y^k \quad \cdots [*]\] に $x = y = 1$ を代入すると \[ 2^n = (1+1)^n = \sum_{k = 0}^n{}_n\mathrm C_k\cdot 1^{n-k}\cdot 1^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^{n-k}\!\cdot\!(-1)^k \!=\! \sum_{k = 0}^n(-1)^k{}_n\mathrm C_k\] となる.
(3)
\[ S = \sum_{k = 0}^nk\,{}_n\mathrm C_k\] とおくと, \[ S = \sum_{k = 0}^nk\,{}_n\mathrm C_{n-k} = \sum_{k = 0}^n(n-k){}_n\mathrm C_k\] となるので, \begin{align*} 2S &= \sum_{k = 0}^nk\,{}_n\mathrm C_k+\sum_{k = 0}^n(n-k){}_n\mathrm C_k \\ &= \sum_{k = 0}^n\{ k+(n-k)\}{}_n\mathrm C_k \\ &= n\sum_{k = 0}^n{}_n\mathrm C_k = n\cdot 2^n \end{align*} から \[ S = n\cdot 2^{n-1}\] が得られる.

別解 1: 組合せを利用

 $1$ 以上 $n$ 以下の整数全体からなる集合 $\{ 1,\cdots,n\}$ を $A$ とおく.
(1)
$A$ の部分集合の個数は, $k$ 個の要素からなる部分集合の個数の和と考えると $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k$ と表され, 各整数が部分集合に属するか否かを考えると $2^n$ と表される. よって, 求める等式が成り立つ.
(2)
$A$ の偶数個の要素からなる部分集合の個数, 奇数個の要素からなる部分集合の個数は, $2k,$ $2k+1$ 個の要素からなる部分集合の個数の和と考えるとそれぞれ ${}_n\mathrm C_0+{}_n\mathrm C_2+\cdots,$ ${}_n\mathrm C_1+{}_n\mathrm C_3+\cdots$ と表され, $1$ から $n-1$ までの整数が部分集合に属するか否かを考える($n$ はそれに応じて部分集合に属するか否かが自動的に決まると考える)とともに $2^{n-1}$ と表される. よって, \[{}_n\mathrm C_0+{}_n\mathrm C_2+\cdots = {}_n\mathrm C_1+{}_n\mathrm C_3+\cdots = 2^{n-1}\] から, $\displaystyle\sum_{k = 0}^n(-1)^k{}_n\mathrm C_k = 0$ が成り立つ.
(3)
$A$ の空集合でない部分集合をとり, さらにその中から $1$ 個の要素(代表と呼ぶ)を選ぶ方法の総数は, $k$ 個の要素からなる部分集合とその代表の組の個数の和と考えると $\displaystyle\sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 0}^nk\,{}_n\mathrm C_k$ と表され, 代表となる要素を選んでからそれ以外の $n-1$ 個の整数が部分集合に属するか否かを考えると $n\cdot 2^{n-1}$ と表される. よって, 求める等式が成り立つ.

別解 2: 二項係数の関係式を利用

(1)
(i)
$n = 1$ のとき, ${}_1\mathrm C_0+{}_1\mathrm C_1 = 1+1 = 2 = 2^1$ から, 等式が成り立つ.
(ii)
$n = m$ ($m$: 正の整数)のとき等式が成り立つとすると, 「パスカルの法則」${}_n\mathrm C_r+{}_n\mathrm C_{r+1} = {}_{n+1}\mathrm C_{r+1}\ (0 \leqq r < n)$ により, \begin{align*} &{}_{m+1}\mathrm C_0+{}_{m+1}\mathrm C_1+\cdots +{}_{m+1}\mathrm C_m+{}_{m+1}\mathrm C_{m+1} \\ &= {}_{m+1}\mathrm C_0+({}_m\mathrm C_0+{}_m\mathrm C_1) \\ &\qquad +\cdots +({}_m\mathrm C_{m-1}+{}_m\mathrm C_m)+{}_{m+1}\mathrm C_{m+1} \\ &= {}_m\mathrm C_0+({}_m\mathrm C_0+{}_m\mathrm C_1) \\ &\qquad +\cdots +({}_m\mathrm C_{m-1}+{}_m\mathrm C_m)+{}_m\mathrm C_m \\ &= 2({}_m\mathrm C_0+\cdots +{}_m\mathrm C_m) \\ &= 2\cdot 2^m = 2^{m+1} \end{align*} となるから, $n = m+1$ のとき等式が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して, 求める等式が成り立つ.
(3)
$k\,{}_n\mathrm C_k = n\,{}_{n-1}\mathrm C_{k-1}$ により, \begin{align*} \sum_{k = 0}^nk\,{}_n\mathrm C_k &= \sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 1}^nn\,{}_{n-1}\mathrm C_{k-1} \\ &= n\sum_{k = 0}^{n-1}\,{}_{n-1}\mathrm C_k = n\cdot 2^{n-1} \end{align*} が成り立つ.

別解 3: 合成関数の微分法を利用(数学 III)

(3)
$(1+x)^n = 1+\displaystyle\sum_{k = 1}^n{}_n\mathrm C_kx^k$ の両辺を $x$ で微分すると \[ n(1+x)^{n-1} = \sum_{k = 1}^nk\,{}_n\mathrm C_kx^{k-1}\] となるから, $x = 1$ を代入すると \[ n\cdot 2^{n-1} = \sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 0}^nk\,{}_n\mathrm C_k\] が得られる.

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

(1)
$m,$ $n$ を正の整数とし, $r$ を $0 \leqq r \leqq m+n$ なる整数とする. $(1+x)^{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)
\[ (1+x)^{m+n} = (1+x)^m(1+x)^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*} が得られる.

別解

(2)
白色の札 $n$ 枚と黒色の札 $n$ 枚に, それぞれ $1$ から $n$ までの番号をふる. これら $2n$ 枚の札から $n$ 枚を取り出す場合の数は, ${}_{2n}\mathrm C_n$ である.
一方, これは, 白色の札から $k$ 枚, 黒色の札から $n-k$ 枚を取り出す場合の数 ${}_n\mathrm C_k\cdot {}_n\mathrm C_{n-k} = {}_n\mathrm C_k{}^2$ の総和と考えると, $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k{}^2$ と表される.
よって, 求める等式が成り立つ.

背景

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