Phantom Bird

外观

Gosper 求和法

约 2550 字大约 9 分钟

mathsstudy-note

2026-1-9

可以当作《具体数学》5.7 节的读书笔记，不过这篇笔记对一些流程给出了更简洁的形式以便记忆。

简要介绍

注意

为了突出代数属性，我们将使用 t(k)t(k) 而非 tkt_k 表示数列。

如果数列 t(k)t(k) 满足 t(k+1)t(k)\dfrac{t(k+1)}{t(k)} 是关于 kk 的有理函数（即两多项式之比），则称 t(k)t(k) 是一个超几何项数列。

Gosper 算法可以对一个超几何项数列 t(k)t(k) 求出另一个超几何项数列 T(k)T(k) 使得 t(k)=T(k+1)−T(k)t(k) = T(k+1) - T(k)，或者报告它不能表示为超几何项。

以下是步骤。我把它放在前面，以便随时温习，第一次看的同学可以直接跳过。

步骤
  1. 将 t(k+1)t(k)\dfrac{t(k+1)}{t(k)} 表示为 p(k+1)p(k)q(k)r(k+1)\dfrac{p(k+1)}{p(k)} \dfrac{q(k)}{r(k+1)}
    使得 q(k)q(k) 的所有因式 (k+α)(k+\alpha) 和 r(k)r(k) 的所有因式 (k+β)(k+\beta) 都满足 α−β∉N∗\alpha-\beta \notin \mathbb{N}^*；
  2. 记 Q(k)=q(k)−r(k),R(k)=q(k)+r(k)Q(k)=q(k)-r(k), R(k)=q(k)+r(k)
    （我们在多数情况只需要它们的次数，当然有时也需要最高次项系数）
    • 令 d=deg⁡(p)−max⁡{deg⁡(Q),deg⁡(R)−1}d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \}；
    • 若 deg⁡(Q)<deg⁡(R)\deg(Q) < \deg(R)，令 d2=−2[kdeg⁡(R)−1]Q[kdeg⁡(R)]Rd_2 = -2 \dfrac{[k^{\deg(R)-1}] Q}{[k^{\deg(R)}] R}，
      若 d2≤dd_2 \le d 则忽略 d2d_2。
  3. 若 d≥0d \ge 0，对 dd 次多项式待定系数解方程 p(k)=q(k)s(k+1)−r(k)s(k)p(k) = q(k)s(k+1) - r(k)s(k)。如果失败，尝试 d2d_2；
  4. T(k)=r(k)s(k)t(k)p(k)T(k) = \dfrac{r(k)s(k)t(k)}{p(k)}。

第一步

步骤

将 t(k+1)t(k)\dfrac{t(k+1)}{t(k)} 表示为 p(k+1)p(k)q(k)r(k+1)\dfrac{p(k+1)}{p(k)} \dfrac{q(k)}{r(k+1)}，其中 p,q,rp,q,r 都是多项式，
使得 q(k)q(k) 的所有因式 (k+α)(k+\alpha) 和 r(k)r(k) 的所有因式 (k+β)(k+\beta) 都满足 α−β∉N∗\alpha-\beta \notin \mathbb{N}^*。

如果没有 α−β∉N∗\alpha - \beta \notin \mathbb{N}^* 的条件，这一步是平凡的。所以我们把重心放在怎么处理冲突（相减为正整数）的因式上。

例子

我们先将分式因式分解好。以 t(k+1)t(k)=2(k+32)(k+4)k(k+12)(k+1)\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+1) 而非 r(k)r(k)，但是如果上下没有相同的因式（如果有请自觉回初中复习约分），冲突的判定仍然是上下因式相减为正整数。

于是它有两对冲突 (k+32),(k+12)\left(k+\frac{3}{2}\right), \left(k+\frac{1}{2}\right) 和 (k+4),(k+1)(k+4), (k+1)。当然还有第三对——(k+4),k(k+4), k，不过我们处理第二对的时候会把 (k+4)(k+4) 处理掉，不需要考虑。

第一对冲突是软“式”子，由于上下差为 11，我们可以把它移到前面去，当作 p(k)p(k)：

t(k+1)t(k)=(k+32)(k+12)2(k+4)k(k+1)\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)}

第一对冲突解决了，我们来看第二对。容易想到在这对苦命鸳鸯中间插入几项：

(k+4)(k+1)=(k+1)(k+2)(k+3)(k+4)(k+1)(k+2)(k+3)(k+4)\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)}}

然后我们惊喜地发现上下因式可以移到前面去了，于是有

t(k+1)t(k)=(k+32)(k+2)(k+3)(k+4)(k+12)(k+1)(k+2)(k+3)2k\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)=(k+12)(k+1)(k+2)(k+3),q(k)=2,r(k)=k−1p(k) = \left(k+\frac{1}{2}\right)(k+1)(k+2)(k+3), q(k)=2, r(k) = k \color{red} -1。

第二步

这应该是最难理解的一步了。实际上这一步的存在是为了辅助第三步的解方程——我们一般不会头铁到直接解，而是在第二步算出它的次数。（当然如果你的注意力够好也可以试试直接解）

为了方便地描述步骤，我们规定一些记号：

记号
  • deg⁡(Q)\deg(Q) 为多项式 QQ 的次数。特别地，deg⁡(0)=−1\deg(0) = -1。
  • [kn]Q[k^n]Q 为多项式 QQ 的 nn 次项系数。
步骤

记 Q(k)=q(k)−r(k),R(k)=q(k)+r(k)Q(k)=q(k)-r(k), R(k)=q(k)+r(k)，分类讨论：

  • 若 deg⁡(Q)≥deg⁡(R)\deg(Q) \ge \deg(R)，令 d=deg⁡(p)−deg⁡(Q)d = \deg(p)-\deg(Q)；

  • 若 deg⁡(Q)<deg⁡(R)\deg(Q) < \deg(R)，令 d=deg⁡(p)−deg⁡(R)+1d = \deg(p) - \deg(R) + 1；

    此时令 d2=−2[kdeg⁡(R)−1]Q[kdeg⁡(R)]Rd_2 = -2 \dfrac{[k^{\deg(R)-1}] Q}{[k^{\deg(R)}] R}，若 d2<dd_2 < d 则忽略 d2d_2。

d2d_2 的情况不常用。对于常用的情况，由于多项式的次数都是整数，我们有一个容易记忆的公式：

d=deg⁡(p)−max⁡{deg⁡(Q),deg⁡(R)−1}d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \}

（如果不信任本人的推导，可以自行验证）

来看两个例子。

例子

p(k)=k,q(k)=α,r(k)=1p(k)=k, q(k)=\alpha, r(k)=1，α\alpha 为参数（这是出题人最爱的差乘比，发现了吗？）

Q(k),R(k)Q(k),R(k) 都是常函数，deg⁡(p)=1,deg⁡(Q)=deg⁡(R)=0\deg(p)=1, \deg(Q)=\deg(R)=0，
于是 d=deg⁡(p)−max⁡{deg⁡(Q),deg⁡(R)−1}=1d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \} = 1。

例子

p(k)=1,q(k)=k2−3k+3,r(k)=k2−2k+1p(k)=1, q(k)=k^2-3k+3, r(k)=k^2-2k+1，此时 Q(k)=−k+2,R(k)=2n2−5k+4Q(k)=-k+2, R(k)=2n^2-5k+4

于是我们有 d=deg⁡(p)−max⁡{deg⁡(Q),deg⁡(R)−1}=−1d = \deg(p) - \max\{ \deg(Q), \deg(R)-1 \} = -1，坏了！

所以 d2d_2 出手了。看看系数（标红的是 deg⁡(R)\deg(R) 次项，标蓝的是 deg⁡(R)−1\deg(R)-1 次项）：

Q(k)=2k2  −1k+2R(k)=2k2−5k+4Q(k) = \phantom{2k^2} \ \, {\color{blue}{-1}}k+2 \\ R(k) = {\color{red}{2}}k^2 - {\color{blue}{5}}k + 4

于是 d2=−2×−12=1d_2 = -2 \times \dfrac{\color{blue}{-1}}{\color{red}{2}} = 1。

第三步、第四步

步骤

若 d≥0d \ge 0，对 dd 次多项式 s(k)s(k) 待定系数解方程

p(k)=q(k)s(k+1)−r(k)s(k)p(k) = q(k)s(k+1) - r(k)s(k)

如果失败，尝试 d2d_2。都失败则无解。

若有解，令 T(k)=r(k)s(k)t(k)p(k)T(k) = \dfrac{r(k)s(k)t(k)}{p(k)} 即可。

没什么技术含量。所以我们下面不给例子，而是回答一个问题：为什么可以这么做？

证明

T(k+1)−T(k)=r(k+1)s(k+1)t(k+1)p(k+1)−r(k)s(k)t(k)p(k)=q(k)s(k+1)t(k)p(k)−r(k)s(k)t(k)p(k)(应用 p,q,r 满足的等式)=q(k)s(k+1)t(k)−r(k)s(k)t(k)q(k)s(k+1)−r(k)s(k)(对分母应用 s 满足的方程)=t(k)(哦，这是极好的)\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 到底是怎么注意到这件事的？

在这里不给出可行性证明，大家可以自行翻阅《具体数学》对应章节。

如何（调戏阅卷人地）写过程

注意到

∑k=1nt(k)=∑k=1nT(k+1)−T(k)=T(n+1)−T(1)\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)T(k+1)-T(k) = t(k) 是你注意到的，别把 Gosper 供出来！

习题

用 Gosper 求和法对 t(k)t(k) 满足

  1. t(k)=k2t(k) = k^2
  2. t(k)=kαk,  α≠1t(k) = k \alpha^k, \ \ \alpha \ne 1
  3. t(k)=k2αk,  α≠1t(k) = k^2 \alpha^k, \ \ \alpha \ne 1
  4. t(k)=(−1)kCnk,  0≤k≤nt(k) = (-1)^k \mathrm{C}_n^k,\ \ 0\le k \le n
  5. t(k)=1k2−1t(k) = \dfrac{1}{k^2-1}
  6. t(k+1)t(k)=k2−3k+3k2\dfrac{t(k+1)}{t(k)} = \dfrac{k^2-3k+3}{k^2}

分别求 T(k)T(k) 使得 t(k)=T(k+1)−t(k)t(k) = T(k+1) - t(k)。

习题解答

1

第一步 t(k+1)t(k)=(k+1)2k2,p(k)=k2,q(k)=r(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\deg(Q)=\deg(R)-1=-1，d=2−(−1)=3d = 2-(-1) = 3，忽略 d2=0d_2 = 0。

第三步 设 s(k)=s3k3+s2k2+s1k+s0s(k) = s_3 k^3 + s_2 k^2 + s_1 k + s_0 解方程

k2=s(k+1)−s(k)=3s3k2+(2s2+3s3)k+s1+s2+s3k^2 = s(k+1)-s(k) = 3 s_3 k^2 + (2s_2 + 3s_3) k + s_1+s_2+s_3

比对系数得 s(k)=13k3−12k2+16k+s0s(k) = \dfrac{1}{3} k^3 - \dfrac{1}{2} k^2 + \dfrac{1}{6} k + s_0。

第四步（实际上可以直接看出来了）

T(k)=(13k3−12k2+16k+s0)k2k2=13k3−12k2+16k+s0T(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)T(k) 是三次的，然后直接待定系数，会更简单。这也说明了 Gosper 算法的特点：流程固定，适合机械操作。

2

第一步 t(k+1)t(k)=k+1kα,p(k)=k,q(k)=α,r(k)=1\dfrac{t(k+1)}{t(k)} = \dfrac{k+1}{k} \alpha, p(k)=k, q(k)=\alpha, r(k)=1。

第二步 α≠1\alpha\ne 1 时，deg⁡(Q)=0,deg⁡(R)−1=−1,d=1−0=1\deg(Q)=0, \deg(R)-1=-1, d = 1-0 = 1。

第三步 设 s(k)=s1k+s0s(k)=s_1 k + s_0，解方程

k=α(s1(k+1)+s0)−(s1k+s0)k = \alpha \bigl( s_1 (k+1) + s_0 \bigr) - (s_1 k + s_0)

得 s(k)=1α−1k−α(α−1)2s(k) = \dfrac{1}{\alpha-1} k - \dfrac{\alpha}{(\alpha-1)^2}。

第四步 T(k)=(1α−1k−α(α−1)2)kαkk=(1α−1k−α(α−1)2)αkT(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

第一步 t(k+1)t(k)=(k+1)2k2α,p(k)=k2,q(k)=α,r(k)=1\dfrac{t(k+1)}{t(k)} = \dfrac{(k+1)^2}{k^2} \alpha, p(k)=k^2, q(k)=\alpha, r(k)=1。

第二步 α≠1\alpha\ne 1 时，deg⁡(Q)=0,deg⁡(R)−1=−1,d=2−0=2\deg(Q)=0, \deg(R)-1=-1, d = 2-0 = 2。

第三步 设 s(k)=s2k2+s1k+s0s(k) = s_2 k^2 + s_1 k + s_0，解方程

k2=α(s2(k+1)2+s1(k+1)+s0)−(s2k2+s1k+s0)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)=1a−1k2−2a(a−1)2k+a(a+1)(a−1)3s(k) = \dfrac{1}{a-1} k^2 - \dfrac{2a}{(a-1)^2} k + \dfrac{a(a+1)}{(a-1)^3}.

第四步 T(k)=(1a−1k2−2a(a−1)2k+a(a+1)(a−1)3)αkT(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

第一步 t(k+1)t(k)=−k!(n−k)!(k+1)!(n−k−1)!=k−nk+1\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)=kp(k)=1, q(k)=k-n, r(k)=k。由于 −n−1<0-n-1 < 0，不存在冲突。

第二步 Q(k)=−n,R(k)=2k−n⟹d1=0−0=0,d2=−2−n2=nQ(k)=-n, R(k)=2k-n \Longrightarrow d_1= 0-0=0, d_2 = -2 \dfrac{-n}{2} = n。

第三步 先试 d1=0d_1=0，设 s(k)=s0s(k)=s_0，解方程

1=(k−n)s0−ks01 = (k-n) s_0 - k s_0

解得 s(k)=−1ns(k) = -\dfrac{1}{n}。

第四步 T(k)=k(−1n)(−1)kCnkT(k) = k \left( -\dfrac{1}{n} \right) (-1)^k \mathrm{C}_n^k，

还可以化简： T(k)=(−1)k+1k n!n k! (n−k)!=(−1)k+1(n−1)!(k−1)!(n−k)!=(−1)k+1Cn−1k−1T(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

第一步 t(k+1)t(k)=(k+1)(k−1)k(k+2),p(k)=k,q(k)=k−1,r(k)=k+1\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,d1=1,d2=2Q(k)=-2, R(k)=2k, d_1=1, d_2=2。

第三步 先试 d1=1d_1=1，设 s(k)=s1k+s0s(k) = s_1 k + s_0，解方程

k=(k−1)(s1(k+1)+s0)−(k+1)(s1k+s0)k = (k-1)\bigl( s_1 (k+1) + s_0 \bigr) - (k+1)(s_1 k + s_0)

得 s(k)=−k+12s(k) = -k + \dfrac{1}{2}。

第四步 T(k)=(k+1)(1/2−k)(1/(k2−1))k=1−2k2k(k−1)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)=k2−3k+3,r(k)=(k−1)2=k2−2k+1p(k)=1, q(k)=k^2-3k+3, r(k)=(k-1)^2=k^2-2k+1，注意 q(k)q(k) 无实根。

第二步 Q(k)=−k+2,R(k)=2n2−5k+4Q(k)={\color{blue}{-}}k+2, R(k)={\color{red}{2}}n^2-5k+4。d1=−1,d2=−2×−12=1d_1=-1, d_2 = -2 \times \dfrac{\color{blue}{-1}}{\color{red}{2}} = 1。

第三步 d1<0d_1<0 不行，试 d2=1d_2=1，设 s(k)=s1k+s0s(k)=s_1 k + s_0，解方程

1=(k2−3k+3)(s1(k+1)+s0)−(k−1)2(s1k+s0)1 = (k^2-3k+3)\bigl( s_1 (k+1) + s_0 \bigr) - (k-1)^2(s_1 k + s_0)

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

第四步 T(k)=(k−1)2(k−1)t(k)1=(k−1)3t(k)T(k) = \dfrac{(k-1)^2 (k-1) t(k)}{1} = (k-1)^3 t(k)。

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)