在中学阶段我们都学过前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) 式。
伯努利数应用广泛，非常深奥。由于时间所限，本文就写到这里。