自然数幂和
pjykk
·
·
个人记录
4.5 年之前写的，不太严谨。
问题是这样的：求0^k+1^k+2^k+\dots +n^k的通项公式。
我们尝试用数学归纳法解决。
首先，这个因为n可能为0，所以通项公式一定是没有常数项的。继续观察可知，通项公式的次数是k+1。这样，我们设通项公式为f(n)=\sum_{i=1}^{k+1}a_in^i。我们的目标就是要求出这些系数。
但通项公式还要满足：
f(n+1)-f(n)=(n+1)^k
这样才能用数学归纳法。
这个等式可以直接暴力展开：
f(n+1)-f(n)=(n+1)^k
\sum_{i=1}^{k+1}a_i(n+1)^i-\sum_{j=1}^{k+1}a_jn^j=(n+1)^k
\sum_{i=1}^{k+1}a_i[(n+1)^i-n^i]=(n+1)^k
\sum_{i=1}^{k+1}a_i\sum_{j=0}^{i-1}C_i^jn^j=\sum_{x=0}^{k}C_k^xn^x
等式左右两边都是多项式，可以对比系数。
暴力展开：
a_1(C^0_1n^0)+a_2(C^0_2n^0+C^1_2n^1)+\dots +a_{k+1}(C^0_{k+1}n^0+C^1_{k+1}n^1+\dots +C^k_{k+1}n^k)=C^0_kn^0+C^1_kn^1+\dots +C^k_kn^k
化简+对比系数：
\left
\{
\begin{array}{c}
{\sum_{i=1}^{k+1}a_iC^0_i=C^0_k}
\\
\\
{\sum_{i=2}^{k+1}a_iC^1_i=C^1_k}
\\
\\
\dots \dots
\\
\\
{\sum_{i=k+1}^{k+1}a_iC^k_i=C^k_k}
\end{array}
\right.
这个方程我们从后往前迭代解。
方程解得：
\left
\{
\begin{array}{c}
a_{k+1}=\dfrac{1}{k+1}
\\
a_i=\dfrac{C^{i-1}_k-\sum^{k+1}_{j=i+1}a_jC^{i-1}_j}{i}
\end{array}
\right.