二項係数

1と2が同値であることを示す。定義1で定まる $\binom{n}{k}$ について、定義2の関係式を示す。$k=0$ のときは
$$\binom{n}{0}=\binom{n}{n}=\frac{n!}{0!n!}=1$$
より明らか。$k>0$ のとき
$$\begin{split} \binom{n+1}{k}-\binom{n}{k}= & ~ \frac{(n+1)n\cdots (n-k+2)-n(n-1)\cdots (n-k+2)(n-k+1)}{k!} \\ = & ~ \frac{kn\cdots (n-k+2)}{k!}=\frac{n\cdots (n-k+1)}{(k-1)!} \\ = & ~ \binom{n!}{(k-1)!(n-k+1)!} \end{split}$$
より定義2の関係式が成り立つ。
定義2は $\binom{n}{k}$ を一意的に定めるから、定義2で定まる$\binom{n}{k}$ は定義1で定まるものと一致する。よって定義1と定義2は同値である。

つぎに2と3が同値であることを示す。定義3で定まる $\binom{n}{k}$ について、定義2の関係式を示せばよい。
$$U\subset \{1, 2, \ldots, n+1\}, \#U=k, n+1\not\in U \Longleftrightarrow U\subset \{1, 2, \ldots, n\}, \#U=k$$
なので、$U\subset \{1, 2, \ldots, n+1\}, \#U=k$ となる $U$ のうち $n+1$ を含まないものの個数は $\binom{n}{k}$ に等しい。一方、
$$U\subset \{1, 2, \ldots, n+1\}, \#U=k, n+1\in U\Longleftrightarrow U\setminus\{n+1\}\subset \{1, 2, \ldots, n\}, \#(U\setminus\{n+1\})=k-1$$
なので、$U\subset \{1, 2, \ldots, n+1\}, \#U=k$ となる $U$ のうち $n+1$ を含むものの個数は $\binom{n}{k-1}$ に等しい。よって定義2の関係式が成り立つ。

$$(x+y)^n=\sum_{k=0}^n a_{n, k} x^k y^{n-k}$$
と展開すると、
$$\begin{split} (x+y)^{m+1}= & (x+y)^m(x+y) \\ = & (x+y)\sum_{k=0}^n a_{m, k} x^k y^{m-k} \\ = & \sum_{k=0}^n a_{m, k} x^{k+1} y^{m-k}+\sum_{k=0}^n a_{m, k} x^k y^{m+1-k} \\ = & \sum_{k=1}^{n+1} a_{m, k-1} x^k y^{m+1-k}+\sum_{k=0}^n a_{m, k} x^k y^{m+1-k} \end{split}$$
となるから、$a_{m+1, 0}=a_{m, 0}$, $a_{m+1, m+1}=a_{m, m}$ かつ $1\leq k\leq m$ のとき
$$a_{m+1, k}=a_{m, k-1}+a_{m, k}$$
となる。

さて、$n=1$ のとき
$$a_{1, 0}=a_{1, 1}=1=\binom{1}{0}=\binom{1}{1}$$
となるから、 定義2 より二項定理が成り立つ。$n=m$ のとき $k=0, 1, \ldots, m$ について $a_{m, k}=\binom{m}{k}$ となるとすると
$a_{m+1, 0}=a_{m, 0}=1=\binom{m+1}{0}$, $a_{m+1, m+1}=a_{m, m}=1=\binom{m+1}{m+1}$ かつ $1\leq k\leq m$ のとき
$$a_{m+1, k}=\binom{m}{k-1}+\binom{m}{k}=\binom{m+1}{k}$$
となるから、 定義2 より$n=m+1$ についても二項定理は正しいことがわかる。

二項定理より
$$\sum_{0\leq k \leq n} (-1)^k \binom{n}{k}=(1-1)^n=0$$
だが、$(1+(-1)^k)/2$ は $k$ が偶数のとき $1$、奇数のとき $0$ となるので
$$\sum_{0\leq 2i \leq n} \binom{n}{2i}=\sum_{0\leq k \leq n} \frac{1+(-1)^k}{2} \binom{n}{k}=\frac{2^n+0}{2}=2^{n-1}.$$

二項定理より直ちに得られる
$$(X+1)^n=\sum_{k=0}^n \binom{n}{k} X^k$$
の両辺を $X$ で微分し、
$$n(X+1)^{n-1}=\sum_{k=1}^n k\binom{n}{k} X^{k-1}$$
となる。$X=1$ を代入し、
$$n\times 2^{n-1}=\sum_{k=1}^n \binom{n}{k}$$
を得る。$k=0$ のとき $k\binom{n}{k}=0$ だから、和をとる範囲を $k=0$ から始めても、この等式は成り立つ。

等式
$$(X+1)^{n_1+n_2+\cdots +n_p}=(X+1)^{n_1}(X+1)^{n_2}\cdots (X+1)^{n_p}$$
の左辺と右辺の $X^m$ の係数は、それぞれ上記の等式の左辺と右辺に等しい。

各 $n$ について、$m$ に関する帰納法で証明する。
$m=0$ のとき、両辺ともに $1$、$m=1$ のとき
$$\binom{n}{0}-\binom{n}{1}=1-n=-\binom{n-1}{1}$$
であるから、上記の等式は成立する。
$2\leq m\leq n$ で、上記の等式が $m-1$ について成立すると仮定すると、
$$\begin{split} \sum_{k=0}^m (-1)^k\binom{n}{k}= & (-1)^{m-1}\binom{n-1}{m-1}+(-1)^m\binom{n}{m} \\ = & (-1)^m(\binom{n}{m}-\binom{n-1}{m-1}) \\ = & (-1)^m \binom{n-1}{m} \end{split}$$
となって、$m$ について上記の等式が成立する。