伯努利数

伯努利数 $B_{n}$ 是一个与数论有密切关联的有理数序列。前几项被发现的伯努利数分别为：

$B_{0} = 1, B_{1} = - \frac{1}{2}, B_{2} = \frac{1}{6}, B_{3} = 0, B_{4} = - \frac{1}{30}, \dots$

等幂求和

伯努利数是由雅各布·伯努利的名字命名的，他在研究 $m$ 次幂和的公式时发现了奇妙的关系。我们记

S_{m} (n) = \sum_{k = 0}^{n - 1} k^{m} = 0^{m} + 1^{m} + \dots + (n - 1)^{m}

伯努利观察了如下一列公式，勾画出一种模式：

\begin{aligned} S_{0} (n) & = n \\ S_{1} (n) & = \frac{1}{2} n^{2} - \frac{1}{2} n \\ S_{2} (n) & = \frac{1}{3} n^{3} - \frac{1}{2} n^{2} + \frac{1}{6} n \\ S_{3} (n) & = \frac{1}{4} n^{4} - \frac{1}{2} n^{3} + \frac{1}{4} n^{2} \\ S_{4} (n) & = \frac{1}{5} n^{5} - \frac{1}{2} n^{4} + \frac{1}{3} n^{3} - \frac{1}{30} n \end{aligned}

可以发现，在 $S_{m} (n)$ 中 $n^{m + 1}$ 的系数总是 $\frac{1}{m + 1}$ ， $n^{m}$ 的系数总是 $- \frac{1}{2}$ ， $n^{m - 1}$ 的系数总是 $\frac{m}{12}$ ， $n^{m - 3}$ 的系数是 $- \frac{m (m - 1) (m - 2)}{720}$ ， $n^{m - 4}$ 的系数总是零等。

而 $n^{m - k}$ 的系数总是某个常数乘以 $m^{\underset{―}{k}}$ ， $m^{\underset{―}{k}}$ 表示下降阶乘幂，即 $\frac{m!}{(m - k)!}$ 。

递推公式

\begin{aligned} S_{m} (n) & = \frac{1}{m + 1} (B_{0} n^{m + 1} + (\binom{m + 1}{1}) B_{1} n^{m} + \dots + (\binom{m + 1}{m}) B_{m} n) \\ = \frac{1}{m + 1} \sum_{k = 0}^{m} (\binom{m + 1}{k}) B_{k} n^{m + 1 - k} \end{aligned}

伯努利数由隐含的递推关系定义：

\begin{aligned} \sum_{j = 0}^{m} (\binom{m + 1}{j}) B_{j} & = 0, (m > 0) \\ B_{0} & = 1 \end{aligned}

例如， $(\binom{2}{0}) B_{0} + (\binom{2}{1}) B_{1} = 0$ ，前几个值显然是

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$\dots$
$B_{n}$	$1$	$- \frac{1}{2}$	$\frac{1}{6}$	$0$	$- \frac{1}{30}$	$0$	$\frac{1}{42}$	$0$	$- \frac{1}{30}$	$\dots$

证明

利用归纳法证明

这个证明方法来自 Concrete Mathematics 6.5 BERNOULLI NUMBER。

运用二项式系数的恒等变换和归纳法进行证明：

\begin{aligned} S_{m + 1} (n) + n^{m + 1} & = \sum_{k = 0}^{n - 1} (k + 1)^{m + 1} \\ = \sum_{k = 0}^{n - 1} \sum_{j = 0}^{m + 1} (\binom{m + 1}{j}) k^{j} \\ = \sum_{j = 0}^{m + 1} (\binom{m + 1}{j}) S_{j} (n) \end{aligned}

令 ${\hat{S}}_{m} (n) = \frac{1}{m + 1} \sum_{k = 0}^{m} (\binom{m + 1}{k}) B_{k} n^{m + 1 - k}$ ，我们希望证明 $S_{m} (n) = {\hat{S}}_{m} (n)$ ，假设对 $j \in [0, m)$ ，有 $S_{j} (n) = {\hat{S}}_{j} (n)$ 。

将原式中两边都减去 $S_{m + 1} (n)$ 后可以得到：

\begin{aligned} S_{m + 1} (n) + n^{m + 1} & = \sum_{j = 0}^{m + 1} (\binom{m + 1}{j}) S_{j} (n) \\ n^{m + 1} & = \sum_{j = 0}^{m} (\binom{m + 1}{j}) S_{j} (n) \\ = \sum_{j = 0}^{m - 1} (\binom{m + 1}{j}) {\hat{S}}_{j} (n) + (\binom{m + 1}{m}) S_{m} (n) \end{aligned}

尝试在式子的右边加上 $(\binom{m + 1}{m}) {\hat{S}}_{m} (n) - (\binom{m + 1}{m}) {\hat{S}}_{m} (n)$ 再进行化简，可以得到：

n^{m + 1} = \sum_{j = 0}^{m} (\binom{m + 1}{j}) {\hat{S}}_{j} (n) + (m + 1) (S_{m} (n) - {\hat{S}}_{m} (n))

不妨设 $Δ = S_{m} (n) - {\hat{S}}_{m} (n)$ ，并且将 ${\hat{S}}_{j} (n)$ 展开，那么有

\begin{aligned} n^{m + 1} & = \sum_{j = 0}^{m} (\binom{m + 1}{j}) {\hat{S}}_{j} (n) + (m + 1) Δ \\ = \sum_{j = 0}^{m} (\binom{m + 1}{j}) \frac{1}{j + 1} \sum_{k = 0}^{j} (\binom{j + 1}{k}) B_{k} n^{j + 1 - k} + (m + 1) Δ \end{aligned}

将第二个 $\sum$ 中的求和顺序改为逆向，再将组合数的写法恒等变换可以得到：

\begin{aligned} n^{m + 1} & = \sum_{j = 0}^{m} (\binom{m + 1}{j}) \frac{1}{j + 1} \sum_{k = 0}^{j} (\binom{j + 1}{j - k}) B_{j - k} n^{k + 1} + (m + 1) Δ \\ = \sum_{j = 0}^{m} (\binom{m + 1}{j}) \frac{1}{j + 1} \sum_{k = 0}^{j} (\binom{j + 1}{k + 1}) B_{j - k} n^{k + 1} + (m + 1) Δ \\ = \sum_{j = 0}^{m} (\binom{m + 1}{j}) \frac{1}{j + 1} \sum_{k = 0}^{j} \frac{j + 1}{k + 1} (\binom{j}{k}) B_{j - k} n^{k + 1} + (m + 1) Δ \\ = \sum_{j = 0}^{m} (\binom{m + 1}{j}) \sum_{k = 0}^{j} (\binom{j}{k}) \frac{B_{j - k}}{k + 1} n^{k + 1} + (m + 1) Δ \end{aligned}

对两个求和符号进行交换，可以得到：

n^{m + 1} = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} \sum_{j = k}^{m} (\binom{m + 1}{j}) (\binom{j}{k}) B_{j - k} + (m + 1) Δ

对 $(\binom{m + 1}{j}) (\binom{j}{k})$ 进行恒等变换：

(\binom{m + 1}{j}) (\binom{j}{k}) ＝ (\binom{m + 1}{k}) (\binom{m - k + 1}{j - k})

那么式子就变成了：

\begin{aligned} n^{m + 1} & = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} \sum_{j = k}^{m} (\binom{m + 1}{k}) (\binom{m - k + 1}{j - k}) B_{j - k} + (m + 1) Δ \\ = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} (\binom{m + 1}{k}) \sum_{j = k}^{m} (\binom{m - k + 1}{j - k}) B_{j - k} + (m + 1) Δ \end{aligned}

将所有的 $j - k$ 用 $j$ 代替，那么就可以得到：

n^{m + 1} = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} (\binom{m + 1}{k}) \sum_{j = 0}^{m - k} (\binom{m - k + 1}{j}) B_{j} + (m + 1) Δ

考虑我们前面提到过的递归关系

\begin{aligned} \sum_{j = 0}^{m} (\binom{m + 1}{j}) B_{j} & = 0, (m > 0) \\ B_{0} & = 1 \\ \sum_{j = 0}^{m} (\binom{m + 1}{j}) B_{j} & = [m = 0] \end{aligned}

代入后可以得到：

\begin{aligned} n^{m + 1} & = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} (\binom{m + 1}{k}) [m - k = 0] + (m + 1) Δ \\ = \sum_{k = 0}^{m} \frac{n^{k + 1}}{k + 1} (\binom{m + 1}{k}) + (m + 1) Δ \\ = \frac{n^{m + 1}}{m + 1} (\binom{m + 1}{m}) + (m + 1) Δ \\ = n^{m + 1} + (m + 1) Δ \end{aligned}

于是 $Δ = 0$ ，且有 $S_{m} (n) = {\hat{S}}_{m} (n)$ 。

利用指数生成函数证明

对递推式 $\sum_{j = 0}^{m} (\binom{m + 1}{j}) B_{j} = [m = 0]$

两边都加上 $B_{m + 1}$ ，即得到：

\begin{aligned} \sum_{j = 0}^{m + 1} (\binom{m + 1}{j}) B_{j} & = [m = 0] + B_{m + 1} \\ \sum_{j = 0}^{m} (\binom{m}{j}) B_{j} & = [m = 1] + B_{m} \\ \sum_{j = 0}^{m} \frac{B_{j}}{j!} \cdot \frac{1}{(m - j)!} & = [m = 1] + \frac{B_{m}}{m!} \end{aligned}

设 $B (z) = \sum_{i \geq 0} \frac{B_{i}}{i!} z^{i}$ ，注意到左边为卷积形式，故：

\begin{aligned} B (z) e^{z} & = z + B (z) \\ B (z) & = \frac{z}{e^{z} - 1} \end{aligned}

设 $F_{n} (z) = \sum_{m \geq 0} \frac{S_{m} (n)}{m!} z^{m}$ ，则：

\begin{aligned} F_{n} (z) & = \sum_{m \geq 0} \frac{S_{m} (n)}{m!} z^{m} \\ = \sum_{m \geq 0} \sum_{i = 0}^{n - 1} \frac{i^{m} z^{m}}{m!} \end{aligned}

调换求和顺序：

\begin{aligned} F_{n} (z) & = \sum_{i = 0}^{n - 1} \sum_{m \geq 0} \frac{i^{m} z^{m}}{m!} \\ = \sum_{i = 0}^{n - 1} e^{i z} \\ = \frac{e^{n z} - 1}{e^{z} - 1} \\ = \frac{z}{e^{z} - 1} \cdot \frac{e^{n z} - 1}{z} \end{aligned}

代入 $B (z) = \frac{z}{e^{z} - 1}$ ：

\begin{aligned} F_{n} (z) & = B (z) \cdot \frac{e^{n z} - 1}{z} \\ = (\sum_{i \geq 0} \frac{B_{i}}{i!}) (\sum_{i \geq 1} \frac{n^{i} z^{i - 1}}{i!}) \\ = (\sum_{i \geq 0} \frac{B_{i}}{i!}) (\sum_{i \geq 0} \frac{n^{i + 1} z^{i}}{(i + 1)!}) \end{aligned}

由于 $F_{n} (z) = \sum_{m \geq 0} \frac{S_{m} (n)}{m!} z^{m}$ ，即 $S_{m} (n) = m! [z^{m}] F_{n} (z)$ ：

\begin{aligned} S \times m (n) & = m! [z^{m}] F_{n} (z) \\ = m! \sum_{i = 0}^{m} \frac{B \times i}{i!} \cdot \frac{n^{m - i + 1}}{(m - i + 1)!} \\ = \frac{1}{m + 1} \sum_{i = 0}^{m} (\binom{m + 1}{i}) B_{i} n^{m - i + 1} \end{aligned}

故得证。

参考实现

using ll = long long;
constexpr int MAXN = 10000;
constexpr int mod = 1e9 + 7;
ll B[MAXN];        // 伯努利数
ll C[MAXN][MAXN];  // 组合数
ll inv[MAXN];      // 逆元（计算伯努利数）

void init() {
  // 预处理组合数
  for (int i = 0; i < MAXN; i++) {
    C[i][0] = C[i][i] = 1;
    for (int k = 1; k < i; k++) {
      C[i][k] = (C[i - 1][k] % mod + C[i - 1][k - 1] % mod) % mod;
    }
  }
  // 预处理逆元
  inv[1] = 1;
  for (int i = 2; i < MAXN; i++) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  }
  // 预处理伯努利数
  B[0] = 1;
  for (int i = 1; i < MAXN; i++) {
    ll ans = 0;
    if (i == MAXN - 1) break;
    for (int k = 0; k < i; k++) {
      ans += C[i + 1][k] * B[k];
      ans %= mod;
    }
    ans = (ans * (-inv[i + 1]) % mod + mod) % mod;
    B[i] = ans;
  }
}

本页面最近更新：2025/5/3 19:43:25，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Enter-tainer, ShaoChenHeng, Tiphereth-A, Aquistcev, c-forrest, Great-designer, Ir1d, kenlig, ksyx, OkazakiYumemi, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用