自然数幂求和公式.md

自然数幂求和公式

（$\text{C}^m_n$ 代表从 $n$ 个不同物品里面选 $m$ 个，有多少种选法）

（$\sum\limits_{i=0}^n\text{f}(i)$ 表示从 $0$ 到 $n$ 对 $\text{f}(i)$ 求和）

（约定 $\text{C}^0_n=1$）

引理：n 次方差公式 $$(m+1)^{k+1}-m^{k+1}=\sum_{i=0}^{k}\text{C}^i_{k+1}m^i$$

证：

$$\sum^n_{m=1}(m+1)^{k+1}-m^{k+1}=(n+1)^{k+1}-1^{k+1}\=\sum_{i=0}^k\text{C}^i_{k+1}\left(\sum^n_{m=1}m^i\right)$$

$$=\text{C}^k_{k+1}\left(\sum^n_{m=1}m^k\right)+\sum^{k-1}{i=1}\text{C}^i{k+1}\left(\sum^n_{m=1}m^i\right)$$

因此有

$$\sum^n_{m=1}m^k=\dfrac{1}{\text{C}^k_{k+1}}\left[(n+1)^{k+1}-1-\sum^{k-1}{i=0}\text{C}^i{k+1}\left(\sum^n_{m=1}m^i\right)\right]$$