伯努利数

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

等幂求和

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

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

可以发现,在 的系数总是 的系数总是 的系数总是 的系数是 的系数总是零等。

的系数总是某个常数乘以 表示下降阶乘幂,即

递推公式

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

例如,,前几个值显然是

证明

利用归纳法证明

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

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

,我们希望证明 ,假设对 ,有

将原式中两边都减去 后可以得到:

尝试在式子的右边加上 再进行化简,可以得到:

不妨设 ,并且将 展开,那么有

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

对两个求和符号进行交换,可以得到:

进行恒等变换:

那么式子就变成了:

将所有的 代替,那么就可以得到:

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

代入后可以得到:

于是 ,且有

利用指数生成函数证明

对递推式

两边都加上 ,即得到:

,注意到左边为卷积形式,故:

,则:

调换求和顺序:

代入

由于 ,即

故得证。

参考实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef long long ll;
const int maxn = 10000;
const 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;
  }
}