文献あり

二項係数についての恒等式と整数値多項式

　こんにちは．昔考えていた話題について再考していたところ，ある程度まとまったので記事として書きます．よろしくお願いします．

　$m = 0, \ldots , n-1$に対して
$$\sum_{k=0}^n (-1)^k k^m \binom{n}{k} = 0$$
が成立する．

　この式の証明はとりあさんの記事にもありますが，ここではこの記事とは異なる証明を紹介します．

帰納法による証明

　まず，「$m = 0, \ldots , n-1$に対して$m$次多項式$f_m(x)$が存在し，
$$f_m(x) (1+x)^{n-m} = \sum_{k=0}^n k^m \binom{n}{k} x^k \tag{1}$$
と表せる」ことを示す．

　$m=0$ のとき，
$$(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$$
より$(1)$は成立する（$f_0(x) = 1$）．

　$m \; (\leq n-2)$での$(1)$の成立を仮定する．$(1)$の両辺を$x$で微分して
$$f'_m(x)(1+x)^{n-m} + (n-m)f_m(x)(1+x)^{n-m-1} = \sum_{k=1}^n k^{m+1} \binom{n}{k} x^{k-1}$$
を得る．この式に両辺$x$を掛けて
$$x(f'_m(x)(1+x) + (n-m)f_m(x))(1+x)^{n-m-1} = \sum_{k=0}^n k^{m+1} \binom{n}{k} x^k$$
を得る．ただし，$\dbinom{n}{0} = 0$であることを用いて右辺に$k=0$を加えた．ここで，$f_m(x)$は$m$次多項式なので$x(f'_m(x)(1+x) + (n-m)f_m(x))$は$m+1$次であるから，$m+1$のとき$(1)$は成立する（$f_{m+1}(x) = x(f'_m(x)(1+x) + (n-m)f_m(x))$である）．
　以上で式$(1)$が示された．この式に$x = -1$を代入して
$$\sum_{k=0}^n (-1)^k k^m \binom{n}{k} = 0$$
が得られる．

　別証も紹介します．やや仰々しい証明です．

Vandermonde行列の逆行列を用いる証明

　$m$元連立方程式
$$0^m+\sum_{k=1}^n k^m x_k = 0 \quad (m=0,\ldots ,n-1)$$
を考える．これを行列の形で書くと
$$\begin{pmatrix} 1 && 1 && 1 && \cdots && 1 \\ 1 && 2 && 3 && \cdots && n \\ 1^2 && 2^2 && 3^2 && \cdots && n^2 \\ \vdots && \vdots && \vdots && \ddots && \vdots \\ 1^{n-1} && 2^{n-1} && 3^{n-1} && \cdots && n^{n-1} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} -1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$
と表せる．ここで，左の行列を$V_n$とし，$V_n^{-1}$の$i$列$j$行を$a_{ij}$と書くと，
$$a_{ij} = (-1)^{n-j} \cdot \left( \prod_{\substack{1 \leq k \leq n \\ k \neq i}} (i-k) \right)^{-1} \cdot \sum_{\substack{1 \leq m_1 < \cdots < m_{n-j} \leq n \\ m_1, \ldots, m_{n-j} \neq i}} \left( \prod_{l=1}^{n-j}m_l \right)$$
と表せる．よって，
\begin{aligned} x_k &= -a_{k1} = -\frac{(-1)^{n-1} \cdot 1 \cdot 2 \cdot \cdots (k-1)(k+1) \cdots (n-1)n}{(k-1)(k-2) \cdots \cdot 2 \cdot 1 \cdot (-1) \cdot \cdots (k-n)} \\ &= - \frac{(-1)^{n-1} \cdot n!}{k! \cdot (-1)^{n-k}(n-k)!} = (-1)^k \binom{n}{k} \end{aligned}
となる．従って，もとの連立方程式に戻って，$m = 0, \ldots , n-1$に対して
$$\sum_{k=0}^n (-1)^k k^m \binom{n}{k} = 0$$
を得る．

　Vandermonde行列の逆行列に関しては子葉さんの記事などをご参照ください．

　この式を用いると以下の事実を証明できます．

　$n$次多項式$P_n(x)$について，以下の2つは同値である：

任意の整数$m$に対して$P_n(m)$は整数である．
ある整数$m_0$が存在して，$P_n(m_0), P_n(m_0+1), \ldots , P_n(m_0+n)$はすべて整数である．

　なお，この定理は定理1を用いなくても証明可能です．

定理2の一般的 (?) な証明

　$(1) \implies (2)$ は明らかに成立するため，$(2) \implies (1)$ を$n$についての帰納法で示す．
　$n = 0$のとき，任意の$m$について$P_0(m) = P_0(m_0)$は整数である．
　$n$での成立を仮定し，$n+1$次多項式$P_{n+1}(x)$について，ある整数$m_0$が存在して$P_{n+1}(m_0), P_{n+1}(m_0+1), \cdots, P_{n+1}(m_0+n+1)$がすべて整数であると仮定する．このとき，$Q(x) = P_{n+1}(x+1) - P_{n+1}(x)$とおくと$Q(x)$は$n$次多項式である．ここで，$Q(m_0) = P_{n+1}(m_0+1) - P_{n+1}(m_0), \cdots, Q(m_0+n) = P_{n+1}(m_0+n+1) - P_{n+1}(m_0+n)$ は整数であるから，帰納法の仮定より任意の整数$m$に対して$Q(m)$は整数である．よって，$P_{n+1}(m_0)$が整数であることと合わせて，任意の整数$m$に対して$P_{n+1}(m)$は整数である．
　よって示された．

　この定理を示す前に以下の補題を示します．

　任意の$n$次多項式$P_n(x)$に対して，
$$\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} P_n(x+k) = 0$$
が恒等的に成立する．

(補題3)

　$\displaystyle P_n(x) = \sum_{r=0}^n a_r x^r$ とおくと，
$$P_n(x+k) = \sum_{r=0}^n a_r (x+k)^r = \sum_{r=0}^n \sum_{m=0}^r a_r \binom{r}{m} k^m x^{r-m}$$
となる．これより
\begin{aligned} \sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} P_n(x+k) &= \sum_{k=0}^{n+1} \sum_{r=0}^n \sum_{m=0}^r (-1)^k \binom{n+1}{k} a_r \binom{r}{m} k^m x^{r-m} \\ &= \sum_{r=0}^n \sum_{m=0}^r a_r \binom{r}{m} \left( \sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} k^m \right) x^{r-m} \end{aligned}
と計算される．ここで，添字の$m$は$0$から$n$までの値を取りうるから，定理1より
$$\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} k^m = 0$$
となる．よって，任意の$n$次多項式$P_n(x)$に対して
$$\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} P_n(x+k) = 0$$
が恒等的に成立することが示された．

(定理2)

　$(1) \implies (2)$ は明らかに成立するため，$(2) \implies (1)$ を$m$についての帰納法で示す．
　$(2)$より，$P_n(m_0), P_n(m_0+1), \cdots , P_n(m_0+n)$は整数である．
　ここで，整数$m'$に対して$P_n(m'), P_n(m'+1), \cdots , P_n(m'+n)$が整数であると仮定する．このとき，補題3より
$$\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} P_n(m'-1+k) = 0 \iff P_n(m'-1) = -\sum_{k=1}^{n+1} (-1)^k \binom{n+1}{k} P_n(m'-1+k)$$
が従い，$P_n(m'), P_n(m'+1), \cdots , P_n(m'+n)$が整数だから$P_n(m'-1)$も整数である．また，
$$\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} P_n(m'+k) = 0 \iff P_n(m'+n+1) = (-1)^n \sum_{k=0}^{n} (-1)^k \binom{n+1}{k} P_n(m'-1+k)$$
が従い，$P_n(m'), P_n(m'+1), \cdots , P_n(m'+n)$が整数だから$P_n(m'+n+1)$も整数である．
　よって，任意の整数$m$に対して$P_n(m)$は整数である．