知识库 · 文字讲解,AI 整理
望远镜求和与 Gosper 算法
如果能找到 $g$ 使
LaTeX
$$f(k)=g(k+1)-g(k),$$
那么中间项全部抵消:
LaTeX
$$\sum_{k=a}^b f(k)=g(b+1)-g(a).$$
这是离散版的牛顿–莱布尼茨公式:$g$ 是 $f$ 的「反差分」。例如 $k=\frac{k(k+1)}2-\frac{(k-1)k}2$,所以
LaTeX
$$\sum_{k=1}^n k=\frac{n(n+1)}2.$$
裂项求和 $\sum\frac1{k(k+1)}=\sum\bigl(\frac1k-\frac1{k+1}\bigr)$ 也是这一条。
Gosper 算法
对超几何项(相邻两项之比是 $k$ 的有理函数),Gosper 算法能系统地判断有没有超几何形式的反差分,有就把它找出来。不是每一项都有:$\sum1/k$ 就没有,所以调和数没有封闭形式。
用到它的地方
- 知识库 欧拉和
- 知识库 牛顿–莱布尼茨公式为什么成立
- 知识库 生成函数
- 知识库 幂和与 Bernoulli 数
- 知识库 前缀和与差分
- 知识库 对级数可以做哪些运算
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。