求多项式数列 $a_n=f(n)$ 的前 $n$ 项和，只需找出 $\sum_{i=1}^n i^k$ 的计算方法，其中 $k\in \mathbb{N}$

$k=0$ 时，$\displaystyle \sum_{i=1}^n i^k=n$

$k=1$ 时，$\displaystyle \sum_{i=1}^n i^k=\frac{n(n+1)}{2}$

对于一般的 $k$，可用以下方式递归求得

$\sum_{i=1}^n\bigl((i+1)^{k+1}-i^{k+1}\bigr)=\sum_{i=1}^n \sum_{j=0}^k \binom{k+1}{j}i^j$

$(n+1)^{k+1}-1=\sum_{j=0}^k \sum_{i=1}^n \binom{k+1}{j}i^j=\sum_{j=0}^{k-1} \binom{k+1}{j} \sum_{i-1}^{n}i^j+(k+1)\sum_{i=1}^n i^k$

于是有

$\sum_{i=1}^n i^k=\frac{1}{k+1}\left((n+1)^{k+1}-\sum_{j=0}^{k-1} \binom{k+1}{j} \sum_{i=1}^n i^j\right)$

其中右侧的 $\sum_{i=1}^n i^j$ 中 $j<k$，即求得 $k=0,1,2,\dots,m-1$ 的答案就能求出 $k=m$ 的答案。