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

Author Avatar
Ivan Chen 3月 23, 2019
  • 在其它设备中阅读本文章

求多项式数列 $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$ 的答案.

本文采用知识共享 署名-相同方式共享 4.0 国际许可协议(CC BY-SA 4.0)进行许可。
本文链接: https://idkidknow.com/2019/03/23/多项式数列求和的计算方式/