外观
Skip to content 查看源代码：
查看源代码：
Gosper-algorithm.md
---
title: Gosper 求和法
createTime: 2026/1/9
categories:
- study
tags:
- maths
- study-note
---
可以当作《具体数学》5.7 节的读书笔记，不过这篇笔记对一些流程给出了更简洁的形式以便记忆。
## 简要介绍
:::warning
为了突出代数属性，我们将使用 $t(k)$ 而非 $t_k$ 表示数列。
:::
如果数列 $t(k)$ 满足 $\dfrac{t(k+1)}{t(k)}$ 是关于 $k$ 的有理函数（即两多项式之比），则称 $t(k)$ 是一个**超几何项**数列。
Gosper 算法可以对一个超几何项数列 $t(k)$ 求出另一个超几何项数列 $T(k)$ 使得 $t(k) = T(k+1) - T(k)$，或者报告它不能表示为超几何项。
以下是步骤。我把它放在前面，以便随时温习，第一次看的同学可以直接跳过。
:::theorem 步骤
1. 将 $\dfrac{t(k+1)}{t(k)}$ 表示为 $\dfrac{p(k+1)}{p(k)} \dfrac{q(k)}{r(k+1)}$
使得 $q(k)$ 的所有因式 $(k+\alpha)$ 和 $r(k)$ 的所有因式 $(k+\beta)$ 都满足 $\alpha-\beta \notin \mathbb{N}^*$；
2. 记 $Q(k)=q(k)-r(k), R(k)=q(k)+r(k)$
<span style="font-size: small;">（我们在多数情况只需要它们的次数，当然有时也需要最高次项系数）</span>
- 令 $d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \}$；
- 若 $\deg(Q) < \deg(R)$，令 $d_2 = -2 \dfrac{[k^{\deg(R)-1}] Q}{[k^{\deg(R)}] R}$，
若 $d_2 \le d$ 则忽略 $d_2$。
3. 若 $d \ge 0$，对 $d$ 次多项式待定系数解方程 $p(k) = q(k)s(k+1) - r(k)s(k)$。如果失败，尝试 $d_2$；
4. $T(k) = \dfrac{r(k)s(k)t(k)}{p(k)}$。
:::
## 第一步
:::lemma 步骤
将 $\dfrac{t(k+1)}{t(k)}$ 表示为 $\dfrac{p(k+1)}{p(k)} \dfrac{q(k)}{r(k+1)}$，其中 $p,q,r$ 都是多项式，
使得 $q(k)$ 的所有因式 $(k+\alpha)$ 和 $r(k)$ 的所有因式 $(k+\beta)$ 都满足 $\alpha-\beta \notin \mathbb{N}^*$。
:::
如果没有 $\alpha - \beta \notin \mathbb{N}^*$ 的条件，这一步是平凡的。所以我们把重心放在怎么处理冲突（相减为正整数）的因式上。
:::analysis 例子
我们先将分式因式分解好。以 $\dfrac{t(k+1)}{t(k)} = \dfrac{2\left(k+\frac{3}{2}\right)(k+4)}{k\left(k+\frac{1}{2}\right)(k+1)}$ 为例：
注意虽然分母虽然是 $r(k+1)$ 而非 $r(k)$，但是如果上下没有相同的因式（如果有请自觉回初中复习约分），冲突的判定仍然是**上下因式相减为正整数**。
于是它有两对冲突 $\left(k+\frac{3}{2}\right), \left(k+\frac{1}{2}\right)$ 和 $(k+4), (k+1)$。当然还有第三对——$(k+4), k$，不过我们处理第二对的时候会把 $(k+4)$ 处理掉，不需要考虑。
第一对冲突是软“式”子，由于上下差为 $1$，我们可以把它移到前面去，当作 $p(k)$：
$$
\dfrac{t(k+1)}{t(k)} = {\color{red}{\dfrac{\left(k+\frac{3}{2}\right)}{\left(k+\frac{1}{2}\right)}}} \dfrac{2(k+4)}{k(k+1)}
$$
第一对冲突解决了，我们来看第二对。容易想到在这对苦命鸳鸯中间插入几项：
$$
\dfrac{(k+4)}{(k+1)} = \dfrac{\phantom{(k+1)}{\color{red}{(k+2)(k+3)}}(k+4)}{(k+1){\color{red}{(k+2)(k+3)}}\phantom{(k+4)}}
$$
然后我们惊喜地发现上下因式可以移到前面去了，于是有
$$
\dfrac{t(k+1)}{t(k)} = \dfrac{\left(k+\frac{3}{2}\right)(k+2)(k+3)(k+4)}{\left(k+\frac{1}{2}\right)(k+1)(k+2)(k+3)} \dfrac{2}{k}
$$
于是 $p(k) = \left(k+\frac{1}{2}\right)(k+1)(k+2)(k+3), q(k)=2, r(k) = k \color{red} -1$。
:::
## 第二步
这应该是最难理解的一步了。实际上这一步的存在是为了辅助第三步的解方程——我们一般不会头铁到直接解，而是在第二步算出它的次数。（当然如果你的注意力够好也可以试试直接解）
为了方便地描述步骤，我们规定一些记号：
:::definition 记号
- $\deg(Q)$ 为多项式 $Q$ 的次数。特别地，$\deg(0) = -1$。
- $[k^n]Q$ 为多项式 $Q$ 的 $n$ 次项系数。
:::
:::lemma 步骤
记 $Q(k)=q(k)-r(k), R(k)=q(k)+r(k)$，分类讨论：
- 若 $\deg(Q) \ge \deg(R)$，令 $d = \deg(p)-\deg(Q)$；
- 若 $\deg(Q) < \deg(R)$，令 $d = \deg(p) - \deg(R) + 1$；
此时令 $d_2 = -2 \dfrac{[k^{\deg(R)-1}] Q}{[k^{\deg(R)}] R}$，若 $d_2 < d$ 则忽略 $d_2$。
:::
$d_2$ 的情况不常用。对于常用的情况，由于多项式的次数都是整数，我们有一个容易记忆的公式：
$$
d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \}
$$
:::center
<span style="font-size: small; color: gray;">（如果不信任本人的推导，可以自行验证）</span>
:::
来看两个例子。
:::analysis 例子
$p(k)=k, q(k)=\alpha, r(k)=1$，$\alpha$ 为参数（这是出题人最爱的差乘比，发现了吗？）
$Q(k),R(k)$ 都是常函数，$\deg(p)=1, \deg(Q)=\deg(R)=0$，
于是 $d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \} = 1$。
:::
:::analysis 例子
$p(k)=1, q(k)=k^2-3k+3, r(k)=k^2-2k+1$，此时 $Q(k)=-k+2, R(k)=2n^2-5k+4$
于是我们有 $d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \} = -1$，坏了！
所以 $d_2$ 出手了。看看系数（标红的是 $\deg(R)$ 次项，标蓝的是 $\deg(R)-1$ 次项）：
$$
Q(k) = \phantom{2k^2} \ \, {\color{blue}{-1}}k+2 \\
R(k) = {\color{red}{2}}k^2 - {\color{blue}{5}}k + 4
$$
于是 $d_2 = -2 \times \dfrac{\color{blue}{-1}}{\color{red}{2}} = 1$。
:::
## 第三步、第四步
:::lemma 步骤
若 $d \ge 0$，对 $d$ 次多项式 $s(k)$ 待定系数解方程
$$p(k) = q(k)s(k+1) - r(k)s(k)$$
如果失败，尝试 $d_2$。都失败则无解。
若有解，令 $T(k) = \dfrac{r(k)s(k)t(k)}{p(k)}$ 即可。
:::
没什么技术含量。所以我们下面不给例子，而是回答一个问题：为什么可以这么做？
:::proof
$$
\begin{align*}
T(k+1) - T(k) &= \frac{r(k+1) s(k+1) t(k+1)}{p(k+1)} - \frac{r(k)s(k)t(k)}{p(k)} \\
&= \frac{q(k) s(k+1) t(k)}{p(k)} - \frac{r(k)s(k)t(k)}{p(k)}
& (\textsf{应用 $p,q,r$ 满足的等式}) \\
&= \frac{q(k) s(k+1) t(k) - r(k)s(k)t(k)}{q(k) s(k+1) - r(k)s(k)}
& (\textsf{对分母应用 $s$ 满足的方程}) \\
&= t(k)
& (\textsf{哦，这是极好的}) \\
\end{align*}
$$
:::
~~所以 Gosper 到底是怎么注意到这件事的？~~
在这里不给出可行性证明，大家可以自行翻阅《具体数学》对应章节。
## 如何（调戏阅卷人地）写过程
注意到
$$
\sum_{k=1}^{n} t(k) = \sum_{k=1}^{n} T(k+1) - T(k) = T(n+1) - T(1)
$$
嗯，没了。
你可以酌情写多点，但注意无论如何都要硬说 $T(k+1)-T(k) = t(k)$ 是你注意到的，别把 Gosper 供出来！
## 习题
用 Gosper 求和法对 $t(k)$ 满足
1. $t(k) = k^2$
2. $t(k) = k \alpha^k, \ \ \alpha \ne 1$
3. $t(k) = k^2 \alpha^k, \ \ \alpha \ne 1$
4. $t(k) = (-1)^k \mathrm{C}_n^k,\ \ 0\le k \le n$
5. $t(k) = \dfrac{1}{k^2-1}$
6. $\dfrac{t(k+1)}{t(k)} = \dfrac{k^2-3k+3}{k^2}$
分别求 $T(k)$ 使得 $t(k) = T(k+1) - t(k)$。
## 习题解答
### 1
**第一步** $\dfrac{t(k+1)}{t(k)} = \dfrac{(k+1)^2}{k^2}, p(k)=k^2, q(k)=r(k)=1$。
**第二步** $\deg(Q)=\deg(R)-1=-1$，$d = 2-(-1) = 3$，忽略 $d_2 = 0$。
**第三步** 设 $s(k) = s_3 k^3 + s_2 k^2 + s_1 k + s_0$ 解方程
$$
k^2 = s(k+1)-s(k) = 3 s_3 k^2 + (2s_2 + 3s_3) k + s_1+s_2+s_3
$$
比对系数得 $s(k) = \dfrac{1}{3} k^3 - \dfrac{1}{2} k^2 + \dfrac{1}{6} k + s_0$。
**第四步**（实际上可以直接看出来了）
$$
T(k) = \dfrac{\left( \dfrac{1}{3} k^3 - \dfrac{1}{2} k^2 + \dfrac{1}{6} k + s_0 \right) k^2} {k^2} = \dfrac{1}{3} k^3 - \dfrac{1}{2} k^2 + \dfrac{1}{6} k + s_0
$$
当然，如果可以直接注意到 $T(k)$ 是三次的，然后直接待定系数，会更简单。这也说明了 Gosper 算法的特点：流程固定，适合机械操作。
### 2
**第一步** $\dfrac{t(k+1)}{t(k)} = \dfrac{k+1}{k} \alpha, p(k)=k, q(k)=\alpha, r(k)=1$。
**第二步** $\alpha\ne 1$ 时，$\deg(Q)=0, \deg(R)-1=-1, d = 1-0 = 1$。
**第三步** 设 $s(k)=s_1 k + s_0$，解方程
$$
k = \alpha \bigl( s_1 (k+1) + s_0 \bigr) - (s_1 k + s_0)
$$
得 $s(k) = \dfrac{1}{\alpha-1} k - \dfrac{\alpha}{(\alpha-1)^2}$。
**第四步** $T(k) = \dfrac{\left( \dfrac{1}{\alpha-1} k - \dfrac{\alpha}{(\alpha-1)^2} \right) k\alpha^k}{k} = \left( \dfrac{1}{\alpha-1} k - \dfrac{\alpha}{(\alpha-1)^2} \right) \alpha^k$。
### 3
**第一步** $\dfrac{t(k+1)}{t(k)} = \dfrac{(k+1)^2}{k^2} \alpha, p(k)=k^2, q(k)=\alpha, r(k)=1$。
**第二步** $\alpha\ne 1$ 时，$\deg(Q)=0, \deg(R)-1=-1, d = 2-0 = 2$。
**第三步** 设 $s(k) = s_2 k^2 + s_1 k + s_0$，解方程
$$
k^2 = \alpha \bigl( s_2 (k+1)^2 + s_1 (k+1) + s_0 \bigr) - (s_2 k^2 + s_1 k + s_0)
$$
解得 $s(k) = \dfrac{1}{a-1} k^2 - \dfrac{2a}{(a-1)^2} k + \dfrac{a(a+1)}{(a-1)^3}$.
**第四步** $T(k) = \left( \dfrac{1}{a-1} k^2 - \dfrac{2a}{(a-1)^2} k + \dfrac{a(a+1)}{(a-1)^3} \right) \alpha^k$
### 4
**第一步** $\dfrac{t(k+1)}{t(k)} = - \dfrac{k!(n-k)!}{(k+1)!(n-k-1)!} = \dfrac{k-n}{k+1}$，
$p(k)=1, q(k)=k-n, r(k)=k$。由于 $-n-1 < 0$，不存在冲突。
**第二步** $Q(k)=-n, R(k)=2k-n \Longrightarrow d_1= 0-0=0, d_2 = -2 \dfrac{-n}{2} = n$。
**第三步** 先试 $d_1=0$，设 $s(k)=s_0$，解方程
$$
1 = (k-n) s_0 - k s_0
$$
解得 $s(k) = -\dfrac{1}{n}$。
**第四步** $T(k) = k \left( -\dfrac{1}{n} \right) (-1)^k \mathrm{C}_n^k$，
还可以化简： $T(k) = \dfrac{(-1)^{k+1} k\ n!}{n\ k!\ (n-k)!} = \dfrac{(-1)^{k+1} (n-1)!}{(k-1)! (n-k)!} = (-1)^{k+1} \mathrm{C}_{n-1}^{k-1}$
### 5
**第一步** $\dfrac{t(k+1)}{t(k)} = \dfrac{(k+1)(k-1)}{k(k+2)}, p(k)=k, q(k)=k-1, r(k)=k+1$。
**第二步** $Q(k)=-2, R(k)=2k, d_1=1, d_2=2$。
**第三步** 先试 $d_1=1$，设 $s(k) = s_1 k + s_0$，解方程
$$
k = (k-1)\bigl( s_1 (k+1) + s_0 \bigr) - (k+1)(s_1 k + s_0)
$$
得 $s(k) = -k + \dfrac{1}{2}$。
**第四步** $T(k) = \dfrac{(k+1)(1/2-k)(1/(k^2-1))}{k} = \dfrac{1-2k}{2k(k-1)}$。
这是比直接裂项更简洁的形式。
### 6
**第一步** $p(k)=1, q(k)=k^2-3k+3, r(k)=(k-1)^2=k^2-2k+1$，注意 $q(k)$ 无实根。
**第二步** $Q(k)={\color{blue}{-}}k+2, R(k)={\color{red}{2}}n^2-5k+4$。$d_1=-1, d_2 = -2 \times \dfrac{\color{blue}{-1}}{\color{red}{2}} = 1$。
**第三步** $d_1<0$ 不行，试 $d_2=1$，设 $s(k)=s_1 k + s_0$，解方程
$$
1 = (k^2-3k+3)\bigl( s_1 (k+1) + s_0 \bigr) - (k-1)^2(s_1 k + s_0)
$$
解得 $s(k) = k-1$。
**第四步** $T(k) = \dfrac{(k-1)^2 (k-1) t(k)}{1} = (k-1)^3 t(k)$。