pCrはpの倍数 - INTEGERS

高校生の皆さん！ $p$ が素数で、 $0 < r < p$ なる整数 $r$ に対して ${}_pC_r$ は必ず $p$ の倍数になります！！

え？そんなことは知ってるって？？

そんなあなたのために、今日は第二種Stirling数ヴァージョンの類似の性質を紹介しましょう。なお、以下では二項係数はいつも通り $\displaystyle \binom{n}{k}$ なる記号を用いることにします。

第二種Stirling数については

integers.hatenablog.com
mathtrain.jp

を参照してください。

目標は次の定理です*1：

定理 $p$ が素数、 $k$ が $1 < k < p$ を満たす整数であるならば、第二種Stirling数 $\displaystyle \left\{ {p \atop k} \right\}$ は $p$ で割り切れる。

第二種Stirling数の二項係数による表示を用います。

補題非負整数 $n, k \ (k \leq n)$ に対し、

$\displaystyle \left\{ {n \atop k} \right\} = \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n$

が成り立つ。

証明. $n$ に関する数学的帰納法で証明する。 $n=(k=)0$ のときは両辺ともに $1$ である。 $n$ のときに成り立つと仮定すると、

$\begin{equation}\begin{split} \left\{ {n+1 \atop k} \right\} &= k\left\{ {n \atop k} \right\}+\left\{ {n \atop k-1} \right\} \\ &= \frac{k}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n + \frac{1}{(k-1)!}\sum_{j=0}^{k-1}(-1)^{k-1-j}\binom{k-1}{j}j^n \\ &= \frac{1}{(k-1)!}\sum_{j=0}^k(-1)^{k-j}\left\{ \binom{k}{j}-\binom{k-1}{j}\right\} j^n \\ &= \frac{1}{(k-1)!}\sum_{j=0}^k(-1)^{k-j}\binom{k-1}{j-1}j^n \\ &= \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^{n+1} \end{split}\end{equation}$