名古屋大学 2013年 理系 第3問 解説

方針・初手

二項定理の展開式を作り出すことが鍵となる。$T_m(n)$ の定義式に $S_k(n)$ の定義を代入し、和を取る順序を交換（$\Sigma$の交換）することで、二項定理が適用できる形が現れることに着目する。(3) は (2) で得られた結果に $n=p-1$ を代入し、帰納法を用いて $k$ が小さい順に $p$ の倍数であることを示すとよい。

解法1

(1)

$T_m(1) = \sum_{k=1}^{m-1} {}_mC_k S_k(1)$

$S_k(1) = 1^k = 1$ であるから、

$$ T_m(1) = \sum_{k=1}^{m-1} {}_mC_k $$

二項定理より、$(1+1)^m = \sum_{k=0}^m {}_mC_k = {}_mC_0 + \sum_{k=1}^{m-1} {}_mC_k + {}_mC_m$ である。 ${}_mC_0 = 1, {}_mC_m = 1$ であるから、

$$ 2^m = 1 + T_m(1) + 1 $$

したがって、

$$ T_m(1) = 2^m - 2 $$

次に $T_m(2)$ を求める。

$$ T_m(2) = \sum_{k=1}^{m-1} {}_mC_k S_k(2) = \sum_{k=1}^{m-1} {}_mC_k (1^k + 2^k) = \sum_{k=1}^{m-1} {}_mC_k 1^k + \sum_{k=1}^{m-1} {}_mC_k 2^k $$

ここで、第1項は $T_m(1)$ に等しい。第2項について、二項定理より、$(1+2)^m = \sum_{k=0}^m {}_mC_k 2^k = 1 \cdot 2^0 + \sum_{k=1}^{m-1} {}_mC_k 2^k + 1 \cdot 2^m$ であるから、

$$ \sum_{k=1}^{m-1} {}_mC_k 2^k = 3^m - 2^m - 1 $$

よって、

$$ T_m(2) = (2^m - 2) + (3^m - 2^m - 1) = 3^m - 3 $$

(2)

$T_m(n)$ の定義式に $S_k(n) = \sum_{j=1}^n j^k$ を代入し、和の順序を交換する。

$$ \begin{aligned} T_m(n) &= \sum_{k=1}^{m-1} {}_mC_k \left( \sum_{j=1}^n j^k \right) \\ &= \sum_{j=1}^n \left( \sum_{k=1}^{m-1} {}_mC_k j^k \right) \end{aligned} $$

ここで、二項定理 $(1+j)^m = \sum_{k=0}^m {}_mC_k j^k = 1 + \sum_{k=1}^{m-1} {}_mC_k j^k + j^m$ より、

$$ \sum_{k=1}^{m-1} {}_mC_k j^k = (j+1)^m - j^m - 1 $$

これを代入すると、

$$ \begin{aligned} T_m(n) &= \sum_{j=1}^n \left( (j+1)^m - j^m - 1 \right) \\ &= \sum_{j=1}^n \left( (j+1)^m - j^m \right) - \sum_{j=1}^n 1 \end{aligned} $$

第1項は隣り合う項が相殺される形（階差数列の和）であり、

$$ \sum_{j=1}^n \left( (j+1)^m - j^m \right) = (n+1)^m - 1^m = (n+1)^m - 1 $$

また、第2項は $\sum_{j=1}^n 1 = n$ であるから、

$$ T_m(n) = (n+1)^m - 1 - n = (n+1)^m - n - 1 $$

(3)

(2) の結果に $n = p-1$ を代入すると、

$$ T_m(p-1) = (p-1+1)^m - (p-1) - 1 = p^m - p $$

これが任意の $m \ge 2$ について成り立つことを用いて、$1 \le k \le p-2$ における $S_k(p-1)$ が $p$ の倍数であることを、$k$ についての数学的帰納法で示す。

(I) $k=1$ のとき

$m=2$ とすると、$T_2(p-1) = {}_2C_1 S_1(p-1) = 2 S_1(p-1)$ である。 一方で上の式より $T_2(p-1) = p^2 - p = p(p-1)$ であるから、

$$ 2 S_1(p-1) = p(p-1) $$

$p$ は $3$ 以上の素数であるから、$2$ と $p$ は互いに素である。また、$p(p-1)$ は $p$ の倍数である。 したがって、$S_1(p-1)$ は $p$ の倍数である。

(II) $1 \le j \le k-1$ に対して、$S_j(p-1)$ が $p$ の倍数であると仮定する

ただし、$k$ は $2 \le k \le p-2$ を満たす整数とする。 $m = k+1$ （このとき $3 \le m \le p-1$）として $T_{k+1}(p-1)$ を考えると、

$$ \begin{aligned} T_{k+1}(p-1) &= \sum_{j=1}^k {}_{k+1}C_j S_j(p-1) \\ &= \sum_{j=1}^{k-1} {}_{k+1}C_j S_j(p-1) + {}_{k+1}C_k S_k(p-1) \\ &= \sum_{j=1}^{k-1} {}_{k+1}C_j S_j(p-1) + (k+1) S_k(p-1) \end{aligned} $$

一方で、(2) の結果より、

$$ T_{k+1}(p-1) = p^{k+1} - p = p(p^k - 1) $$

であり、これは $p$ の倍数である。 帰納法の仮定より、$1 \le j \le k-1$ のとき $S_j(p-1)$ は $p$ の倍数であるため、$\sum_{j=1}^{k-1} {}_{k+1}C_j S_j(p-1)$ も $p$ の倍数である。 よって、両者の差である $(k+1) S_k(p-1)$ は $p$ の倍数である。

ここで、$2 \le k \le p-2$ より、$3 \le k+1 \le p-1$ であるから、$k+1$ は素数 $p$ より小さい正の整数となり、$p$ と互いに素である。 したがって、$S_k(p-1)$ は $p$ の倍数である。

(I), (II) より、$1 \le k \le p-2$ を満たす任意の整数 $k$ について、$S_k(p-1)$ は $p$ の倍数であることが示された。

解法2

(3) の別解

$p$ を $3$ 以上の素数、$k$ を $1 \le k \le p-2$ を満たす整数とする。

方程式 $x^k - 1 \equiv 0 \pmod p$ を考える。剰余定理より、この方程式は modulo $p$ において高々 $k$ 個の解しか持たない。 いま、$k \le p-2 < p-1$ であるから、$1, 2, \dots, p-1$ の $p-1$ 個の整数のうち、少なくとも1つは $x^k - 1 \not\equiv 0 \pmod p$ を満たす。 そのような整数の1つを $a$ と固定する（すなわち $a \not\equiv 0 \pmod p$ かつ $a^k \not\equiv 1 \pmod p$）。

$a$ と $p$ は互いに素であるから、集合 $\{1, 2, \dots, p-1\}$ の各要素に $a$ を掛けた集合 $\{a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)\}$ は、modulo $p$ で考えると元の集合 $\{1, 2, \dots, p-1\}$ と一致する。

よって、それぞれの要素を $k$ 乗して和をとったものも、modulo $p$ で合同になる。

$$ \sum_{i=1}^{p-1} i^k \equiv \sum_{i=1}^{p-1} (ai)^k \pmod p $$

$$ S_k(p-1) \equiv a^k \sum_{i=1}^{p-1} i^k \pmod p $$

$$ S_k(p-1) \equiv a^k S_k(p-1) \pmod p $$

整理すると、

$$ (a^k - 1) S_k(p-1) \equiv 0 \pmod p $$

ここで、選び方から $a^k - 1 \not\equiv 0 \pmod p$ であり、$a^k - 1$ と $p$ は互いに素である。 したがって、$S_k(p-1) \equiv 0 \pmod p$ となり、$S_k(p-1)$ が $p$ の倍数であることが示された。

解説

・(1), (2) は和の記号 $\Sigma$ を入れ替えることで、二項定理を用いて式を簡略化する手法である。$\sum_{k} \sum_{j}$ の和の順序を交換し、内側の $\Sigma$ を先に計算するのは難関大で頻出のテクニックである。 ・(3) は (2) で導いた $T_m(n)$ の一般項を利用し、数学的帰納法で証明するのが出題者の意図と考えられる。帰納法の仮定から、求める項以外がすべて $p$ の倍数であることを利用して連鎖的に示していく構造になっている。 ・解法2で示したように、整数の剰余系における全単射性を利用した証明も鮮やかである。フェルマーの小定理の証明と同様の論理構造を持っているため、整数問題の背景知識として身につけておきたい。

答え

(1) $T_m(1) = 2^m - 2, \quad T_m(2) = 3^m - 3$ (2) $T_m(n) = (n+1)^m - n - 1$ (3) $p$ が $3$ 以上の素数のとき、$k = 1, 2, 3, \dots, p-2$ に対して $S_k(p-1)$ は $p$ の倍数である。