多项式数列求和的计算方式

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

\(k=0\) 时, \(\sum_{i=1}^n i^k=n\)

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

对于一般的 \(k\), 可用以下方式递归求得

\[\sum_{i=1}^n((i+1)^{k+1}-i^{k+1})=\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\]

\[\therefore \sum_{i=1}^n i^k=\frac{1}{k+1}((n+1)^{k+1}-\sum_{j=0}^{k-1} \binom{k+1}{j} \sum_{i=1}^n i^j)\]

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