关于伯努利数转化自然数幂和公式的证明

虽说这东西没什么实际应用价值但还是写一下好了 我们定义伯努利数$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)$就成立了,这样我们使用归纳法证明了伯努利数转化自然数幂和公式的正确性