自然数幂和

自然数幂和问题,是给定 $n, k$ ,求
$$ f_k(n)=\sum_{i=1}^{n}i^k $$
之前在伯努利数备忘录里面写了一点自然数幂和
后来又看到几个大爷在博客里面写了自然数幂和,所以又开一篇文章来引用一下其他的方法,我都只是简要提一下思路,具体方法在链接里

Miskcoo 的方法

以下思路与图片来自miskcoo 的博客
感觉思路新奇,明明看上去很简单,但是我怎么就想不到
首先考虑 $S_n=\sum_{i=1}^{n}i^2$ 应该怎样求解
1.png

发现是折线围成面积,也就是曲线围成面积减去中间的面积
由于曲线的函数比较显然,所以可以借助微积分求出为
$$ \int_1^{n+1} x^2 dx = \left .\frac{x^3}{3}\right | _ 1^{n+1} = \frac{(n+1)^3}{3} – \frac{1}{3} $$
然后枚举每一段水平区域,减去差值
$$ S_n = \int_1^{n+1} x^2 dx – \sum_{i=1}^n \left( \int_i^{i+1} x^2 dx – i^2 \right) $$
同样的,可以计算 $f_k(n)$
$$
\begin{eqnarray}
f _ k(n) &=& \int _ 1^{n+1} x^k dx – \sum _ {i=1}^n \left( \int _ i^{i+1} x^k dx – i^k \right) \\
&=& \frac{(n+1)^{k+1} – 1}{k+1} – \sum _ {i=1}^n \frac{(i+1)^{k+1}-i^{k+1}-(k+1)i^k}{k+1} \\
&=& \frac{(n+1)^{k+1} – 1}{k+1} – \frac{1}{k+1} \sum _ {i=1}^n \left((i+1)^{k+1}-i^{k+1}-(k+1)i^k\right) \\
&=& \frac{(n+1)^{k+1} – 1}{k+1} – \frac{1}{k+1} \sum _ {i=1}^n \sum _ {j=0}^{k-1} {{k+1} \choose j} i^j \\
&=& \frac{(n+1)^{k+1} – 1}{k+1} – \frac{1}{k+1} \sum _ {i=0}^{k-1} {{k+1} \choose i} f _ i(n)
\end{eqnarray}
$$
先将整数扩展到更好求的实数域求完之后再减去误差这种方法挺不错的啊

dna094的方法

链接先放上来,我看完再写。
update(2019-2-19): 最近有很多其他更重要的事情要做,先坑在这里,闲的时候再说

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注