关于伯努利数转化自然数幂和公式的证明
shadowice1984
·
·
个人记录
虽说这东西没什么实际应用价值但还是写一下好了
我们定义伯努利数B(n)是满足如下递归式的数列
\sum_{i=0}^{m}{m+1 \choose i}B(i)=[m==0]
我们定义自然数幂和函数S(n,k)表示
S(n,k)=\sum_{i=0}^{n-1}i^k
那么我们希望证明的是\hat{S}(n,k)=S(n,k)其中\hat{S}(n,k)等于这个式子
\hat{S}(n,k)=\frac{1}{k+1}\sum_{i=0}^{k}{k+1 \choose i}B(i)n^{k+1-i}
怎么证明这个鬼畜的东西呢？
指数生成函数直接上啊
但是事实上运用二项式系数的恒等变换，我们可以的得到一个非常有趣的归纳做法(这个做法是《具体数学》上给出的)
我们使用强归纳法(也叫完全归纳法)来证明这个命题，具体点来讲，假如对于所有的0 \leq j <k,S(n,j)=\hat{S}(n,j)这个命题全部成立，我们希望证明S(n,k)=\hat{S}(n,k)是成立的
让我们先来证明一个关于S(n,k)的递归式
S(n,k+1)=\sum_{i=0}^{n-1}i^{k+1}
S(n,k+1)+n^{k+1}=\sum_{i=0}^{n-1}(i+1)^{k+1}
使用一个简单的二项式定理可以得到
S(n,k+1)+n^{k+1}=\sum_{i=0}^{n-1}\sum_{j=0}^{k+1}{k+1 \choose j}i^j
然后我们交换一下求和号就可以得到这个式子
S(n,k+1)+n^{k+1}=\sum_{j=0}^{k+1}{k+1 \choose j}\sum_{i=0}^{n-1}i^{j}
S(n,k+1)+n^{k+1}=\sum_{j=0}^{k+1}{k+1 \choose j}S(n,j)
考虑到{k+1 \choose k+1}=1
所以我们在等式两边同时减去一个{k+1 \choose k+1}S(n,k+1)就得到了这个递归式
\sum_{j=0}^{k}{k+1 \choose j}S(n,j)=n^{k+1}
好了这个递归式有什么用呢？
根据强归纳假设,对于0 \leq j <k来讲S(n,j)=\hat{S}(n,j)都是成立的，但是我们的式子里还有一个S(n,k)这十分的不优美，因此我们将式子里减去一个\hat{S}(n,k)然后加上一个\hat{S}(n,k)
我们就可以得到这个式子:
n^{k+1}=\sum_{j=0}^{k-1}{k+1 \choose j}\hat{S}(n,j)+{k+1 \choose k}S(n,k)+{k+1 \choose k}\hat{S}(n,k)-{k+1 \choose k}\hat{S}(n,k)
稍微整理一下就是
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\hat{S}(n,j)+(k+1)(S(n,k)-\hat{S}(n,k))
假如我们可以证明这个式子是成立的
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\hat{S}(n,j)
那么我们就会发现后边加上的东西必然等于0，我们也就可以证明S(n,k)=\hat{S}(n,k)了，因此让我们把精力集中在上面式子的化简上
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\hat{S}(n,j)
让我们先将\hat{S}(n,j)展开
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\frac{1}{j+1}\sum_{i=0}^{j}{j+1 \choose i}B(i)n^{j+1-i}
然后接下来把第二个\Sigma倒着求一遍和
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\frac{1}{j+1}\sum_{i=0}^{j}{j+1 \choose j-i}B(j-i)n^{i+1}
接下我们运用对称法则把第二个组合数给反过来
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\frac{1}{j+1}\sum_{i=0}^{j}{j+1 \choose i+1}B(j-i)n^{i+1}
我们发现这个组合数里面有两个+1这令我们十分的不爽，所以我们用吸收恒等式把这两个+1拆出来
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\frac{1}{j+1}\sum_{i=0}^{j}\frac{j+1}{i+1}{j \choose i}B(j-i)n^{i+1}
n^{k+1}=\sum_{j=0}^{k}{k+1 \choose j}\sum_{i=0}^{j}{j \choose i}B(j-i)\frac{n^{i+1}}{i+1}
好啦接下来是大家喜闻乐见的交换求和号的环节啦，让我们把第一个求和号和第二个求和号交换过来
限制条件是0 \leq i \leq j \leq k所以我们交换求和号之后还是要按照这个限制求和
n^{k+1}=\sum_{i=0}^{k}\frac{n^{i+1}}{i+1}\sum_{j=i}^{k}{k+1 \choose j}{j \choose i}B(j-i)
好了我们来观察一下{k+1 \choose j}{j \choose i}这个式子的组合意义，从k+1个数字中选择j个数字，再从j个数字当中选择i个数字，这个行为等价于先从k+1个数字中钦定i个数字，接下来从剩余的k+1-i个数字中钦定j-i个数字，所以我们证明了这个式子
{k+1 \choose j}{j \choose i}={k+1 \choose i}{k+1-i \choose j-i}
好啦这样的话我们的式子就变成了
n^{k+1}=\sum_{i=0}^{k}\frac{n^{i+1}}{i+1}\sum_{j=i}^{k}{k+1 \choose i}{k+1-i \choose j-i}B(j-i)
n^{k+1}=\sum_{i=0}^{k}\frac{n^{i+1}}{i+1}{k+1 \choose i}\sum_{j=i}^{k}{k+1-i \choose j-i}B(j-i)
我们稍微变换一下j的意义，用j'=j-i来代换j那么之前式子中的j全部用j'+i来替换
n^{k+1}=\sum_{i=0}^{k}\frac{n^{i+1}}{i+1}{k+1 \choose i}\sum_{j=0}^{k-i}{k+1-i \choose j}B(j)
不如想一下伯努利数的定义是什么？
\sum_{i=0}^{m}{m+1 \choose i}B(i)=[m==0]
把这个式子代入进去我们会发现世界瞬间安静了
n^{k+1}=\sum_{i=0}^{k}\frac{n^{i+1}}{i+1}{k+1 \choose i}[i==k]
n^{k+1}=\frac{n^{k+1}}{k+1}{k+1 \choose k}=n^{k+1}
所以我们就证明了上面的式子的确是成立的，这样的话此时S(n,k)=\hat{S}(n,k)就成立了,这样我们使用归纳法证明了伯努利数转化自然数幂和公式的正确性