摘 要 本文主要介绍以下的自然数等幂求和问题
$$\sum_{i=1}^n i^k=1^k+2^k+\cdots+n^k$$

  我们已经知道
$$\begin{aligned}&S_0 &&=\sum i^0 &&=n &&=n\\ &S_1 &&=\sum i^1 &&=\frac{n(n+1)}{2} &&=\frac{1}{2}n^2 +\frac{1}{2}n\\ &S_2 &&=\sum i^2 &&=\frac{n(n+1)(2n+1)}{6} &&=\frac{1}{3}n^3 +\frac{1}{2}n^2 +\frac{1}{6}n\\ &S_3 &&=\sum i^3 &&=\left(\frac{n(n+1)}{2}\right)^2 &&=\frac{1}{4}n^4 +\frac{1}{2}n^3 +\frac{1}{4}n^2\\ \end{aligned}$$

1 $S_n$ 的递推公式

  据 Newton 二项式展开定理有
$$(m-1)^\ell=m^\ell-\mathrm C_\ell^1 m^{\ell-1}+\mathrm C_\ell^2 m^{\ell-2}-\cdots +(-1)^{\ell-1}C_\ell^{\ell-1}m + (-1)^\ell$$
移项, 得
$$m^\ell-(m-1)^\ell=\mathrm C_\ell^1 m^{\ell-1}-\mathrm C_\ell^2 m^{\ell-2}+\cdots -(-1)^{\ell-1}C_\ell^{\ell-1}m - (-1)^\ell$$
$m$ 取遍 $1,2,\cdots,n$ 得到 $n$ 条等式, 所有等式两边相加, 得到式(*)
$$n^\ell=\mathrm C_\ell^1 S_{\ell-1}-\mathrm C_\ell^2 S_{\ell-2}+\cdots -(-1)^{\ell-1}C_\ell^{\ell-1}S_1 - (-1)^\ell S_0$$
移项，得
$$S_{\ell-1}=\frac{1}{\ell}\left(n^\ell+\mathrm C_\ell^2 S_{\ell-2}-\cdots +(-1)^{\ell-1}C_\ell^{\ell-1}S_1 + (-1)^\ell S_0\right)$$

2 递推公式的矩阵写法

  在式(*)中将 $n$ 取遍 $1,2,\cdots,k$, 得到一个由 $k$ 条方程组成的方程组
$$\begin{aligned} &n^1 &&= & &S_0\\ &n^2 &&= &-&S_0 &+2&S_1\\ &n^3 &&= & &S_0 &-3&S_1 &+3&S_2\\ &n^4 &&= &-&S_0 &+4&S_1 &-6&S_2 &+4&S_3\\ &\cdots\\ &n^k &&= &*&S_0 &+*&S_1 &+*&S_2 &+*&S_3 &+&\cdots &+k&S_{k-1} \end{aligned}$$
写成矩阵形式
$$\begin{pmatrix} n^1\\ n^2\\ n^3\\ n^4\\ \vdots\\ n^k \end{pmatrix} = \begin{pmatrix} 1\\ -1 & 2\\ 1 & -3 & 3\\ -1 & 4 & -6 & 4\\ \vdots & \vdots & \vdots & \vdots & \ddots\\ * & * & * & * & \cdots & k\\ \end{pmatrix} \begin{pmatrix} S_0\\ S_1\\ S_2\\ S_3\\ \vdots\\ S_{k-1} \end{pmatrix}$$
不妨简写为
$$\boldsymbol n=A\boldsymbol S$$
其中矩阵 $A=(a_{ij})_{n\times n}$ 中隐藏了一个杨辉三角
$$P = \begin{pmatrix} 1\\ 1 & 2\\ 1 & 3 & 3\\ 1 & 4 & 6 & 4\\ \vdots & \vdots & \vdots & \vdots & \ddots\\ 1 & k & \mathrm C_k^2 & \mathrm C_k^3 & \cdots & k\\ \end{pmatrix} = (p_{ij})_{n\times n}$$
即
$$a_{ij}=(-1)^{i-j}p_{ij},\qquad p_{ij}=\left\{\begin{aligned}&\mathrm C_i^{j-1},&&i\geq j\\ &0,&&i<j\end{aligned}\right.$$
这里直接给出 $A$ 的逆
$$A^{-1}=\begin{pmatrix} 1\\ 1/2 & 1/2\\ 1/6 & 1/2 & 1/3\\ 0 & 1/4 & 1/2 & 1/4\\ -1/30 & 0 & 1/3 & 1/2 & 1/5\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ * & * & * & * & * & \cdots & 1/k\\ \end{pmatrix}$$
而 $\boldsymbol S=A^{-1}\boldsymbol n$, 即是说根据 $A^{-1}$ 的元素可以得到一系列等幂求和公式
$$\begin{aligned} &S_0&&=&&n\\ &S_1&&=&\frac{1}{2}&n & +\frac{1}{2}&n^2\\ &S_2&&=&\frac{1}{6}&n & +\frac{1}{2}&n^2 & +&\frac{1}{3}n^3\\ &S_3&&=&&0 & +\frac{1}{4}&n^2 & +&\frac{1}{2}n^3 & +&\frac{1}{4}n^4\\ &S_4&&=&-\frac{1}{30}&n & +&0 & +&\frac{1}{3}n^3 & +&\frac{1}{2}n^4 & +&\frac{1}{5}n^5\\ &\cdots\\ &S_{k-1}&&=&*&n & +*&n^2 & +&*n^3 & +&*n^4 & +&*n^5 & +&\cdots & +&\frac{1}{k}n^k\\ \end{aligned}$$

3 对 $A^{-1}$ 的观察

  现将上述求和式降幂排列
$$\begin{aligned} &S_0&&=&&n\\ &S_1&&=&\frac{1}{2}&n^2 & +\frac{1}{2}&n\\ &S_2&&=&\frac{1}{3}&n^3 & +\frac{1}{2}&n^2 & +&\frac{1}{6}n\\ &S_3&&=&\frac{1}{4}&n^4 & +\frac{1}{2}&n^4 & +&\frac{1}{4}n^2 & +&0\\ &S_4&&=&\frac{1}{5}&n^5 & +\frac{1}{2}&n^4 & +&\frac{1}{3}n^3 & +&0 &-\frac{1}{30}&n\\ &\cdots\\ &S_{k-1}&&=&\frac{1}{k}&n^k & +*&n^{k-1} & +*&n^{k-2} & +*&n^{k-3} & +*&n^{k-4} & +&\cdots & +&*n\\ \end{aligned}$$
现抽离出系数, 记作矩阵 $U=(u_{ij})_{n\times n}$. 记 $T=(t_{ij})_{n\times n}:=A^{-1}$, 则有 $u_{ij}=t_{i,i-j+1}$. $U$ 矩阵即
$$U=\begin{pmatrix} 1\\ 1/2 & 1/2\\ 1/3 & 1/2 & 1/6\\ 1/4 & 1/2 & 1/4 & 0\\ 1/5 & 1/2 & 1/3 & 0 & -1/30\\ 1/6 & 1/2 & 5/12 & 0 & -1/12 & 0\\ 1/7 & 1/2 & 1/2 & 0 & -1/6 & 0 & 1/42\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ 1/k & * & * & 0 & * & 0 & * & \cdots & *\\ \end{pmatrix}$$

注意到 $U$ 的各元素可以分解成三数之积
$$U=\begin{pmatrix} 1\cdot 1\cdot 1\\ \frac{1}{2}\cdot 1\cdot 1 & \frac{1}{2}\cdot 2\cdot \frac{1}{2} \\ \frac{1}{3}\cdot 1\cdot 1 & \frac{1}{3}\cdot 3\cdot \frac{1}{2} & \frac{1}{3}\cdot 3 \cdot \frac{1}{6}\\ \frac{1}{4}\cdot 1\cdot 1 & \frac{1}{4}\cdot 4\cdot \frac{1}{2} & \frac{1}{4}\cdot 6 \cdot \frac{1}{6} & \frac{1}{4}\cdot 4 \cdot 0\\ \frac{1}{5}\cdot 1\cdot 1 & \frac{1}{5}\cdot 5\cdot \frac{1}{2} & \frac{1}{5}\cdot 10\cdot \frac{1}{6} & \frac{1}{5}\cdot 10\cdot 0 &\frac{1}{5}\cdot 5 \cdot-\frac{1}{30}\\ \frac{1}{6}\cdot 1\cdot 1 & \frac{1}{6}\cdot 6\cdot \frac{1}{2} & \frac{1}{6}\cdot 15\cdot \frac{1}{6} & \frac{1}{6}\cdot 20\cdot 0 &\frac{1}{6}\cdot 15\cdot-\frac{1}{30} & \frac{1}{6}\cdot 6\cdot 0\\ \frac{1}{7}\cdot 1\cdot 1 & \frac{1}{7}\cdot 7\cdot \frac{1}{2} & \frac{1}{7}\cdot 21\cdot \frac{1}{6} & \frac{1}{7}\cdot 35\cdot 0 &\frac{1}{7}\cdot 35\cdot-\frac{1}{30} & \frac{1}{7}\cdot 21\cdot 0 & \frac{1}{7}\cdot 7\cdot \frac{1}{42}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \frac{1}{k}\cdot 1\cdot 1 & * & * & * & * & * & * & \cdots & *\\ \end{pmatrix}$$
对于 $u_{ij}$, 第一个数是 $1/i$, 第二个数是前述杨辉三角矩阵的元素 $p_{ij}$, 第三个数是仅与列号 $j$ 有关的数. 记 Bernoulli 数
$$B_0=1,\ B_1=\frac{1}{2},\ B_2=\frac{1}{6},\ B_3=0,\ B_4=-\frac{1}{30},\ B_5=0,\ B_6=\frac{1}{42},\ \cdots$$
则 $u_{ij}=\frac{1}{i}\times p_{ij}\times B_{j-1}$. 注意到 $S_{i-1}$ 中 $\ell$ 次项的系数是 $u_{i,i-\ell+1}$. 所以
$$\begin{aligned}S_{k-1}=\sum_{\ell=1}^i u_{k,k-\ell+1}n^\ell&=\sum_{\ell=1}^i \frac{1}{k}p_{k,k-\ell+1}B_{k-\ell}n^\ell\\ &=\frac{1}{k}\left(\sum_{\ell=1}^k \mathrm C_k^{k-\ell}B_{k-\ell}n^\ell\right)\\&=\frac{1}{k}\left(\sum_{\ell=0}^k \mathrm C_k^\ell\mathcal B^{k-\ell}n^\ell-B_k\right)\end{aligned}$$
上述使用了一个形式上的幂记号 $\mathcal B^n:=B_n$. 容易发现上式其实是 Newton 二项式定理的形式, 于是有
$$\sum_{i=1}^n i^{k-1}=\frac{(\mathcal B+n)^k-B_k}{k}$$
例如取 $k=3$ 时有
$$\begin{aligned}\sum i^2&=\frac{B_0n^3+3B_1n^2+3B_2n+B_3-B_3}{3}\\&=\frac{n^3+3n^2/2+n/2}{3}\\&=\frac{1}{3}n^3 +\frac{1}{2}n^2 +\frac{1}{6}n\end{aligned}$$

附录 A 部分 Bernoulli 数

$$\begin{aligned} B_0&=1 & B_1&=\frac{1}{2} & B_2&=\frac{1}{6} & B_4&=-\frac{1}{30}\\ B_6&=\frac{1}{42} & B_8&=-\frac{1}{30} & B_{10}&=\frac{5}{66} & B_{12}&=-\frac{691}{2730}\\ B_{14}&=\frac{7}{6} & B_{16}&=-\frac{3617}{510} & B_{18}&=\frac{43867}{798} & B_{20}&=-\frac{174611}{330} \end{aligned}$$
$$B_{2k+1}=0,\ k=1,2,\cdots$$