二項係数

$1\leq k\leq n-1$ では、通分して次を得る。
$$\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{(n-1)!(n-k+k)}{k!(n-k)!}=\binom nk.$$
$k=0$ では右辺は $1+0$ であり、$k=n$ では $0+1$ である。
$k<0$ または $k>n$ では両辺とも $0$ である。
対称性は定義式で $k$ と $n-k$ を入れ替えても分母が変わらないことから従う。

$0$ 行は初期値と範囲外の約束で決まる。
各行は直前の行から決まるので、数学的帰納法により一意である。
階乗の比は同じ初期値と Pascal の関係式を満たすから、この値に一致する。

空集合の部分集合は空集合一つである。
$n\geq1$ のとき一つの元 $x$ を固定し、$k$ 元部分集合を $x$ を含まないものと含むものに分ける。
前者は残りの $n-1$ 元から $k$ 元を選ぶ方法と一対一に対応する（全単射）。
後者は $x$ を取り除くことにより、残りの $n-1$ 元から $k-1$ 元を選ぶ方法と一対一に対応する。
範囲外の個数を $0$ とすれば、個数は prop-binomial-coefficient-recursive の再帰条件を満たすので二項係数に等しい。

素数付値による方法。
素数 $p$ と正整数 $M$ に対し、$v_p(M)$ を $p^e$ が $M$ を割り切る最大の非負整数 $e$ とする（p進付値）。
階乗の Legendre の公式 $v_p(m!)=\sum_{r\ge1}\lfloor m/p^r\rfloor$（Legendreの公式）を、非負整数 $n,k,n-k$ に適用する。
任意の実数 $a,b$ に対し、床関数の性質から $\lfloor a\rfloor+\lfloor b\rfloor\leq\lfloor a+b\rfloor$ である。
実際、各実数を整数部分と $0$ 以上 $1$ 未満の小数部分に分ければ、この不等式を得る。
各 $r\geq1$ で $a=k/p^r,\ b=(n-k)/p^r$ として足すと、次が従う。
$$v_p(k!)+v_p((n-k)!)\leq v_p(n!).$$
すべての素数についてこの不等式が成り立つので、素因数分解の一意性により $k!(n-k)!$ は $n!$ を割り切る。
比は正であるから正整数である。

群の位数による方法。
$A=\{1,\ldots,k\}$、$B=\{k+1,\ldots,n\}$ とおく。
対称群 $S_n$ のうち $A$ と $B$ をそれぞれ集合として保つ置換全体を $H$ とする。
恒等置換は $H$ に属する。
$H$ の二元の合成は各集合を保つ。
$H$ の元の逆置換も各集合を保つ。
したがって $H$ は部分群である。
制限写像 $\sigma\mapsto(\sigma|_A,\sigma|_B)$ は、逆写像を二つの置換の貼り合わせで与えられる群同型 $H\cong S_A\times S_B$ である。
対称群の位数公式から $|H|=k!(n-k)!$、$|S_n|=n!$ である。
空集合の置換も空写像一つなので、$k=0$ や $k=n$ や $n=0$ を含む。
Lagrangeの定理により商 $|S_n|/|H|=\binom nk$ は正整数である。

Pascal の関係式による方法。
$n=0$ では $\binom00=1$ である。
$n-1$ 行の範囲内の値が正整数であると仮定する。
$n$ 行の端の値は $1$ である。
$1\leq k\leq n-1$ では Pascal の関係式により二つの正整数を足すので、$\binom nk$ も正整数である。
数学的帰納法で結論を得る。

分子 $(-n)(-n-1)\cdots(-n-k+1)$ の各因子から $-1$ を括り出すと $(-1)^k\,n(n+1)\cdots(n+k-1)$ であり、$n\ge1$ ならこれは $(-1)^k(n+k-1)!/(n-1)!$ に等しい。$k!$ で割れば右辺を得る。$n=0$ では $k\ge1$ のとき両辺とも $0$、$k=0$ のとき両辺とも $1$ である。

$n=0$ では両辺とも単位元である。
$n-1$ での式に $x+y$ を掛けると、可換性により $x^k y^{n-k}$ の係数は $\binom{n-1}{k-1}+\binom{n-1}k$ になる。
Pascal の関係式でこれが $\binom nk$ に等しいので、帰納法で式を得る。

整数環の二項定理で $x=y=1$ とおく。

二項定理で $x=1,y=1$ とした式と、$x=-1,y=1$ とした式を足す。
奇数添字の項は消え、偶数添字の項は二倍になる。
$n\geq1$ なので $(1-1)^n=0$ であり、全和の半分を得る。

$1\leq k\leq n$ では階乗の比から $k\binom nk=n\binom{n-1}{k-1}$ である。
これを足し、$k=0$ の項が $0$ であることと $n-1$ 行の全和を用いる。

別証明（形式微分）。
整数係数多項式の二項定理 $(1+T)^n=\sum_{k=0}^n\binom nk T^k$ を形式微分する。
$$n(1+T)^{n-1}=\sum_{k=1}^n k\binom nk T^{k-1}.$$
$T=1$ を代入すると、$n2^{n-1}=\sum_{k=1}^n k\binom nk$ となる。
$k=0$ の項は $0$ なので、和を $k=0$ から始めても値は変わらない。

整数係数多項式の恒等式 $(1+T)^{n_1+\cdots+n_r}=\prod_{i=1}^r(1+T)^{n_i}$ を二項定理で展開する。
両辺の $T^m$ の係数を比較すれば式を得る。
$m$ が次数を超える場合も、範囲外の二項係数を $0$ とする約束により成り立つ。

多変数の畳み込みで $r=2,n_1=a,n_2=b$ とおく。

対称性 $\binom m{m-k}=\binom mk$ を用い、二変数の公式で $a=b=m$ とおけば結論を得る。

各項に Pascal の関係式を代入すると、次の二つの和になる。
$$\sum_{k=0}^m(-1)^k\binom{n-1}k-\sum_{j=0}^{m-1}(-1)^j\binom{n-1}j.$$
共通する項が相殺され、最初の和の末項だけが残る。
$m=0$ では後の和を空和とする。

別証明（帰納法）。
$n\geq1$ を固定して $m$ に関する数学的帰納法を用いる。
$m=0$ では両辺とも $1$ である。
$1\leq m\leq n$ で $m-1$ の式を仮定すると、次を得る。
$$\sum_{k=0}^m(-1)^k\binom nk=(-1)^{m-1}\binom{n-1}{m-1}+(-1)^m\binom nm.$$
Pascal の関係式を使えば、この右辺は $(-1)^m\binom{n-1}m$ に等しい。
したがって帰納法により $0\leq m\leq n$ で成り立つ。

$N$ に関する帰納法による。$N=0$ では、$k=0$ なら両辺とも $1$、$k\ge1$ なら両辺とも $0$ である。$N\ge1$ で $N-1$ の式を仮定すると、左辺は $\binom{N}{k+1}+\binom Nk$ であり、Pascal の関係式により $\binom{N+1}{k+1}$ に等しい。

$(1-T)\sum_{n\ge0}T^n=1$ は係数の相殺で確かめられる。後の式を $k$ に関する帰納法で示す。$k=0$ は上の等式である。$k-1$ の式に $(1-T)^{-1}=\sum_mT^m$ を掛けると、$T^N$ の係数は $\sum_{n=0}^{N}\binom{n+k-1}{k-1}$ であり、prop-binomial-coefficient-hockey-stick（$k-1$、$N+k-1$ に適用し、$n< k-1$ の項が $0$ であることを用いる）により $\binom{N+k}{k}$ に等しい。前の式は、後の式に $T^k$ を掛け、$n< k$ で $\binom nk=0$ であることを用いれば得られる。

$0< k< p$ なら $k!(p-k)!$ は $p$ で割れず、$p!$ は $p$ で割れるので、整数性と定義式から前者の合同式を得る。
$0\leq k\leq p-1$ では $k!$ は法 $p$ で逆元を持つ。
積 $(p-1)(p-2)\cdots(p-k)$ は $(-1)^k k!$ と合同なので、$k!$ を消去して後者の合同式を得る。
$k=0$ の積は空積である。

整数性と階乗の比の定義から、$v_p(\binom nk)=v_p(n!)-v_p(k!)-v_p((n-k)!)$ である。
階乗の Legendre の公式を三つの階乗に適用すれば、表示した和を得る。
$n=k=0$ でも左辺は $v_p(1)=0$ であり、右辺も $0$ である。

$a=k,b=n-k$ とし、その $p$ 進表示の第 $i$ 桁をそれぞれ $a_i,b_i$、和の第 $i$ 桁を $d_i$ とする。
最下位を $i=0$ とし、繰り上がりを $c_0=0$ と $a_i+b_i+c_i=d_i+pc_{i+1}$ で定める。
各桁は $0$ 以上 $p-1$ 以下なので、$c_i$ は $0$ または $1$ である。
下位 $r$ 桁の式を重み $p^i$ で足すと、$a\bmod p^r+b\bmod p^r=n\bmod p^r+p^r c_r$ となる。
$a+b=n$ と合わせれば、$c_r=\lfloor n/p^r\rfloor-\lfloor a/p^r\rfloor-\lfloor b/p^r\rfloor$ である。
十分上の桁では $c_r=0$ である。
素数付値の公式に代入すると $v_p(\binom nk)=\sum_{r\geq1}c_r$ となり、これが繰り上がりの回数である。

有限体 $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ 上の多項式環 $\mathbb{F}_p[T]$ で考える。二項定理と prop-binomial-coefficient-prime により $(1+T)^p=1+T^p$ である。これを繰り返して $(1+T)^{p^i}=1+T^{p^i}$ を得るので、
$$(1+T)^n=\prod_{i=0}^{s}\bigl((1+T)^{p^i}\bigr)^{n_i}=\prod_{i=0}^{s}(1+T^{p^i})^{n_i}=\prod_{i=0}^{s}\left(\sum_{j_i=0}^{n_i}\binom{n_i}{j_i}T^{j_ip^i}\right)$$
となる。右辺を展開した各項の指数は $\sum_ij_ip^i$（$0\le j_i\le n_i\le p-1$）であり、$p$ 進表示の一意性により、指数 $k$ を与える組 $(j_i)$ は $j_i=k_i$（すべての $i$）ただ一つである（ある $i$ で $k_i>n_i$ なら該当する組はなく、そのとき $\binom{n_i}{k_i}=0$ である）。よって両辺の $T^k$ の係数を比べて主張の合同式を得る。後半は、$0\le k_i,n_i\le p-1$ のとき $\binom{n_i}{k_i}$ が $p$ で割り切れないことと $k_i\le n_i$ が同値であることから従う。$k_i>n_i$ のときは $\binom{n_i}{k_i}=0$ なので $p$ で割り切れる。$k_i\le n_i< p$ のとき、$n_i!$ は $p$ で割り切れず、$\binom{n_i}{k_i}\cdot k_i!\,(n_i-k_i)!=n_i!$ より $\binom{n_i}{k_i}$ も $p$ で割り切れない。