Gosper 算法（一）

差分数组

如果 $f(k)$ 是 $g(k)$ 的差分数组，即 $f(k) = \Delta g(k) = g(k+1) - g(k)$
记 $\sum f(k) \delta k = g(k) + C$ ，差分数组的前缀和等于原数组

$\displaystyle \sum_{i = a}^{b} f(k)\delta k = g(k) \mid_{a}^{b} = g(b) - g(a)$

比如 $\displaystyle \sum_{k < m} \binom{n}{k}(-1)^k = (-1)^{m-1} \binom{n-1}{m-1}$

实际上等于差分求和 $\displaystyle \sum\binom{n}{k}(-1)^k \delta k = (-1)^{k-1}\binom{n-1}{k-1} +C$

写成差分公式，就是

$\displaystyle \Delta\left( (-1)^k \binom{n}{k} \right) = (-1)^{k+1} \binom{n}{k+1} - (-1)^k \binom{n}{k} = (-1)^{k+1} \binom{n+1}{k+1}$

超几何函数求和

$\displaystyle F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = \sum_{k \geqslant 1} \frac{a_1^{\overline{k}} \cdots a_m^{\overline{k}} }{ b_1^{\overline{k}} \cdots b_n^{\overline{k}} } \cdot \frac{z^{k}}{k!}$

将超几何函数看成是关于 $k$ 的而不是关于 $z$ 的

$\displaystyle \sum F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right)_k \delta k = c\displaystyle F\left(\begin{gathered} A_1, \cdots, A_m \\ B_1, \cdots, B_n \end{gathered} \middle| \ Z\right)_k + C$

Gosper 算法执行流程

第一步

具体思想，构造法

容易发现 $\displaystyle \frac{t(k+1)}{t(k)} = \frac{k}{k+1} A(), A()$ 为多项式

观察超几何项，不难发现，可以写成

$\displaystyle \frac{t(k+1)}{t(k)} = \frac{p(k+1)}{p(k)} \frac{r(k)}{r(k+1)}$

其中 $r(k)$ 中含有因子 $(k+b)$ ， $q(k)$ 中含有因子 $(k+a)$

将 $r(k)$ 与 $p(k)$ 约化，可以写成 $\displaystyle \frac{p(k+1)}{p(k)} \cdot \frac{q(k)}{r(k+1)} \quad \textbf{(1)}$

其中必须满足 $(k+a) \mid q(k), (k+b) \mid r(k)$ ，并且

$a - b$ 不是正整数 $\textbf{(1)}$

如果不满足要怎么做？假设 $a-b = N > 0$
考虑到 $r(k)$ 中含有因子 $(k+b)$ ，并且 $r(k+1)$ 中含有因子 $(k+b+1)$

$\displaystyle \frac{p(k+1)}{p(k)} = \frac{(k+a)}{(k+b+1)} \cdot A()$ ，可以同时划归

由此 $\displaystyle \frac{p(k+1)}{p(k)} = \displaystyle \frac{(k+a)\textcolor{red}{(k+a-1) \cdots (k+b+2)}}{\textcolor{red}{ (k+a-1)\cdots (k+b+2)} (k+b+1) }$

红色部分恰好相等，也就是说，可以用

$\displaystyle p(k) \leftarrow p(k)(k+a-1)^{\underline{N-1}} = p(k)(k+a-1)(k+a-2) \cdots (k+b+1)$
来代替 $p(k)$

算法第一步就是将超几何函数写成满足 $\textbf{(1)}$ 的形式

第二步

将原来的超几何项 $t(k)$ 看作是差分数组
求一个超几何项 $T(k)$ 使得 $t(k) = T(k+1) - T(k)$

将未知函数 $T(k)$ 写成

$\displaystyle T(k) = \frac{r(k)s(k)t(k)}{p(k)} \quad \textbf{(2)}$

至于为什么要写成这种形式

不妨看 $\displaystyle t(k+1) = \frac{p(k+1)}{p(k)} \cdot \frac{q(k)}{r(k+1)} \cdot t(k)$

原数组肯定有形式 $T(k) = F(k)t(k)$ ，代入 $t(k) = T(k+1) - T(k)$

从而 $\displaystyle t(k) = \left(F(k+1) \frac{p(k+1)}{p(k)} \frac{q(k)}{r(k+1)} - F(k)\right)t(k)$

令 $\displaystyle F(k+1) = s(k+1)\frac{r(k+1)}{p(k+1)}$

从而 $\displaystyle T(k) = \frac{r(k)s(k)t(k)}{p(k)}$

其中 $s(k)$ 必须用某种方法来发现
将其带入差分就可以发现

$\displaystyle t(k) = \frac{r(k+1)s(k+1)t(k+1)}{p(k+1)} - \frac{r(k)s(k)t(k)}{p(k)}$

由于 $\displaystyle t(k+1) = \frac{p(k+1)q(k)}{p(k)r(k+1)}\cdot t(k)$

从而 $t(k) = \displaystyle \frac{q(k)s(k+1)t(k)}{p(k)} - \frac{r(k)s(k)t(k)}{p(k)}$

由此有一个重要的递归关系

$\displaystyle p(k) = q(k)s(k+1) - r(k)s(k) \quad \textbf{(3)}$

如果能够找到 $s(k)$ ，那么就找到了 $T(k) = \sum t(k)\delta k$ ，否则找不到 $T$

下面证明 $s(k)$ 为一个多项式
$s(k) = f(k)/g(k)$ ，如果 $g(k)$ 不是常数，并且 $f(k), g(k)$ 之间没有公共因子
不妨设 $g(k)$ 的因子为 $(k + \beta), (k+\beta + N-1)$
其中我们令 $N$ 是使得 $(k+\beta + N-1)$ 作为 $g(k)$ 因子出现的最大整数，因为 $N = 1$ 总满足条件
所以对于一个数 $\beta$ ，我们总可以尝试找到这样的 $N$
由此方程 $\textbf{(3)}$ 可以改写成
$\displaystyle p(k)g(k+1)g(k) = q(k)f(k+1)g(k)-r(k)g(k+1)f(k)$

根据上面的假设，我们有 $k = -\beta, k = 1-\beta - N$ 时， $g(-\beta) = 0, \ g(1-\beta - N) = 0$
由此我们可以取 $k = -\beta, \ k = -\beta - N$
$\displaystyle r(-\beta)g(1-\beta)f(-\beta) = 0 = q(-\beta - N) f(1-\beta - N)g(-\beta - N)$

根据最先的归纳假设， $f(k)$ 并不含有 $(k +\beta), (k + \beta + N-1)$ 这个公共因子
所以 $f(-\beta) \neq 0, f(1- \beta -N) \neq 0$
又因为之前我们假设 $N$ 是 最大的使得 $(k+\beta + N-1)$ 为 $g(k)$ 因子的项
所以 $k_{\min} = 1-N-\beta$ 使得 $k$ 为 $g(k) = 0$ 的根
换句话说， $g(1-\beta) \neq 0, \ g(-\beta - N) \neq 0$
从而有 $r(-\beta) = q(-\beta - N) = 0$

回顾条件 $\textbf{(1)}$ ，我们构造的时候是令 $(k + \alpha) \mid q(k), \ (k+\beta) \mid r(k)$
并且 $\alpha - \beta$ 不是正整数
那么当 $r(-\beta) = 0$ 说明 $(k+\beta) \mid r(k), (k + \beta + N) \mid q(k)$
如果我们取 $\alpha = \beta + N$ ， $\beta = \beta$ ，那么就违背了算法假定条件，得出矛盾
所以 $s(k)$ 一定是多项式

如果已知 $s(k)$ 的次数是 $d$ ，那么很容易可以有
$s(k) = \displaystyle \alpha_d k^d + \alpha_{d-1} k^{d-1} + \cdots + \alpha_0, \quad \alpha_d \neq 0$
将表达式代入 $\textbf{(3)}$ 中，让 $k$ 的对应幂指相等即可得到线性方程求解

问题了来了，如何确定 $s(k)$ 的次数

$\displaystyle p(k) = q(k)s(k+1) - r(k)s(k) + q(k)s(k) - q(k)s(k)$
$\displaystyle p(k) = -r(k)s(k+1) + r(k)s(k+1) + q(k)s(k+1) - r(k)s(k)$

$\displaystyle 2p(k) = Q(k)\left(s(k+1)+s(k) \right) + R(k) \left(s(k+1)-s(k) \right) \quad \textbf{(4)}$
$Q(k) = q(k) - r(k), \quad R(k) = q(k) + r(k)$

注意到如果 $s(k)$ 次数为 $d$ ，那么 $s(k+1) + s(k) = 2\alpha_d k^d + \cdots$ 次数也是 $d$
差分 $s(k+1) - s(k) = \Delta s(k) = d\alpha_d k^{d-1} + \cdots$ 次数为 $d-1$ ，用 $\text{deg}$ 表示多项式次数
如果 $\text{deg}(Q) \geqslant \text{deg}(R)$ ，那么 $\textbf{(4)}$ 右边次数是 $\text{deg}(Q) + d$
此时 $d = \text{deg}(p) - \text{deg}(Q)$

如果 $\text{deg}(Q) < \text{deg}(R) = d'$ ，那么可以有形式
$R(k) = \lambda k^{d'} + \cdots \quad \lambda \neq 0$
$Q(k) = \lambda' k^{d'-1} + \cdots$
代入 $\textbf{(4)}$ 中，我们有
$\displaystyle (2\lambda' \alpha_d + \lambda d \alpha_d) k^{d+d'-1} + \cdots$
分类讨论如下，注意到这里我们令 $d' = \text{deg}(R)$ ， $\text{deg}(p) \leqslant d + \text{deg}(R) - 1$

$2\lambda' + \lambda d \neq 0$ 且 $d = \text{deg}(p) - \text{deg}(R)+1$
$2\lambda' + \lambda d = 0$ 且 $d > \text{deg}(p) - \text{deg}(R) + 1$ ，当且仅当 $d = -2\lambda' / \lambda$ 并且
$-2\lambda' / \lambda > \text{deg}(p) - \text{deg}(R) + 1$

第二种情形只有在 $-2\lambda' / \lambda > \text{deg}(p) - \text{deg}(R) + 1$ 时才需要核查

一些例子

$\displaystyle \sum \binom{n}{k}(-1)^k \delta k$ 的封闭形式

$t(k) = \displaystyle \binom{n}{k} (-1)^k = \frac{n!(-1)^k}{k!(n-k)!}$

第一步，划归
可以将比值表示成我们想要的形式，根据 $\textbf{(1)}$

$\displaystyle \frac{t(k+1)}{t(k)} = \frac{k-n}{k+1} = \frac{p(k+1)}{p(k)} \frac{q(k)}{r(k+1)}$

可以直接取 $p(k) = 1, q(k) = k-n, r(k) = k$ ，这样是可以满足 $q(k) / r(k)$ 没有 $d > 0$ 的关于 $k$ 的因子 $k^d$

第二步，根据 $\textbf{(4)}$
$Q(k) = q(k) - r(k), R(k) = q(k) + r(k)$
可以得到 $Q(k) = -n, R(k) = 2k - n$ ，我们先尝试 $d = \text{deg}(p) - \text{deg}(R) + 1 = 0-1+1 = 0$
也就是说，此时 $s(k)$ 最高次是 $0$ 次，此时 $s(k) = \alpha_0$