type
status
date
slug
summary
tags
category
icon
password
在一切开始之前——
零音想强烈谴责 Notion！什么年代了，还不支持行内 LaTeX 公式。
给定下面这个数列
如果我们需要求出它的前 n 项和的表达式，使用常规的裂项方法过程如下
这种裂项看起来简单明了，但实际上，并不是每个人都能在极短的时间内发现该裂项规律。如何将这种严重依赖注意力的裂项题目变得机械化？我们今天引入的 Gosper Algorithm 就是为了解决这个问题！
Gosper Algorithm 是由计算机科学家 R. William Gosper 于 1978 年提出的。当时，他正在研究符号计算（symbolic computation），这是计算机数学领域的重要分支，研究如何用算法解决代数、数论和离散数学中的问题。Gosper 是 MIT 人工智能实验室 的一员，喜欢用编程去解数学问题。受计算机代数系统（比如 Macsyma，一个早期的符号计算工具）的启发，他试图构造一种算法，用于自动化复杂的级数求和过程——这就是 Gosper Algorithm 的起点！
接下来，我们将会使用 Gosper Algorithm 重做上述题目，去感受数学机械化的魅力。
这篇文章仅涉及 Gosper Algorithm 运算方法的更通俗易懂的解释，而不包括其背后的原理。如果你对 Gosper Algorithm 的具体原理感兴趣，请参阅其他视频或书籍。
得到 p(k)，q(k) 和 r(k)
设
首先，我们需要计算出
接下来，我们需要将 f(k+1)/f(k) 拆解为 [p(k+1)/p(k)]·[q(k)r(k+1)] 的形式。需要注意的是，这里的 p(k)，q(k) 和 r(k) 应当类比为关于 k 的函数，而不是变量 p 或 q 或 r 与变量 k 的简单乘积。
为了得到 q(k) 和 r(k)，我们首先需要得到 p(k)。但 p(k) 应当满足什么样的条件呢？简单来说，当我们确定了一个满足条件的 p(k) 并以此得到了 q(k) 和 r(k) 时，q(k) 所有一次的因式分解项 k+α 和 r(k) 所有一次的因式分解项 k+β 应当满足，任意一个 α 减去任意一个 β 的结果都不是正自然数。
有点懵了吗？别急。我们仍然用上面的示例演示一下。在得到 p(k) 的过程中，我们首先尝试 p(k) = 1，此时亦有 p(k+1) = 1。将所有计算得到的值全部代入 f(k+1)/f(k) = [p(k+1)/p(k)]·[q(k)r(k+1)]，我们有
接下来，利用 r(k+1) 得到 r(k)=k^3-1。我们需要对二者进行因式分解。我们都学过立方差公式和立方和公式
但是这两个公式只能将立方差或立方和分解到 k^2±k+1，这还达不到我们所要求分解到的 k+α 和 k+β。怎么办呢？引入复数，继续分解！
至此，我们得到了最终分解的结果。写出所有的 α 和 β，我们有
现在让我们回顾一下 p(k) 的要求。
当我们确定了一个满足条件的 p(k) 并以此得到了 q(k) 和 r(k) 时，q(k) 所有因式分解项 k+α 和 r(k) 所有因式分解项 k+β 应当满足，任意一个 α 减去任意一个 β 的结果都不是正自然数。
我们不难发现
也就是说，对于 p(k) 的第一次尝试 p(k)=1 并不符合要求！运气好的朋友做题，第一次尝试 p(k)=1 时，或许直接就符合要求了，你便可以将这时的 p(k)，q(k) 和 r(k) 代入到下一步计算。但我们这里尝试的示例恰好没有符合要求，于是我们需要继续寻找满足要求的 p(k)。
如何寻找到满足要求的 p(k) 呢？一般来说，我们通过这样的方法得到新的 p(k)
也就是说，用原来的 p(k)，从 k+β+1 开始与它相乘，直到 k+α-1 停止。有朋友或许会问，如果找到了不止一组的 α 和 β 使得它们作差结果是正自然数该怎么办？很简单，一组一组地迭代即可，直到把所有这样的 α 和 β 全部处理完毕。
在本例中，由于只有 1 组这样的 α 和 β，我们只需要处理一次即可。注意到 k+β+1=k+α-1，说到底其实只需要 k 和原先的 p(k) 相乘即可。我们可以得到这样的新的 p(k)
接下来仿照上面的步骤，计算出 q(k) 和 r(k+1)，再由后者得到 r(k) 即可。具体的计算过程概不赘述。我们可以得到以下的 q(k) 和 r(k)
利用指标 d 判断裂项可行性
首先设
记 d_P，d_Q 和 d_R 分别为 P(k)，Q(k) 和 R(k) 的最高次数。（例如，一个二次函数的最高次数就是 2，一个一次函数的最高次数就是 1）本例中，d_P=1，d_Q=1，d_R=2。我们需要用上面这些数据计算出指标 d，判断裂项的可行性。d 的计算方法如下
一般地，若 d<0，则说明该裂项不能使用 Gosper Algorithm 进行。若 d>0，则说明该裂项应当可以使用 Gosper Algorithm 进行。本例中，d_Q<d_R，因此计算 d 得
构造 k 的 d 次多项式 s(k)
做到这一步基本上已经接近尾声了！现在，我们需要找到一个满足 Gosper 方程的 s(k)，它是一个 k 的 d 次多项式。怎么办呢？我们可以使用待定系数法。本例中，d=0，所以很幸运，s(k) 是一个常数，设它为 b。Gosper 方程如下所示
我们将结果全部代入 Gosper 方程，有
计算 T(k) 并得到最终的裂项结果
我们再将上面的结果代入 T(k) 的计算式中
再使用 T(k) 计算得到 T(k+1)
大功告成。现在，我们有 f(k)=T(k+1)-T(k)，也就是
化简后，我们就得到了最终的裂项结果！
- 作者:零音LyRin-owo
- 链接:https://crystal.lyrin-owo.top/learning/1532a20b-af5f-80a6-87ef-d4bbbb908d8d
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
