伯努利数列

伯努利数是18世纪瑞士数学家雅各布·伯努利引入的一个数。在数学上，伯努利数是一个有理数数列，在许多领域都有很大的应用。一般地，n>=1时，有B(2n+1)=0n>=2时，有公式B(n)=∑[C(k，n)*B(k)](k:0->n)可用来逐一计算伯努利数。伯努利数在数论中很有用。伯努利数还可用于费马大定理的论证中。

伯努利数，第i项记为Bi，是专门解决自然数幂求和而构造的一个数列

我们先记Sk(n)=∑i=0n−1ik

那么，不知道为什么

Sk(n)=1k+1∑i=0k(k+1i)Bink+1−i

我们发现n=0是个特例

得到

∑i=0k(k+1i)Bi=[k=0]

所以我们有

Bk=−1k+1∑i=0k−1(k+1i)Bi

就可以O(k2)递推辣

然后就可以O(k)计算Sk(n)辣