\[\sum_{i=1}^ni^k \]
-
递推
令其为\(f(n,k)\)
\[(i+1)^{k+1}-i^{k+1}=C_{k+1}^1i^k+C_{k+1}^2i^{k-1}+…+C_{k+1}^ki+1 \]
相加得
\[(n+1)^{k+1}-1=C_{k+1}^1\sum_{i=0}^ni^k+C_{k+1}^2\sum_{i=0}^ni^{k-1}+…+C_{k+1}^k\sum_{i=0}^ni+n \]
\[f(n,k)=\frac1{k+1}((n+1)^{k+1}-\sum_{i=2}^{k+1}C_{k+1}^if(n,k+1-i)-1) \]
时间复杂度\(O(k^2)\)
-
拉格朗日插值
明显是一个关于n的k+1次多项式，可以做到\(O(k)\)
-
斯特林数（见组合数学）
-
伯努利数
\[f(n,k)=\frac1{k+1}\sum_{i=1}^{k+1}C_{k+1}^iB_{k+1-i}(n+1)^i \]
\(B_0=1\)，对于\(n>0\)有
\[\sum_{i=0}^nC_{n+1}^iB_i=0 \]
-
多项式差分
\(g(n)=n^k\)这一函数的差分表的第0条对角线为\(c_0…c_k\)
\[\sum_{i=0}^nf(i)=\sum_{i=0}^n\sum_{j=0}^kc_jC_i^j \]
\[=\sum_{j=0}^k\sum_{i=0}^nc_jC_i^j \]
\[=\sum_{j=0}^kc_jC_{n+1}^{j+1} \]