インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

Ruizの恒等式とLerchの合同式

Ruizの恒等式 nを非負整数、xを任意の実数とする。このとき、
\displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^n=n!
が成り立つ。

証明. nに関する帰納法で証明する。

\displaystyle f_n(x):=\sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^n

とおく。f_0(x)=1=0!である。f_n(x)=n!であると仮定して、f_{n+1}(x)=(n+1)!を示せばよい。

\begin{equation}\begin{split} f'_{n+1}(x) &= \frac{d}{dx}\left\{ \sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}(x-k)^{n+1} \right\} \\ &=(n+1)\sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}(x-k)^n \\ &= (n+1) \left\{ \sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^n+(-1)^{n+1}(x-n-1)^n \right. \\ & \left. \ \ \ \ \ \ \ \ \ \ \ +\sum_{k=1}^n(-1)^k\binom{n}{k-1}(x-k)^n \right\} \\ &= (n+1)\left\{ f_n(x)+\sum_{k=0}^n(-1)^{k+1}\binom{n}{k}(x-1-k)^n \right\} \\ &= (n+1)\{f_n(x)-f_n(x-1)\} \\ &= (n+1)(n!-n!)=0\end{split}\end{equation}

より、f_{n+1}(x)は定数であることがわかる。従って、

\begin{equation}\begin{split} f_{n+1}(x) &= f_{n+1}(n+1) \\ &= \sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}(n+1-k)^{n+1} \\ &= (n+1)\sum_{k=0}^n(-1)^k\binom{n}{k}(n+1-k)^n \\ &=(n+1)f_n(n+1)\\ &= (n+1)n! \\ &=(n+1)! \end{split}\end{equation}

を得る。 Q.E.D.

Ruizはこの恒等式を用いてWilsonの定理の別証明を与えていますが、Lerchの合同式の別証明を与えることもできます:
integers.hatenablog.com

補題1 pを素数とし、kk < pを満たす非負整数とする。このとき、
\displaystyle (-1)^k\binom{p-1}{k} \equiv 1-pH_k\pmod{p^2}
が成り立つ。ここで、\displaystyle H_k=\sum_{j=1}^k\frac{1}{j}は第k調和数。

証明. \displaystyle (-1)^k\binom{p-1}{k} = \prod_{j=1}^k\left( 1-\frac{p}{j} \right)より分かる。 Q.E.D.

補題2 pを素数とする。このとき、
\displaystyle \sum_{k=1}^{p-1} H_k \equiv 1 \pmod{p}
が成り立つ。

証明.

\displaystyle \sum_{k=1}^{p-1}H_k = \sum_{k=1}^{p-1}\sum_{j=1}^k\frac{1}{j}=\sum_{j=1}^{p-1}\frac{1}{j}\sum_{k=j}^{p-1}1 = \sum_{j=1}^{p-1}\frac{p-j}{j} \equiv 1 \pmod{p}.
Q.E.D.

Lerchの合同式の別証明 pを奇素数とする。Ruizの恒等式において、n=p-1x=0とすると、(-1)^{p-1}=1に注意して

\begin{equation}\begin{split} (p-1)! &= \sum_{k=1}^{p-1}(-1)^k\binom{p-1}{k}k^{p-1} \\ &\equiv \sum_{k=1}^{p-1}(1-pH_k)(1+pq_p(k)) \pmod{p^2} \\ &\equiv \sum_{k=1}^{p-1}(1+pq_p(k)-pH_k) \pmod{p^2} \\ &\equiv 1+p\sum_{k=1}^{p-1}q_p(k) \pmod{p^2}\end{split}\end{equation}

を得る(二つの補題を用いた)。これより、

\displaystyle \sum_{k=1}^{p-1}q_p(k) \equiv w_p \pmod{p}

が従う。 Q.E.D.

私はこの証明は得意というか或る意味で自然だと思う一方で、実際やってみたらLerchさんの証明の方がエレガントだなと悔しい気持ちもあります(笑)。