Gosper裂项

Jomo1203 · 2025-09-08 15:02:48 · 算法·理论

我们在学习中时常会遇见一系列的求和问题，比如

这个求和很简单，不难发现 \frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}，这样就能直接把中间的项给消掉，只需计算开头和结尾的前后两项即可。

这给我们一个启发，我们似乎可以将某些函数 t(k) 写成另一个函数 T(k) 的相邻两项之差 t(k)=T(k+1)-T(k) 的形式，这样我们便可以消去中间的项，只计算两边的项

有时候求和的式子很复杂，如

那如何计算 T(k) 的表达式呢？这就得用到 Gosper 算法了，它是解决组合数求和的利器，在此声明，下文中的例子都用上式。 这种算法只针对超几何函数求和，纯机械化，只要想算一定会有有一个结果。

Gosper 的推导

首先，我们不难发现

是一个有理函数，设其为有理函数 y(k)，将 T(k)=y(k)t(k) 代入上一话的式子中，则

设 z(k)=\frac{t(k+1)}{t(k)}，就有

假设我们能将 z(k) 写成这样的形式

其中 q(k) 与 r(k) 满足，对于所有 h\in\N，有

注意，这里的 q(k)\perp r(k+h)) 等价于 \deg\gcd(q(k),r(k+h))=0，其中 \deg 表示多项式的最高次数。

在后续的证明中，我们会发现解有理函数的问题被转换为了求解多项式的问题。

我们考虑将 y(k) 写成下面的形式

将它与 z(k)=\frac{p(k+1)q(k)}{p(k)r(k+1)} 代入 y(k+1)z(k)-y(k)=1，可得

现在我们如果解出了 s(k)，便能反代出 T(k)=\frac{r(k)s(k)}{p(k)}t(k)。

这样我们就确定了 Gosper 的算法流程：

1. 将 z(k)=\frac{t(k+1)}{t(k)}，分解成满足条件的 \frac{p(k+1)q(k)}{p(k)r(k+1)} 的形式。
2. 找到方程的解 s(k)，或者得知无解，终止运算。
3. 若有解，则 T(k)=\frac{r(k)s(k)}{p(k)}t(k)。

好了，思路有了，但在前两个过程中仍有很多困难：

1. 这个对 z(k) 的有条件的分解一看就很逆天，有时系数瞪不出来你不就炸了吗？
2. 在自变量不同的时候解有理函数 s(k) 还是太吃操作了，有没有简单点的方法推荐一下呢？

为了使它成为傻瓜式算法，我们还要提供一种机械化的计算方法。

机械化分解

首先设 z(k)=\frac{C_ff(k)}{C_gg(k)}，为了方便，这里的 f(k) 和 g(k) 都是首一多项式，且满足 f(k)\perp g(k)，前面的 C_f 与 C_g 都是保证左右相等的系数。

如果 q(k)=f(k),r(k)=g(k-1) 满足上面的条件，那么我们可以直接令 q(k)=f(k),r(k)=g(k-1),p(k)=1，这样就结束了。

但是，如果不满足条件，即存在 h\in\N 使得 f(k) 和 g(k+h) 有公因式 x(k)，那我们可以令最开始 q(k)=f(k),r(k+1)=g(k),p(k)=1， 递归的找出 q(k) 和 r(k+h+1) 的 x(k)，然后

这里为了直接修改 p(k)，可以先将 \frac{x(k)}{x(k-h)} 这样展开

这样，我们就可以这样修改 p(k)

如此往复，便能得到结果。

判断两个多项式是否满足条件，可以将其因式分解，判断是否有 a,b 满足 (k+a)|q(k),(k+b)|r(k+1)，且 a-b 不为正整数。

解方程

实际上，s(k) 会是一个多项式，在这里用反证法给出简单证明。

为了方便阅读，在这里写出方程

假设命题为假，那么我们就能将 s(k) 写成 \frac{f(k)}{g(k)}，其中 f(k)\perp g(k) 且 \deg g(k)\ne0。

将其代入方程，则

设 N 是使 \gcd(g(k),g(k+N)) 为非常多项式的最大整数，容易知道 N\geq0。

设 x(k) 为 g(k) 和 g(k+N) 的一个非常数多项式的不可约公因式，将 x(k-N)|g(n) 代入方程，因为它整除 q(k)f(k+1)g(k) 和 p(k)g(k)g(k+1)，得

因为 x(k-N)|g(k)，且 f(k)\perp g(k)，故 x(k-N)\nmid f(k)。

若 x(k-N)|g(k+1)，则 x(k)|g(k+N+1)，即 \gcd(g(k),g(k+N+1)) 为非常多项式，与 N 的选取要求矛盾，所以 x(k-N)\nmid g(k+1)。

因此，x(k-N)|r(k)，即 x(k+1)|r(k+N+1)。

同样，将 x(k+1)|g(k+1) 代入方程，因为它整除 r(k)f(k)g(k+1) 和 p(k)g(k)g(k+1)，得

由于 x(k+1)|g(k+1) 且 f(k+1)\perp g(k+1)，则 x(k+1)\nmid f(k+1)。

若 x(k+1)|g(k)，则 x(k)|g(k-1)，又因为 x(k)|g(k+N)，所以 \gcd(g(k-1),g(k+N)) 为非常多项式，即 \gcd(g(k),g(k+N+1)) 为非常多项式，与 N 的选取要求矛盾，所以 x(k-1)\nmid g(k)。

因此，x(k+1)|q(k)。

于是，x(k+1) 是 q(k) 和 r(k+N+1) 的一个非常多项式的公因式，与前面的对选取 q(k) 和 r(k) 的要求不符，因此 s(k) 得是一个多项式。

这里同样可以解释，我们在选取 q(k) 和 r(k) 时之所以要有那个要求，就是为了使得现在得 s(k) 必须是多项式。

如果 s(k) 是多项式，这无疑为 s(k) 求解降低了很多难度。

求 s(k) 的表达式，可以用待定系数法，而使用待定系数法首先要确定它的次数。

设 d=\deg s(k)，现在来求 d 的值，我们可以将方程改写为

设 Q(k)=q(k)-r(k),R(k)=q(k)+r(k)。

容易发现，如果 \deg Q(k)\geq\deg R(k)，有 d=\deg p(k)-\deg Q(k)，否则 \deg q(k)=\deg r(k)=d' 且 [k^{d'}]q(k)=[k^{d'}]r(k)，所以它们的最高次项抵消了，因此上面变形后的方程的右边的实际最高次数为 d+d'-1，得 d=\deg p(k)-d'+1。

如果 d<0，就说明方程无解，Gosper 算法不适用，否则解方程就行了。

接下来的待定系数，大家都会，这里就跳过了。

使用示例

用的是最开始的的那个长例子

令 t(k)=\frac{4k+3}{(n-2k-2)!(n+2k+1)!}，直接作比

直接分解

注意，我们不将 n 这样的系数视为整数。

现在计算辅助多项式，有时一眼能瞪出它们的次数，就不必展开计算了

所以 d=\deg p(k)-\deg R(k)+1=0

设 s(k)=s_0，则

解得 s(k)=s_0=\frac1{2(1-n)}，所以 T(k)=\frac{r(k)s(k)}{p(k)}t(k)=-\frac1{(2n-2)}\binom{2n-3}{n+2k+1}

由于 \lim\limits_{k\to\infin}T(k)=0，所以

小结

氵了 4.8k 字，简单介绍了 Gosper 算法，它能帮助我系统地计算超几何项的不定求和。但遗憾的是，如果题目不刻意安排，那绝大多数情况下求和最后的结果并不是一个封闭形式，所以在 OI 中应用不广泛，不过应对一些求和题还是很轻松的。

出几道形式复杂一点的题，求下列求和，由于过程十分雷同，就不展示了。

:::info[答案]

:::