数学浅谈：Gosper裂项算法

· · 学习·文化课

前言：

你是否曾被恐怖的数列求和所困扰？是否又被答案神乎其神的注意到然后裂项相消给整蒙过？

我们能否像解析几何那样，用暴力、流程化的方式解决数列求和呢？

有的，兄弟！有的！

接下来，我将为你介绍这种机械化解题的裂项算法：Gosper 算法。

::::info[注]{open} 本人 SD 蒟蒻初二，有错勿喷，回复纠错闭关。 ::::

本文重点介绍 Gosper 算法如何使用，而非证明。（显然，证明并是不太有用）

更细致的补充可以看dongzhenmao大佬的这篇文章。

引入：

在小学阶段，我们便开始接触裂项，最经典的，莫过于这道题：

计算：\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + \frac{1}{20} + \frac{1}{30} + \frac{1}{42}

小学老师会反复强调，这类问题可以变成：

(\frac{1}{1} - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + (\frac{1}{3} - \frac{1}{4}) + (\frac{1}{4} - \frac{1}{5}) + (\frac{1}{5} - \frac{1}{6}) + (\frac{1}{6} - \frac{1}{7})

所以最终结果就等于：1 - \frac{1}{7} = \frac{6}{7}

这便是裂项。

到了高中，学到了等差与等比，便会遇到另一道经典题目：

计算：\frac{1}{2} + \frac{2}{2 ^ 2} + \frac{3}{2 ^ 3} + \cdots + \frac{n}{2 ^ n}

这时老师会告诉我们，错位相减，便可以消掉中间项。

但其实这也可以裂项：

\sum_{i = 1}^{n}{\frac{i}{2 ^ i}} = \sum_{i = 1}^{n}{(\frac{i + 1}{2 ^ {i - 1}} - \frac{i + 2}{2 ^ i})} = 2 - \frac{n + 2}{2 ^ n}

这便是裂项的力量。

但有时裂项的规律并不明显，需要很强的数学直觉，才能一眼看出，俗称“注意到”。

为了解决这个麻烦，比尔·戈斯珀（Bill Gosper）于 1977 年发明了 Gosper 算法，使像我一样的蒟蒻也能机械化的构造出复杂的裂项。

Gosper 算法：

对于一个数列的求和：

\sum_{i = 1}^{n}{f(i)}

其中 f(i) (i = 1, 2, \cdots , n) 是一个整数序列。

我们想要把它变成这样的形式：

\sum_{i = 1}^{n}{f(i)} = \sum_{i = 1}^{n}{F(i + 1) - F(i)}

然后就可以利用和式恒等变换，求得结果等于 F(n + 1) - F(1)。

第一步

将数列的相邻两项作比，化为最简分式，记为：

\frac{f(k + 1)}{f(k)} = \frac{p(k + 1)}{p(k)} \cdot \frac{q(k)}{r(k + 1)}

先设 p(k) = 1，然后分解 q(k) 和 r(k)。

\begin{cases}p(k) = C_q(k + q_1)(k + q_2)\cdots(k + q_n)\\r(k) = C_r(k + r_1)(k + r_2)\cdots(k + r_n)\end{cases}

必须分解成最简，是在分解不了就用复数。

第二步

若对 \forall i, j 满足 q_i -r_j 不是正整数，则跳过这一步。

对于每对使 q_i - r_j 为正整数的 i,j，对 p(k) 乘上 \prod_{i = 1}^{q_i - r_j - 1}{k + r_j + n}，然后把这对 i, j 随对应的因式从 q(k) 和 r(k) 中删去，直至不存在这样的 i, j。

第三步

此时，我们已经确定了 p, q, r 三个函数，本人建议在这一步之前代入验算一下，看看是否相等。（如果你实力强悍，计算从未出过错的话，当我没说）

先定义一个运算 d_F，表示函数 F 的最高项次数。特别的，我们定义 0 的次数是 -1。

算出下面两个函数：

\begin{cases}Q(k) = q(k) - r(k)\\R(k) = q(k) + r(k)\end{cases}

按一下判断规则算出一个判别因子 d：

d = \begin{cases}d_p - d_Q & d_Q \ge d_R\\d_p - d_R + 1 & d_Q < d_R\end{cases}

第四步

根据上一步算出的这个 d 进行判别：

第五步（最后一步）

解 Gosper 方程：p(k) = q(k)s(k + 1) - r(k)s(k)

别看它长得稀奇古怪，实际上里面的 p, q, r 都是已知。

待定系数求 s：设 s(k) = a_d k^d + a_{d - 1}k ^ {d - 1} + \cdots + s_1 k + s_0

注：这里的 d 一般都很小，所以不用担心解多元方程。

最后，裂项函数即为：F(k) = \frac{r(k)s(k)f(k)}{p(k)}

算法总结与说明：

如果你认真阅读了上面的内容的话，你会发现这个算法极具流程化，完全不需要思考，重点在于计算，非常适合数列小白。特别的，Gosper 算法高考不能直接用，我作为初中生并不担心，所以只是提醒各位一下。

这个算法还是很考验计算功底的，尤其是在求 p, q, r 的过程中。基本功不好的，可能使用起来很耗时间，但只要计算不出错，这个算法能在一两分钟内解决题目。（本人亲测）

刚接触到该算法时，肯定是无法将流程全记住的。（如果你可以，受我一拜）前期希望大家对照着过程逐步进行，或许会花不少时间，但确实能使你对算法的掌握和理解程度有很大的提升。

此算法擅长解决组合数求和，可以体会一下下面的例5和例7。

例题：

前三例较为基础，希望大家能够自己做出来，这样能很快适应这个算法。

为了方便大家理解，以下的题解并不是非常规范，（~比如没有写“解”~），当然本人实力有限，还请谅解。

但保证不会像“某蓝本”那样：读者可以试着自己证明……

例1：

计算：

\sum_{i = 1}^{n}{i^2 - i}

（选自《平行线高中数学联赛一试强化训练题集》 3.2 裂项思维的应用~好像叫这个~）

::::success[题解] 法1（Gosper 算法）：

相邻两项作比：\frac{(k + 1)^2 - (k + 1)}{k^2 - k} = \frac{k + 1}{k - 1} = \frac{p(k + 1)}{p(k)} \cdot \frac{q(k)}{r(k + 1)}

不难算出，q, r 均等于 1，p(k) = k^2 - k。

代入算得 Q(k) = 0, R(k) = 2, d = 3，可以用 Gosper 算法。（此处注意 d_Q = -1）

待定系数：s(k) = ak^3 + bk^2 + ck + d。

随便代入三个 k，同时发现 d 无关紧要，解出 s(k) = \frac{k(k - 1)(k - 2)}{3}。

注：请把此处的 d 与前文算得的判别因子 d 区分开。

最后，代入裂项函数：F(k) = \frac{k(k - 1)(k - 2)}{3}（此处 p 和 f 约去了）

所以最终结果为：

\sum_{i = 1}^{n}{i^2 - i} = \sum_{i = 1}^{n}{F(i + 1) - F(i)} = \sum_{i = 1}^{n}{\frac{1}{3}[(i + 1)i(i - 1) - i(i - 1)(i - 2)]} = \frac{n^ 3 - n}{3}

当然，如果你有点常识的话，这题还可以做简单点。

法2（高斯求和）：

利用求和公式：

\sum_{i=1}^{n}i=\frac{n(n+1)}2,\qquad\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}6

因此，

\begin{aligned}\sum_{i = 1}^{n}(i ^ 2 - i)& = \sum_{i = 1}^{n}i^2-\sum_{i=1}^{n}i\\[4pt]&=\frac{n(n+1)(2n+1)}6-\frac{n(n+1)}2\\[4pt]&=\frac{n^ 3 - n}{3}\end{aligned}

注：其实这里的二阶等差求和也可以用 Gosper 算法证明。

例2：

计算：

\sum_{i = 1}^{n}{(-1)^iC_n^i}

(保证 n \ge 1) ::::success[题解] 法1：

相邻两项作比：\frac{f(k + 1)}{f(k)} = \frac{k - n}{k + 1} = \frac{p(k + 1)}{p(k)} \cdot \frac{q(k)}{r(k + 1)}

算出 p(k) = 1, q(k) = k - n, r(k) = k。

进而得到：Q(k) = -n, R(k) = 2k - n

> 注：这里把 $n$ 看作变量。 解 Gosper 方程：$1 = (k - n)s_0 - ks_0 \implies s(k) = s_0 = -\frac{1}{n}

裂项函数为：F(k) = k(-\frac{1}{n})(-1)^kC_n^k = (-1)^{k - 1}C_{n - 1}^{k - 1}

从而算得总和等于 -1。

相比上一题，这道题的巧解就并不是那么明显了，至少你得会二项式定理。

法2：

注意到（或由二项式定理得）：

(1 - 1)^n = \sum_{i=0}^{n}{(-1)^iC_n^i}

所以：

0 = 1 + \sum_{i = 1}^{n}{(-1)^iC_n^i}
即得 \sum_{i = 1}^{n}{(-1)^iC_n^i} = -1。

例3：

设 a_k = k\cdot k!，求：\sum_{k = 1}^{n}a_k

（2025年山东青岛一模）~出道自己地区的题，嘿嘿。~

::::success[题解] 相邻两项作比，算出 p(k) = k, q(k) = k + 1, r(k) = 1。

推出 d = 0，可用。

知 s 为常数。代入 Gosper 方程，解得：s(k) = 1。

所以列项函数为：F(k) = \frac{r(k)s(k)f(k)}{p(k)} = k!。

故总和为：\sum_{k = 1}^{n}a_k = \sum_{k = 1}^{n}{(k + 1)! - k!} = (n + 1)! - 1。

注：我认为这题应该能直接注意到 k\cdot k! = (k + 1)! - k!，这便是 Gosper 算法的劣势所在，它无法在过程中发现一些显然的性质，导致多花费了许多时间。

对于这题本人并未找到巧解，而且标答给的也是裂项，如有发现巧解，欢迎私信探讨。

::::info[中场休息]{open} 如果你有认真做上面三道题的话，现在应该已经对 Gosper 算法有所领悟了吧。（我相信切高考题肯定没问题）

接下来的题目难度会有所提升，且并不好找巧解（还是我太菜了），我将仅介绍 Gosper 算法的做法，如果对下面的例题有更好的做法，欢迎私信我，谢谢。

例4：

求：

\sum_{k=1}^{n} \frac{4k+6}{k(k+1)(k+2)(k+3)}

::::success[题解] 相邻两项作比，化简得：

\frac{f_{k+1}}{f_k} &=\frac{4k+10}{4k+6} \frac{k(k+1)(k+2)(k+3)} {(k+1)(k+2)(k+3)(k+4)}\\ &=\frac{k(2k+5)}{(k+4)(2k+3)} \end{aligned}

算得：p(k)=2k+3,\quad q(k)=k,\quad r(k)=k+3。

验证：

\frac{p(k+1)}{p(k)} \frac{q(k)}{r(k+1)} = \frac{2k+5}{2k+3}\cdot\frac{k}{k+4}

从而 Q(k) = -3, R(k) = 2k + 3 \implies d = 1，可用。

待定系数，设 s(k) = ak + b。

解 Gosper 方程：2k + 3 = k[a(k + 1) + b] - (k + 3)(ak + b)

解得 s(k) = -k - 1。

算出 F(k)=-\frac{2}{k(k+2)}。

故答案为：\boxed{1 - \frac{2}{(n + 1)(n + 3)}}

例5：

设 n\ge 1，求

\sum_{k=1}^{n}(-1)^k\binom nk\frac{k+2}{k+1}

::::success[题解] 利用 \frac{\binom n{k+1}}{\binom nk}=\frac{n-k}{k+1}

可得

\begin{aligned}\frac{f_{k+1}}{f_k}&=-\frac{n-k}{k+1}\frac{k+3}{k+2}\frac{k+1}{k+2}\\&=\frac{(k-n)(k+3)}{(k+2)^2}\end{aligned}

算得：p(k)=k + 2,\quad q(k)=k - n,\quad r(k)=(k+1)

进而得：Q(k)=-n - 1, R(k)=2k + 1

故 d = 1，可用。

设 s(k) = ak + b，代入 Gosper 方程：k+2=(k-n)s(k+1)-(k+1)s(k)

解得 s(k)=-\frac{k}{n}-\frac1{n+1}。

代入：

\begin{aligned}F(k) &= \frac{k+1}{k+2}\left(-\frac{k}{n}-\frac1{n+1}\right)(-1)^k\binom nk\frac{k+2}{k+1}\\&=(-1)^{k-1}\binom nk\left(\frac{k}{n}+\frac1{n+1}\right)\end{aligned}
答案为：\boxed{-2 + \frac1{n + 1}}

例6：

求：

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

::::success[题解] 相邻两项作比：

\begin{aligned} \frac{f_{k+1}}{f_k} &= \frac{2k+3}{2k+1}\frac{(k^2+1)((k+1)^2+1)}{((k+1)^2+1)((k+2)^2+1)}\\ &= \frac{2k+3}{2k+1} \frac{k^2+1}{(k+2)^2+1}\end{aligned}

算得 p(k) = 2k + 1, q(k) = (k + i)(k - i), r(k) = (k + 1 + i)(k + 1 - i)。

注：这里的 i 代表虚数单位（即 \sqrt{-1}），此处需要将因式分解到最简的一次因子，以防出存在 i,j，使 q_i - r_j 为正整数。

Q(k) = -2k - 1, R(k) = 2k^2 + 2k + 3 \implies d = 0 裂项函数为 $$\begin{aligned}F(k) &=\frac{r(k)s(k)f(k)}{p(k)}\\&=-\frac{(k+1)^2+1}{2k+1}\frac{2k+1}{(k^2+1)((k+1)^2+1)}\\&=-\frac1{k^2+1}\end{aligned}$$ 故，答案为： $$\boxed{F(n+1)-F(1) = -\frac1{(n+1)^2+1} + \frac12}$$ ::::

例7：

计算：

\sum_{k = 1}^{n}{(-1)^{k - 1}\dbinom{2n}{k}^{-1}}

注：来自泰勒猫爱丽丝的一期视频。我超喜欢这个 up 主，物理和数学双一流，希望大家能欣赏和关注他。

::::success[题解] 两项作比，一些简单的化简算得结果为 \frac{k + 1}{k - 2n}。

算出 p = 1, q = k + 1, r = k - 2n - 1。

算出 d = 0。

$$F(k) = \frac{k - 2n - 1}{2n + 2}(-1)^{k -1}\dbinom{2n}{k}^{-1}$$ 总和就显然了，由于临近考试，时间紧迫，大家就自己算吧。 ::::

后记：

对学生的：

Gosper 算法作为一个裂项技巧，而且是高级裂项技巧，在高考中，甚至在联赛中都是不能直接使用的，所以我建议上述过程只出现在草稿本上，对于答题过程，可以参考如下模板（说模板是扯的，你们看看就好了）：

答题模板：

解：考虑裂项求和，注意到：\text{所求的抄一遍} = \sum_{i = a}^{b}{F(i + 1) - F(i)} = F(b + 1) - F(a) = \text{答案}

其中 a, b 分别代表所求范围的下届和上界。

（F(i) 是你草稿本上算的裂项函数，这里别傻乎乎的写上 F(i) 了哈）

而且，这种算法对于我们的能力并没有实质的提升作用，所以我建议，遇到题目还是多思考性质和特点，而非暴力计算。

对教练和老师的：

如果你是一位教练或老师，想要以此出裂项相关的题来~恶心~帮助学生训练思维的话，可以用 Gosper 算法反向构造题目，构造的步骤大概如下：

习题：

恭喜FantasySegmentTree大佬首个拿下全部习题，有人反应习题太简单了，我再次深表歉意。

求：

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

::::info[答案]

1 - \frac1{(n + 1)^2}

::::

求：

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

::::info[答案]

\frac14 - \frac1{2(n + 1)(n + 2)}

::::

求：

\sum_{i = 1}^{n}{ \frac{i}{i^4 + i^2 + 1}}

::::info[答案]

\frac12(1 - \frac1{n^2 + n + 1})

::::

计算：\sum_{i = 2}^{n}i2^i

注：来自泰勒猫爱丽丝的一期视频。我超喜欢这个 up 主，物理和数学双一流，希望大家能欣赏和关注他。

::::info[答案]

(n - 1)2^{n + 1}

::::

裂项相关

以下题目与本文关联并不大。

计算：

\sum_{i = 1}^{n}{\sqrt{1 + \frac1{i^2} + \frac1{(i + 1)^2}}}

注：此题改编自我们初二周测的一道活动题（恐怖），仅仅把原题给出的探究过程还有例子删了，并未加强。（这道题其实用不了 Gosper 算法，我只是想防止有人用 AI 骗奖励，直接展开根号里面的即可裂项） ::::info[答案] 直接展开算根号下面的就行，刚好是平方式，答案是 n + 1 - \frac1{n + 1}. ::::

计算：

\displaystyle\sum_{k=1}^n \frac{1}{\sqrt[3]{(k + 1)^2} + \sqrt[3]{k(k + 1)} + \sqrt[3]{k^2}}

感谢zhangxiaoyu008大佬投的好题。 ::::info[答案] 我们知道有立方差公式 (a - b)(a^2 + ab + b^2) = a^3 - b^3 \Longleftrightarrow a - b = \frac{a^3 - b^3}{a^2 + ab + b^2}。

令 a = \sqrt[3]{k + 1}, b = \sqrt[3]{k}，发现 a^3 - b^3 = (k + 1) - k = 1，进而有 \frac{1}{\sqrt[3]{(k + 1)^2} + \sqrt[3]{k(k + 1)} + \sqrt[3]{k^2}} = \sqrt[3]{k + 1} - \sqrt[3]k。

故：

\text{原式}=\sum_{k = 1}^{n}{\sqrt[3]{k + 1} - \sqrt[3]k} = \sqrt[3]{n + 1} - 1
虽然这题与 Gosper 算法没啥关系，但也是道裂项的好题，重点在于注意到立方差公式的转换。

结语：

完结撒花，审核员辛苦了，希望这篇文章能给大家带来一定帮助和思维的启发，期待未来菲尔兹奖有你一份。