正整数幂和表示为多项式——我的探究 • 动量星空

在中学阶段我们都学过前n个正整数的求和公式：

1 + 2 + \cdots + n = \frac{n(n + 1)}2

有的同学还知道他们的平方和、立方和公式：

1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}

1^3 + 2^3 + \cdots + n^3 = \left(\frac{n(n + 1)}{2}\right)^2

注意到以上式子右边都可化为关于 $n$ 的多项式，且次数比左边待求和的数幂次正好高一，于是猜想：前 $n$ 个正整数的 $m$ 次幂之和可以表示为 $n$ 的 $m+1$ 次多项式。现在我想知道，能否求出这个多项式的各项系数的通项。

设 $S_m(n) = \sum_{x=1}^n x^m = \sum_{i=1}^{m+1} a_i n^i$ ，用含有 $i, m$ 的式子表示 $a_i$ 。

考虑 $S_m(n) - S_m(n-1)$ ：

n^m = \sum_{i=1}^{m+1} a^i \left(n^i - (n-1)^i\right)

用二项式定理展开 $(n-1)^i$ ：

\begin{align} n^m & = \sum_{i=1}^{m+1} a^i \left(n^i - \sum_{j=0}^i \binom{i}{j} n^j (-1)^{i-j}\right) \\ & = \sum_{i=1}^{m+1} a^i \left(- \sum_{j=1}^i \binom{i}{j} n^j (-1)^{i-j}\right) \end{align}

有的同学还知道他们的平方和、立方和公式：交换求和顺序，则

n^m = \sum_{j=0}^{m} \sum_{i=j+1}^{m+1} a^i \binom{i}{j} (-1)^{i-j+1} n^j

比较两边 $n^j$ 的系数，可得：

对于 $j=m$ ，

a_{m+1} = \frac 1 {m+1}

对于 $0 \le j < m$ ，

\sum_{i=j+1}^{m+1} a_i \binom {i}{j} (-1)^{i-j+1} = 0

则

(j+1)a_{j+1} = \sum_{i=j+2}^{m+1} a_i \binom {i}{j} (-1)^{i-j}

这就得到了 $a_i$ 的递推公式。可以依次算出：

a_m = \frac 1 2, a_{m-1} = \frac m {12}, a_{m-2} = 0,

a_{m-3} = -\frac {m(m-1)(m-2)} {720}, \cdots

发现 $a_{m-3}$ 中的一段 $m$ 的下降幂，于是猜想 $a_j$ 可以表示为 $b_{m+1-j} \frac {m!} {j!}, \quad \left(b_{m+1-j} \in \mathbb R\right)$

于是 $b_k$ 有如下递推关系和前几项：

\begin{equation} b_k = \sum_{i=0}^{k-1} b_i \\frac {(-1)^{k-i+1}}{(k-i+1)!} \end{equation}

b_0 = 1, b_1 = \frac 1 2, b_2 = \frac 1 {12},

b_3 = 0, b_4 = -\frac 1 {720}, b_5 = 0,

b_6 = \frac 1 {6 \cdot 7!}, \cdots

到了这里， $b_k$ 就找不到什么规律了。于是这个问题被我搁置了，直到最近才被我从笔记本里翻出来看到，重新研究。

虽然…但是系数有了递推公式，便可以解决一些问题，如在多项式时间内计算正整数幂和。

上网搜索，发现我要求的系数 $a_i$ 跟伯努利数很有关系。事实上，如果令 $b_j = \frac {(-1)^j\beta_i}{j!}$ ，代入 (1) 就得到

\frac {\beta_k}{k!} = - \sum_{i=0}^{k-1} \frac {\beta_i}{i!(k-i+1)!}

(k+1)\beta_k = - \sum_{i=0}^{k-1} \frac {\beta_i(k+1)!}{i!(k-i+1)!}

\begin{equation} \beta_k = - \frac 1{k+1} \sum_{i=0}^{k-1} \beta_i \binom{k+1}{i} \end{equation}

这就是伯努利数的递推公式， $\beta_i$ 就是伯努利数。伯努利数的前几项是：

1, -\frac 1 2, \frac 1 6, 0, -\frac 1 {30}, 0, \frac 1 {42}, \cdots

于是我们要求的 $a_i$ 可以暂时写成 $\frac {(-1)^{m+1-i} \beta_{m+1-i} m!}{(m+1-i)! i!} = \frac {(-1)^{m+1-i}}{m+1} \beta_{m+1-i} \binom{m+1}{i}$

下面来从伯努利数的定义推导以下它的递推公式。

伯努利数的生成函数定义是：

\frac x {e^x - 1} = \sum_{n=0}^\infty \beta_n \frac {x^n} {n!}

把 $e^x -1$ 乘过去，并把 $e^x$ 泰勒展开：

x = \sum_{n=0}^\infty \beta_n \frac {x^n} {n!} \sum_{n=1}^\infty \frac {x^n}{n!}

再把 x 除过去：

1 = \left(\sum_{n=0}^\infty \beta_n \frac {x^n} {n!}\right) \cdot \left(\sum_{n=0}^\infty \frac {x^n}{(n+1)!}\right)

通过对应右边展开式（柯西乘积）的 $x^n$ 系数，知

对于常数项， $\beta_0 = 1$

对于 $x^n$ 项， $\sum_{i=0}^n \frac {\beta_i}{i! (n-i+1)!} = 0$

单独取出 $\beta_n$ ，稍作调整就得到 (2) 式。

伯努利数应用广泛，非常深奥。由于时间所限，本文就写到这里。