連続するn個の整数の積と二項係数

連続するn個の数の積： $m(m-1)\cdots(m-n+1)=\dfrac{m!}{(m-n)!}$ が $n!$ で割り切れることは，$\dfrac{m!}{n!(m-n)!}$ が整数であることと同値である。

任意の素数 $p$ に対して，上式の分母と分子がそれぞれ素因数 $p$ を何個持つか数え，分子の方が多く持っていることを示せばよい。 ルジャンドルの定理より，$m!$ が持つ素因数 $p$ の数は，

${\displaystyle\sum_{i=1}^{\infty}\left\lfloor \dfrac{m}{p^i} \right\rfloor}$ 個。

同様に，$n!(m-n)!$ が持つ素因数 $p$ の数は，

${\displaystyle\sum_{i=1}^{\infty}\left(\left\lfloor \dfrac{n}{p^i} \right\rfloor+\left\lfloor \dfrac{m-n}{p^i} \right\rfloor\right)}$ 個。

これと，フロアー関数の性質： $\lfloor x+y \rfloor\geq\lfloor x \rfloor+\lfloor y \rfloor$ （和を取って切り捨てるよりも，切り捨ててから和を取ったほうが小さい）より，目標の定理が示された。

$m$ 個から $n$ 個選ぶ組み合わせの数は ${}_m\mathrm{C}_n=\dfrac{m!}{n!(m-n)!}$ 通りであり，これは紛れもない整数なので目標の定理が示された。

${}_m\mathrm{C}_n$ が整数であることを $m$ に関する帰納法で示す。

$m=1$ のときは自明。

$m=k$ のとき ${}_k\mathrm{C}_n\:(n=0, 1,\cdots, k)$ が整数だと仮定すると，二項係数の有名公式より，${}_{k+1}\mathrm{C}_{n}={}_k\mathrm{C}_n+{}_k\mathrm{C}_{n-1}$ も整数 $(n=1,\cdots, k)$ 。また，${}_{k+1}\mathrm{C}_{0}$ と ${}_{k+1}\mathrm{C}_{k+1}$ は $1$ なので整数。

よって，$m=k+1$ のときも主張は成立する。