数列求和中的 Gosper 算法
xixisuper
·
·
学习·文化课
前言
刚升高二，正在与众多数列题死斗，本文章源于笔者对求和的系统解决技巧的渴望，以及对一些出题人的优美构造的敬佩。
引入
考虑计算一个这样的求和：
\sum_{a}^bf(x)\delta x=\sum_{i=a}^{b-1}f(i)
一种的想法是考虑找到一个函数 F(x)，满足：
\Delta F(x)=F(x+1)-F(x)=f(x)
则对于上述求和式，就可以非常简单的写成：
\sum_{a}^bf(x)\delta x=F(b)-F(a)
那么问题来了，怎么求这个函数 F(x) 嘞？
Gosper 算法
在 1977 年，Gosper 提出了一个得到 F(x) 的优美的办法，我们下面来详细的讲解这个算法。
算法的第一步，是计算求和项之比，并将其表示成一个特殊的形式：
\frac{f(x+1)}{f(x)}=\frac{p(x+1)}{p(x)}\cdot\frac{q(x)}{r(x+1)}
其中，q,p,r 是三个多项式，并满足如下条件：
\begin{aligned}
\forall &~\alpha \in \mathbb{C} ~\text{such that}~ (x+\alpha)\mid q(x)\\
&~\beta\in\mathbb{C}~\text{such that}~ (x+\beta)\mid r(x)\\
\Rightarrow & ~\alpha-\beta\not\in \N^*
\end{aligned}
说人话就是函数 q(-x) 的任意零点与函数 r(-x) 的任意零点相减，差值不为正整数。
但是如果我们直接把令 p(x)=1，是很难直接得到满足条件的 q(x) 和 r(x) 的，举个简单的例子：
f(x)=\frac{x}{2^x}\Rightarrow\frac{f(x+1)}{f(x)}=\frac{x+1}{2x}
那么你得到的就是应该是：
\begin{cases}
q(x)=x+1\\
r(x)=2(x-1)
\end{cases}
但是很不幸的是，你发现 1-(-1)=2\in \N^*，怎么办呢？
这时就要把搁置在一旁的 p(x) 用起来，每当你在 p,r 中找到一对这样的 \alpha,\beta 的时候，就把 (x+\alpha) 与 (x+\beta) 从对应的多项式中删掉，并进行：
p(x)\leftarrow p(x)\cdot\prod_{i=\beta+1}^{\alpha-1}(x+i)
不难验证，进行如上操作后 \frac{p(x+1)}{p(x)} 就会把 \frac{(x+\alpha)}{(x+\beta+1)} 带走。
这时候你可能会有疑问，要是 \alpha-\beta=1 怎么办？仔细思考后你会发现，这种情况在 \frac{q(x)}{r(x+1)} 时就会直接约分掉了，所以不会出现问题。
综上，我们得到的三个多项式分别为：
\begin{cases}
p(x)=x\\
q(x)=1\\
r(x)=2
\end{cases}
下一步，是提取多项式的次数。我们用 \deg 来表示取一个多项式的次数，特别的，我们把常数 0 的次数定义为 -1，非零常数的系数定义为 0。
记 \deg_p,\deg_q,\deg_r 分别为多项式 p,q,r 的次数，并构造多项式 Q,R：
\begin{cases}
Q(x)=q(x)-r(x)\\
R(x)=q(x)+r(x)
\end{cases}
我们不需要实际上计算出 Q,R 的每一项，我们只需要提取其次数 \deg_Q,\deg_R。然后，得到一个值 d，其被定义为：
d=
\begin{cases}
\deg_p-\deg_Q & \deg_Q\ge\deg_R\\
\deg_p-\deg_R+1 & \text{otherwise}
\end{cases}
如果 d\ge0，则可以继续进行裂项，否则不可以。
验证 \frac{x}{2^x} 是否满足，能够计算得到 d=1>0，可以裂。
下一步，就是要得到 F(x) 是什么了，设存在函数 s(x)，满足：
F(x)=\frac{r(x)\cdot s(x)\cdot f(x)}{p(x)}
为了计算 s(x)，我们能够得到一个函数方程：
\begin{aligned}
f(x)&=\frac{r(x+1)\cdot s(x+1)\cdot f(x+1)}{p(x+1)}-\frac{r(x)\cdot s(x)\cdot f(x)}{p(x)}\\
f(x)&=\frac{r(x+1)\cdot s(x+1)\cdot f(x+1)\cdot f(x)}{p(x+1)\cdot f(x)}-\frac{r(x)\cdot s(x)\cdot f(x)}{p(x)}\\
f(x)&=f(x)\cdot\left(\frac{q(x)\cdot s(x+1)-r(x)\cdot s(x)}{p(x)}\right)\\
p(x)&=q(x)\cdot s(x+1)-r(x)\cdot s(x)
\end{aligned}
由于 p,q,r 都是已知的，而且 Gosper 断言函数 s(x) 是一个次数为 d 的多项式，所以我们可以直接待定系数。
还是最开始的例子，能够得到 s(x) 的系数都是 -1，最后铠甲合体，就能够得到最后的答案啦！
F(x)=-\frac{k+1}{2^{k-1}}
例题
例题 1：
f(x)=(2x+1)\cdot 5^x\\~\\\sum f(x)\delta x=?
:::success[答案]
\frac{(4x-3)\cdot 5^x}{8}
:::
例题 2：
f(n)=(-1)^n\cdot n^2\\~\\\sum f(n)\delta n=?
:::success[答案]
-\frac{1}{2}(n^2-n)\cdot (-1)^n
:::
例题 3：
f(n)=(-1)^n\cdot\frac{2n+1}{n(n+1)}\\~\\\sum f(n)\delta n=?
:::success[答案]
\frac{(-1)^{n+1}}{n}
:::
例题 4：
f(n)=\frac{n+2}{n(n+1)\cdot 2^{n+1}}\\~\\\sum f(n)\delta n=?
:::success[答案]
\frac{1}{n\cdot 2^n}
:::
例题可能会有更新，更新的题目大多来自于笔者的数学作业。
鸣谢
大量参考 B 站泰勒猫爱丽丝的视频系统性裂项方法：重温 Gosper 裂项。
部分参考具体数学中“部分超几何合式”部分。