有个Oier小学妹问了我一个Σi^k，i<=1e8 ,k<=1e6的问题，我认为这个用伯努利数列可能可以解决他的问题，所以整理了以下文章，给学弟学习学习~~~本人水平有限，也只能帮到这里了吧QAQ~~~

下面进入正文：

计算∑{i=1,n}i^k 的值需要引入伯努利数列的概念

定义将(B-1)^k展开，然后将B^k写成数列的第k项，即B(k)

当k>=2时，令(B-1)^k展开后的形式（将B^k写成B(k)）与B(k)相等

（便于记忆相当于，令(B-1)^k=B^k，然后将B^k写成B(k)求出各个项的值）

即可得出伯努利数列（即伯努利数）

例如

计算B(1)

令(B-1)^2=B^2

B^2-2B+1=B^2

将B^k写成数列的第k项，即B(k)

有B(2)-2B(1)+1=B(2)

则B(1)=0.5

同理，若计算B(2)

令(B-1)^3=B^3

有

B^3-3B^2+3B-1=B^3

将B^k写成数列的第k项

有

B(3)-3B(2)+3B(1)-1=B(3)

B(2)=[3B(1)-1]/3

即

B(2)=1/6

由此可算出数列的任意一项

定义B(0)=1

由上面所述：

(x+B)^(k+1)

=∑{i=0, k+1}C{i,k+1}B^i*x^(k+1-i)

=x^(k+1)+C{1,k+1}Bx^k+∑{i=2,k+1}C{i,k+1}*B^i*x^(k+1-i)

=x^(k+1)+0.5C{1,k+1}x^k+∑{i=2,k+1}C{i,k+1}*B^i*x^(k+1-i)

又

(x+B-1)^(k+1)

=∑{i=0, k+1}C{i,k+1}(B-1)^i*x^(k+1-i)

=x^(k+1)+C{1,k+1}(B-1)x^k+∑{i=2,k+1}C{i,k+1}*(B-1)^i*x^(k+1-i)

=x^(k+1)-0.5C{1,k+1}x^k+∑{i=2,k+1}C{i,k+1}*(B-1)^i*x^(k+1-i)

因为B(k)是伯努利数列

有

(B-1)^i=B^i

即

(x+B-1)^(k+1)

=x^(k+1)-0.5C{1,k+1}x^k+∑{i=2,k+1}C{i,k+1}*B^i*x^(k+1-i)

所以

(x+B)^(k+1)-(x+B-1)^(k+1)=(k+1)x^k

令x=1，2，3，…，i，…，n

有

(1+B)^(k+1)-B^(k+1)=(k+1)

(2+B)^(k+1)-(1+B)^(k+1)=(k+1)*2^k

(3+B)^(k+1)-(2+B)^(k+1)=(k+1)*3^k

……

(i+B)^(k+1)-(i-1+B)^(k+1)=(k+1)*i^k

……

(n+B)^(k+1)-(n-1+B)^(k+1)=(k+1)*n^k

由上式求和，得：

(n+B)^(k+1)-B^(k+1)=(k+1)∑{i=1,n}i^k

即

∑{i=1,n}i^k=[(n+B)^(k+1)-B^(k+1)]/(k+1)

注意：

这里的(n+B)^(k+1)并不代表(n+B)的k+1次幂

而是指的展开后将B^k写成伯努利数列的第k项

就像前面说的一样。想要严密的算法，就是欧拉

的算法，涉及到无穷级数，比较麻烦但非常严密。

本文所用的符号：

数列求和a(1)+a(2)+a(3)+…+a(n)表示为

∑{i=1,n}a(n)

从n个数中选出m个的组合数为

C{m,n}

以下是用Word整理的文本，我也不知道为啥有时候公式贴上来是错误的，所以怕看不清什么的，截个图存一下，也方便自己查询学习~

下面的图片是数学家欧拉考虑到无穷级数的比较严密的算法：