我们设 \(\operatorname{f}_k(n) = \sum\limits_{i = 1}^{n}i^k\)
如果已知 \(\operatorname{f}_{k-1}(n)\)，如何推导至 \(\operatorname{f}_k(n)\)？
首先发现：
\[\operatorname{f}_k(n) = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}j^{k-1} \]于是就有：
\[\begin{aligned}\operatorname{f}_k(n) &= \sum\limits_{i = 1}^{n}\operatorname{f}_{k-1}(n)-\operatorname{f}_{k-1}(i-1)\\ &= n \cdot \operatorname{f}_{k-1}(n)-\sum\limits_{i = 1}^{n}\operatorname{f}_{k-1}(i-1)\end{aligned}\]所以次数就降下来了。
再往里面代一下 \(\operatorname{f}_{k-1}(n)\) 的式子即可。
（虽然但是，这玩意的 \(k\) 越大，推导过程中式子的复杂度就越高，不是很好推的样子）
有人有别的好法嘛？
标签：前缀,limits,sum,如何,aligned,operatorname,式子 From： https://www.cnblogs.com/bikuhiku/p/get_pre_f.html