定义
递归定义：\(\sum\limits_{i=0}^n\dbinom {n+1}iB_i=[n=0]\)
生成函数定义：\(\sum\limits_{i=0}^{\infty}\dfrac{B_i}{i!}x^i=\dfrac x{e^x-1}\)
等价性证明：
由递归定义式易得：
\[\begin{aligned}
\sum\limits_{i=0}^{n-1}\dbinom ni B_i&=0(n>1)\\sum\limits_{i=0}^{n-1}\dbinom niB_i+B_n&=B_n(n>1)\\sum\limits_{i=0}^{n}\dbinom niB_i&=B_n(n>1)\\sum\limits_{i=0}^{n}\dfrac{n!}{i!(n-i)!}B_i&=\dfrac{B_n}{n!}(n>1)\\end{aligned}\]
构建伯努利数的指数型生成函数 \(B(x)=\sum\limits_{i=0}^{\infty}\dfrac{B_i}{i!}x^i\)
考虑上面推导出的式子，式子左侧为 \(B(x)\) 和 \(\mathbf{EGF}\{[1,1,\cdots]\}\) 的卷积，右侧为 \(B(x)\)
则对于 \(i\in[2,+\infty)\)，有 \([x^i]\left(B(x)e^x\right)=[x^i]B(x)\)
设 \(B(x)e^x=B(x)+mx+n\)，将 \(B_0,B_1\) 直接代入可得 \(m=1,n=0\)
即 \(B(x)e^x=B(x)+x\)l，由此可得生成函数定义：\(B(x)=\dfrac{x}{e^x-1}\)
应用：自然数幂和
伯努利数可以用来求自然数幂和，具体来说：
设 \(S(n,k)=\sum\limits_{i=0}^{n-1}i^k\)
则 \(S(n,k)=\dfrac1{k+1}\sum\limits_{i=0}^k\dbinom{k+1}{i}B_in^{k-i+1}\)
递归定义证明
采用数学归纳法证明
设 \(R(n,k)=\dfrac1{k+1}\sum\limits_{i=0}^k\dbinom{k+1}{i}B_in^{k-i+1}\)，即证明 \(R=S\)
\(R(n,0)=\dbinom{1}{0}B_0n^1=n=S(n,0)\)
问题转化为：已知对于所有的 \(j\in[0,k)\)，\(S(n,j)=R(n,j)\)，求证：\(S(n,k)=R(n,k)\)
先证明一个关于 \(S(n,k)\) 的递归式：
\[\begin{aligned}
S(n,k+1)&=\sum\limits_{i=0}^{n-1}i^{k+1}\S(n,k+1)+n^{k+1}&=\sum\limits_{i=0}^{n-1}(i+1)^{k+1}\S(n,k+1)+n^{k+1}&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{k+1}\dbinom{k+1}{j}i^j\S(n,k+1)+n^{k+1}&=\sum\limits_{j=0}^{k+1}\dbinom{k+1}j\sum\limits_{i=0}^{n-1}i^j\S(n,k+1)+n^{k+1}&=\sum\limits_{j=0}^{k+1}\dbinom{k+1}jS(n,j)\\sum\limits_{j=0}^{k}\dbinom{k+1}jS(n,j)&=n^{k+1}
\end{aligned}\]
对于所有的 \(j\in[0,k)\)，有 \(S(n,j)=R(n,j)\) 成立，所以我们可以将上式中的 \(S(n,j)\) 换掉
\[\begin{aligned}
n^{k+1}&=\sum\limits_{j=0}^{k-1}\dbinom{k+1}jR(n,j)+\dbinom{k+1}kS(n,k)\&=\sum\limits_{j=0}^{k-1}\dbinom{k+1}jR(n,j)+\dbinom{k+1}kS(n,k)+\dbinom{k+1}kR(n,k)-\dbinom{k+1}kR(n,k)\&=\sum\limits_{j=0}^{k}\dbinom{k+1}jR(n,j)+(k+1)(S(n,k)-R(n,k))\\end{aligned}\]
要证 \(S(n,k)=R(n,k)\)，只需证 \(\sum\limits_{j=0}^k\dbinom{k+1}jR(n,j)=n^{k+1}\)
下面会用到一些组合数公式，参考常用组合数公式及证明
将 \(R(n,j)\) 展开：
\[\begin{aligned}
n^{k+1}&=\sum\limits_{j=0}^{k}\dbinom{k+1}j\dfrac{1}{j+1}\sum\limits_{i=0}^j\dbinom{j+1}iB_in^{j-i+1}\&=\sum\limits_{j=0}^{k}\dbinom{k+1}j\dfrac{1}{j+1}\sum\limits_{i=0}^j\dbinom{j+1}{j-i}B_{j-i}n^{i+1}\&=\sum\limits_{j=0}^{k}\dbinom{k+1}j\dfrac{1}{j+1}\sum\limits_{i=0}^j\dbinom{j+1}{i+1}B_{j-i}n^{i+1}\&=\sum\limits_{j=0}^{k}\dbinom{k+1}j\dfrac{1}{j+1}\sum\limits_{i=0}^j\dfrac{j+1}{i+1}\dbinom{j}{i}B_{j-i}n^{i+1}\&=\sum\limits_{j=0}^{k}\dbinom{k+1}j\sum\limits_{i=0}^j\dbinom{j}{i}B_{j-i}\dfrac{n^{i+1}}{i+1}\\end{aligned}\]
交换求和符号并改写组合数：
\[\begin{aligned}
n^{k+1}&=\sum\limits_{i=0}^k\dfrac{n^{i+1}}{i+1}\sum\limits_{j=i}^k\dbinom{k+1}{j}\dbinom{j}{i}B_{j-i}\&=\sum\limits_{i=0}^k\dfrac{n^{i+1}}{i+1}\sum\limits_{j=i}^k\dbinom{k+1}{i}\dbinom{k-i+1}{j-i}B_{j-i}\&=\sum\limits_{i=0}^k\dfrac{n^{i+1}}{i+1}\dbinom{k+1}{i}\sum\limits_{j=0}^{k-i}\dbinom{k-i+1}{j}B_{j}\\end{aligned}\]
是时候将定义式 \(\sum\limits_{i=0}^n\dbinom {n+1}iB_i=[n=0]\) 代入了！
\[\begin{aligned}
n^{k+1}&=\sum\limits_{i=0}^k\dfrac{n^{i+1}}{i+1}\dbinom{k+1}{i}[k-i=0]\&=\dfrac{n^{k+1}}{k+1}\dbinom{k+1}{k}\&=n^{k+1}
\end{aligned}\]
证毕
生成函数定义证明
设 \(A_n(x)\) 为 \(S(n,k)\) 关于 \(k\) 的指数型生成函数，即 \([x^k]A_n(x)=\dfrac{S(n,k)}{k!}\)
\[\begin{aligned}
A_n(x)&=\sum\limits_{i=0}^{\infty}\dfrac{S(n,i)}{i!}x^i\&=\sum\limits_{i=0}^{\infty}\sum\limits_{j=0}^{n-1}\dfrac{j^i}{i!}x^i\&=\sum\limits_{j=0}^{n-1}\sum\limits_{i=0}^{\infty}\dfrac{j^i}{i!}x^i\&=\sum\limits_{j=0}^{n-1}e^{jx}\&=\dfrac{e^{nx}-1}{e^x-1}\&=\dfrac{B(x)(e^{nx}-1)}{x}\\end{aligned}\]
\(\dfrac{e^{nx}-1}{x}=\sum\limits_{i=1}^{\infty}\dfrac{n^ix^i}{i!x}=\sum\limits_{i=0}^{\infty}\dfrac{n^{i+1}}{(i+1)!}x^i\)
考虑 \(A_n(x)\) 的第 \(k\) 项：
\[\begin{aligned}
\dfrac{S(n,k)}{k!}&=[x^k]A_n(x)\&=\sum\limits_{i=0}^k\dfrac{B_i}{i!}\dfrac{n^{k-i+1}}{(k-i+1)!}\&=\dfrac{1}{(k+1)!}\sum\limits_{i=0}^k\dfrac{(k+1)!}{i!(k-i+1)!}B_in^{k-i+1}\&=\dfrac{1}{(k+1)!}\sum\limits_{i=0}^k\dbinom{k+1}{i}B_in^{k-i+1}\\end{aligned}\]
即 \(S(n,k)=\dfrac{1}{k+1}\sum\limits_{i=0}^k\dbinom{k+1}{i}B_in^{k-i+1}\)
证毕
伯努利数
原文：https://www.cnblogs.com/s-z-q/p/13352497.html
