关于伯努利数

问题引入. 给定 \(n\), \(k\)，我们想计算

\[S(n,k)= \sum_{i=0}^{n-1} i^k. \]

进一步地，我们已经知道 \(S(n,k)\) 是一个关于 \(n\) 的 \(k+1\) 次多项式，现在我们想求出它的系数。

推导. 对 \(i^k\) 的求和比较困难，但是另一方面，我们回忆对等比数列做求和非常容易。注意到形式幂级数 \(e^{iz}\) 中 \(z^k\) 一项的系数恰好是 \(\frac{i^k}{k!}\)，这启发我们做变换：

\[S(n,k) = \sum_{i=0}^{n-1} [z^k/k!] e^{iz} = [z^k/k!] \frac{e^{nz}-1}{e^z-1}. \]

其中 \([z^k/k!] P(z)\) 是一个作用在形式幂级数上的算符。它的定义为：假设 \(P(z) = \sum_{j} \frac{c_j}{j!} z^j\)，那么 \([z^k/k!] P(z) = c_k\). 此时，我们将 \(\frac{1-e^{nz}}{1-e^z}\) 看成一个关于 \(z\) 的形式幂级数，做一个多项式求逆之后可以得到它的第 \(k\) 项的系数，这样就能在 \(\Theta(k\log k)\) 的时间内得出上述问题的答案了。

更进一步，我们来仔细研究一下 \(\frac{e^{nz}-1}{e^z-1}\) 这个式子。它的分子是

\[e^{nz} - 1= \sum_{i=1}^{\infty} \frac{n^i}{i!}\cdot z^i, \]

而分母是

\[e^z-1 = \sum_{i=1}^{\infty} \frac{z^i}{i!}. \]

注意到分母的常数项为 0，它本身并没有逆元。为了能够求逆，我们在分子添上一个 \(z\)，考虑 \(\frac{z}{e^z-1}\)。我们假设求出了它的逆元如下：

\[\frac{z}{e^z-1} = \sum_{i=0}^{\infty} \frac{B_i}{i!}\cdot z^i. \]

那么我们就有

\[[z^k/k!]\frac{e^{nz}-1}{e^z-1}=[z^k/k!] \left(\frac{e^{nz}-1}{z}\cdot \frac{z}{e^z-1} \right) = k!\cdot \sum_{i+j=k} \frac{n^{i+1}\cdot B_j}{(i+1)! j!}. \]

我们发现，等式的右边是一个关于 \(n\) 的 \(k+1\) 次多项式，这正是我们想得到的东西。

在以上推导里扮演了重要作用的数列 \((B_i)\) 即为伯努利数。

定义（伯努利数）. 我们通过生成函数定义（有符号）伯努利数如下。定义伯努利数 \((B_i)_{i=0}^{\infty}\) 为一数列，满足下述等式:

\[\frac{z}{e^z-1} = \sum_{i=0}^\infty \frac{B_i}{i!}\cdot z^i. \]

不难发现这样的数列存在且唯一。

注：人们也定义了无符号伯努利数 \(B_i^+\) 为生成函数 \(\frac{z}{1-e^{-z}}\) 的系数，我们发现 \(B_i^+=|B_i|\)。

同时，根据上面的推导，我们发现伯努利数可以用来给出关于 \(n\) 的 \(k\) 次多项式 \(S(n,k)=\sum_{i=0}^{n-1} i^k\) 的系数：

定理. 我们有下式成立：

\[S(n,k):= \sum_{i=0}^{n-1} i^k = \frac{1}{k+1}\cdot \sum_{j=0}^{k}\binom{k+1}{j}\cdot B_j \cdot n^{k+1-j}. \]

伯努利数也可以用以下方法递归定义：

\[B_m = [m=0] - \sum_{k=0}^{m-1}\binom{m}{k}\frac{B_k}{m-k+1}. \]

证明也很简单，考虑等式 \(\left( \sum_{i=0}^{\infty}\limits \frac{B_i}{i!} z^i \right)\left( \frac{e^z-1}{z} \right) = 1\)，对两边作用算子 \([z^m/m!]\) （也即考虑 \(m\) 次项系数）即可。