Gosper 算法（二）

算法思想，将求和项看作 $n$ 和 $k$ 的一个函数 $t(n, k)$

基本思想

$\displaystyle t(n, k) = \binom{n}{k} z^k$，考虑一个更加一般的项

$\displaystyle \hat{t}(n, k) = \beta_0(n) t(n, k) + \beta_1(n) t(n+1, k) \quad \textbf{(1)}$

首先将 $n$ 看作变量

$\displaystyle \frac{t(n+1, k)}{t(n, k)} = \frac{n+1}{n+1-k}$，代入 $\textbf{(1)}$ 中

$\hat{t}(n, k) = \displaystyle p(n, k)\frac{t(n, k)}{n+1-k} \quad \textbf{(1.0)}$，其中

$p(n, k) = (n+1-k) \beta_0(n) + (n+1) \beta_1(n) \quad \textbf{(1.1)}$

下面对 $\hat{t}(n, k)$ 应用 Gosper 算法，对 $k$ 应用算法

$\displaystyle \frac{\hat{t}(n, k+1)}{\hat{t}(n, k)} = \frac{\hat{p}(n, k+1)}{\hat{p}(n, k)} \frac{q(n, k)}{r(n, k+1)} \quad \textbf{(2)}$

一般来说，在 Gosper 中我们令 $\hat{p}(n, k) = 1$，但是在 Zeilberger 推广中

令 $\hat{p}(n, k) = p(n, k)$，令 $\displaystyle \overline{t}(n, k) = \frac{\hat{t}(n, k)} { p(n, k) }, \ \overline{p}(n, k) = \frac{\hat{p}(n, k)} { p(n, k) }$

这样，就可以得到如下表达式

$\displaystyle \frac{\overline{t}(n, k+1)}{\overline{t}(n, k)} = \frac{\overline{p}(n, k+1)}{\overline{p}(n, k)} \frac{q(n, k)}{r(n, k+1)} \quad \textbf{(3)}$

这样我们就可以令 $\overline{p}(n, k) = 1$

我们令 $\displaystyle \overline{t}(n, k) = \hat{t}(n, k) / p(n, k)$，而 $\displaystyle\hat{t}(n, k) = p(n, k) \frac{t(n, k)}{n+1-k}$，从而

$\displaystyle \overline{t}(n, k) = \frac{t(n, k)}{n+1-k} = \frac{n!z^k}{(n+1-k)!k!}$，所以

$\displaystyle \frac{\overline{t}(n, k+1)}{\overline{t}(n, k)} = \frac{(n+1-k)z}{k+1}$

根据 Gosper 算法，可以令 $q(n, k) = (n+1-k)z, \quad r(n, k) = k$，并且 $q/r$ 没有关于 $k$ 的 $\geqslant 1$ 的因子
满足算法条件，可以直接用 Gosper 算法求解

接下来关于 $k$ 执行 Gosper 算法第二步

$\displaystyle \hat{p}(n, k) = q(n, k)s(n, k+1) - r(n, k) s(n, k) \quad \textbf{(4)}$
其中 $s(n, k) = \alpha_d(n) k^d + \alpha_{d-1}(n)k^{d-1} + \cdots + \alpha_0(n)$ 是一个待定多项式

将例子中给出的 $q, r$ 代入 $\textbf{(4)}$ 和 $\textbf{(1.1)}$

$\displaystyle (n+1-k)\beta_0(n) + (n+1) \beta_1(n) = (n+1-k)z s(n, k+1) - ks(n, k)$

看作关于 $k$ 的方程，通过考虑 $Q(n, k) = q(n, k) - r(n, k), \quad R(n, k) = q(n, k) + r(n, k)$ 确定次数 $d$
$\text{deg}(\hat{p}) = \text{deg}(Q) = \text{deg}(R) = 1$
由此我们有 $d = \text{deg}(\hat{p}) - \text{deg}(Q) = 0$，$s(n, k) = \alpha_0(n)$ 与 $k$ 无关

方程写成
$(n+1-k)\beta_0(n) + (n+1) \beta_1(n) = (n+1-k) z\alpha_0(n) - k\alpha_0(n)$

让两边关于 $k$ 的幂相等

$$\begin{cases} (n+1)\beta_0(n) + (n+1)\beta_1(n) - (n+1)z\alpha_0(n) = 0 \\ -\beta_0(n) + (z+1)\alpha_0(n) = 0 \end{cases}$$

因此满足条件的是

$\displaystyle \beta_0(n) = z+1, \quad \beta_1(n) = -1, \quad \alpha_0(n) = s(n, k) = 1$

综上所述

$\hat{t}(n, k) = T(n, k+1) - T(n, k) \quad \textbf{(5)}$
其中根据 Gosper 算法的推广

$T(n, k) = \displaystyle \frac{r(n, k)s(n, k)\hat{t}(n, k)}{\hat{p}(n, k)} = r(n, k) s(n, k) \overline{t}(n, k)$

最后一步是因为
$\hat{t}(n, k) = \overline{t}(n, k) p(n, k)$，因为 $\overline{p}(n, k) = 1$，所以 $\displaystyle \frac{p(n, k)}{\hat{p}(n, k)} = \overline{p}(n, k) = 1$

根据 $\textbf{(1.0)}$，$\displaystyle \overline{t}(n, k) = \frac{\hat{t}(n, k)}{p(n, k)} = \frac{t(n, k)}{n+1-k}$

$T(n, k) = \displaystyle \frac{k}{n+1-k}t(n, k) = \frac{k}{n+1-k} \binom{n}{k} z^k = \binom{n}{k-1}z^k$

根据 $\textbf{(1)}$ 和 $\textbf{(5)}$ 容易验证

$\displaystyle (z+1)\binom{n}{k}z^k - \binom{n+1}{k}z^k = \binom{n}{k}z^{k+1} - \binom{n}{k-1}z^k$

当 $n$ 是任意整数时，仅有限多个 $k$ 值不等于 $0$，这样 $T(n, k+1)-T(n, k)$ 对所有 $k$ 求和缩减为 $0$

$\displaystyle \sum \hat{t}(n, k) = 0$

$\displaystyle \sum_k \left((z+1)t(n, k) - t(n+1, k) \right) = 0$

这个求和就是
$(z+1)S_n - S_{n+1} = 0$，从而 $S_{n+1} = (z+1)S_n$，$S_0 = 1$，那么有 $S_n = (z+1)^n$

Gosper-Zeilberger 算法

• 令 $l = 0$，求关于 $n$ 的 $l$ 阶递归式

• 先将通项 $t(n, k)$ 看作是关于 $n$ 的，求 $\displaystyle \frac{t(n+1, k)}{t(n, k)} \cdots$，代入

  $\displaystyle \hat{t}(n, k) = \beta_0(n) t(n, k) + \cdots + \beta_l(n)t(n+l, k)$，可以求出一个线性组合

  一般是令 $\displaystyle\overline{t}(n, k) = \frac{t(n, k)}{A(n, k)}$，$A(n, k)$ 是通分之后的分母

  从而有 $\hat{t}(n, k) = p(n, k) \overline{t}(n, k)$，其中 $\overline{t}(n, k)$ 是关于 $k$ 的超几何项

  一般来说，线性组合通分之后，分子表达式一般有形式 $p(n, k) = B(n, k) = \hat{p}(n, k)$

• 根据得到的 $\overline{t}(n, k)$，看作 $k$ 的超几何项

  根据 $\displaystyle \frac{\overline{t}(n, k+1)}{\overline{t}(n, k)} = \frac{\overline{p}(n, k+1)}{\overline{p}(n, k)} \frac{q(n, k)}{r(n, k+1)}$

  通常我们有 $\overline{p}(n, k) = 1$，从而可以求出 $q(n, k), r(n, k)$，此时 $\hat{p}(n, k) = p(n, k) \overline{p}(n, k)$

• 令 $d_Q = \text{deg}(q-r), \ d_R = \text{deg}(q+r)$

  $\displaystyle d = \begin{cases} \text{deg}(\hat{p}) - d_Q & d_Q \geqslant d_R \\ \text{deg}(\hat{p}) - d_R + 1 & d_Q < d_R \end{cases}$

• 如果 $d \geqslant 0$，那么用 $s(n, k) = \alpha_d(n) k^d + \alpha_{d-1}(n)k^{d-1} + \cdots + \alpha_0(n)$ 待定 $s(n, k)$
  并且代入方程，（其中 $\hat{p}(n, k)$ 在第二步中求出来了）
  $\displaystyle \hat{p}(n, k) = q(n, k)s(n, k+1) - r(n, k) s(n, k)$
  代入方程之后，令 $k$ 的幂对应的系数相等可以得到 $\beta_0, \beta_1, \cdots, \beta_l$
  如果这些关于 $\beta$ 的解不全为 $0$，$\text{return true}$

• 否则的话，当 $d_Q < d_R$ 并且 $-2\lambda' / \lambda$ 是一个 $> d$ 的整数时
  （注意到 $\lambda$ 是 $q+r$ 中 $k^{d_R}$ 的系数，$\lambda'$ 是 $q-r$ 中 $k^{d_R - 1}$ 的系数）
  令 $d = -2\lambda' / \lambda$ 并且重复上一步
  如果不满足这一步一开始时的条件，$\text{return false}$

• 如果 $\text{false}$，那么将 $l += 1$，从第一步开始再尝试

• 如果 $\text{true}$，那么令

  $\displaystyle T(n, k) = \frac{r(n, k)s(n,k)\overline{t}(n, k)}{\overline{p}(n, k)}$，并且 $\hat{t}(n, k) = T(n, k+1)-T(n, k)$

一些例子

具体数学习题 5.94

求 $\displaystyle \sum \binom{a}{k} \binom{-a}{n-k} \delta k$ 的封闭形式

第一步
不难推出

$\displaystyle \frac{t(k+1)}{t(k)} = \frac{(k-a)(k-n)}{(k+1)(k-n-a+1)}$

令 $p(k) = 1$
$r(k) = k(k-n-a), \ q(k) = (k-a)(k-n)$

第二步
划归之后有 $\displaystyle Q(k) = q(k) - r(k) = an, \quad R(k) = q(k)+r(k) = 2k^2 - 2(a+n)k + an$
$\text{deg}(R) = 2, \text{deg}(Q) = 0$

$d = \text{deg}(p) - \text{deg}(R) + 1 = 0-2+1 = -1$，这里需要额外检查

$R(k) = 2k^2 + \cdots$，由此 $\lambda = 2$
$Q(k) = 0\cdot k^{1} + \cdots$，由此 $\lambda' = 0$

$-2\lambda' / \lambda > \text{deg}(p) - \text{deg}(R) + 1$，转为 Gosper 算法第二种情形
$2\lambda' + \lambda d = 0$，则 $s(k)$ 次数 $d = 0$

第三步

$s(k) = \alpha_0$ 代入 $p(k) = q(k)s(k+1) - r(k)s(k)$，从而

$1 = (k-a)(k-n)\alpha_0 - k(k-n-a)\alpha_0 = an \cdot \alpha_0$

$s(k) = \displaystyle \frac{1}{an}$

第四步

$T(k) = \displaystyle \frac{r(k)s(k)t(k)}{p(k)} = k(k-n-a) \frac{1}{an} \binom{a}{k} \binom{-a}{n-k}$

$T(k) = \displaystyle \binom{a-1}{k-1} \frac{k-n-a}{n} \binom{-a}{n-k} = \binom{a-1}{k-1} \textcolor{blue}{ \frac{k-n-a}{n} \frac{(-a)^{\underline{n-k}}}{(n-k)!} }$

化简蓝色部分，$(-1) \cdot \displaystyle \frac{(-a)^{\underline{n-k}}}{(n-k)!} \frac{a+n-k}{n}$

$\displaystyle (-1) \frac{(-a)(-a-1)\cdots (-a-n+k+1)}{(n-k)!} \frac{a+n-k}{n}$

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

$\displaystyle = (-1)^{n-k+1}(-1)^{n-k} \binom{-a-1}{n-k} \frac{a}{n} = (-1) \binom{-a-1}{n-k} \frac{a}{n}$

由此 Gosper 求出答案为

$\displaystyle T(k) = -\binom{a-1}{k-1}\binom{-a-1}{n-k} \frac{a}{n} + C$

当 $m \geqslant 0$ 是一个小于 $n$ 的整数的时候

$\displaystyle\binom{m-a}{n-k} \delta k \Rightarrow (1+k)^m (1+k)^{-a}$ 关于 $k$ 的二项式生成函数

从而

$\displaystyle \sum \binom{a}{k} \binom{m-a}{n-k} \delta k = \sum_j\binom{m}{j} \cdot \binom{a}{k}\binom{-a}{n-j-k}$

$\displaystyle \quad = \sum_j \binom{m}{j} \frac{-a}{n-j} \binom{a-1}{k-1} \binom{-a-1}{n-j-k} + C$

一些例子2

$\displaystyle \sum_k \binom{m-r+s}{k} \binom{n+r-s}{n-k} \binom{r+k}{m+n} = \binom{r}{m}\binom{s}{n}$

作变换 $\displaystyle m = b+d, n = a, r = a+b+c+d, s = a+b+c$，可以将原式写成更为对称的形式

$\displaystyle \sum_k = \frac{(a+b+c+d+k)!}{(a-k)!(b-k)!(c+k)!(d+k)!k!} = \frac{(a+b+c+d)!(a+b+c)!(a+b+d)!}{a!b!(a+c)!(a+d)!(b+c)!(b+d)!}$

这样可以考虑 Gosper 算法的标准流程，取 $n = a$

$\displaystyle t(n, k) = \frac{(n+b+c+d+k)!}{(n-k)!(b-k)!(c+k)!(d+k)!k!}$

$\displaystyle p(n, k) = \hat{p}(n, k) = (n+1-k)\beta_0(n) + (n+1+b+c+d+k)\beta_1(n)$

$\displaystyle \overline{t}(n, k) = \frac{t(n, k)}{n+1-k} = \frac{(n+1+b+c+d+k)!}{(n+1-k)!(b-k)!(c+k)!(d+k)!k!}$

$\displaystyle q(n, k) = (n+b+c+d+k+1)(n+1-k)(b-k)$

$\displaystyle r(n, k) = (c+k)(d+k)k$

注意到 $\text{deg}(q-r) < \text{deg}(q+r)$，但是 $\text{deg}(\hat{p}) = 1, \text{deg}(q+r) = 3$
$\text{deg}(\hat{p}) - \text{deg}(q+r) + 1 = -1$，但是注意到还需要判 $-2\lambda' / \lambda$

$q+r = 2k^3 + \cdots$，从而 $\lambda = 2$
$q-r = 0k^2 + \cdots$，从而 $\lambda' = 0$
此时我们取 $d = -2\lambda' / \lambda = 0$，即 $s(n, k) = \alpha_0(n)$

最后我们考虑关于 $k$ 的方程幂次相等

$\displaystyle (n+1-k)\beta_0(n) + (n+b+c+d+k+1)\beta_1(n)$
$\quad = (n+b+c+d+k+1)(n+1-k)(b-k)\cdot\alpha_0(n) - (c+k)(d+k)k \cdot \alpha_0(n)$

$$\begin{cases} (n+1)\beta_0(n) + (n+1+b+c+d)\beta_1(n) - (n+1)(n+b+c+d+1)b\alpha_0(n) = 0 \\ -\beta_0(n) + \beta_1(n) - \left((n+1)b - (n+1+b)(n+b+c+d+1)-cd \right) \alpha_0(n) = 0 \end{cases}$$

将 $\beta_0(n) = \beta_1(n) - \cdots$ 代入第一个方程即可求解

$\alpha_0(n) = 2n + 2 + b + c +d$
$\beta_1(n) = -(n+1)(n+1+c)(n+1+d)$

$\beta_0(n)$ 的推导比较复杂，先令 $n+1 = t$

$\beta_0(n) = -t(t+c)(t+d)$
$\ \textcolor{red}{- tb((t+b+c+d+t) + (t+b)(t+b+c+d)(t+b+c+d+t) + cd(t+b+c+d+t))}$
红色部分化简成
$(t+b+c+d+t)((t+b+c)(t+b+d) - tb)$
原式就化为
$(t+b+c)(t+b+d)(2t+b+c+d)-tb(t+c)-tb(t+d)-tb\cdot b - t(t+c)(t+d)$

综上所述
$\beta_0(n) = (n+1+b+c)(n+1+b+d)(n+1+b+c+d)$

我们得出递推结论

$\beta_0(n)t(n, k) + \beta_1(n)t(n+1, k)$ 是可以关于 $k$ 求和的

即 $(n+1+b+c)(n+1+b+d)(n+1+b+c+d)S_n - (n+1)(n+1+c)(n+1+d)S_{n+1} = 0$

$\displaystyle \frac{S_n}{S_{n-1}} = \frac{(n+b+c)(n+b+d)(n+b+c+d)}{n(n+c)(n+d)}$

$\displaystyle \frac{S_n}{S_0} = \frac{(n+b+c)^{\underline{n}} (n+b+d)^{\underline{n}} (n+b+c+d)^{\underline{n}} }{n!(n+c)^{\underline{n}} (n+d)^{\underline{n}}}$

$\displaystyle \frac{S_n}{S_0} = \frac{(n+b+c)!(n+b+d)!(n+b+c+d)!c!d!}{(b+c)!(b+d)!(b+c+d)!(n+c)!(n+d)!n!}$

因为 $\displaystyle S_0 = \binom{n+r-s}{n}\binom{r}{m+n} = \frac{(b+c+d)!}{a!b!c!d!}$

该问题证毕

一些例子3

同例2，只是这里令 $n = d$ 入手，那么表达式变成了

$\displaystyle t(n, k) = \frac{(n+a+b+c+k)!}{(n+k)!(c+k)!(a-k)!(b-k)!k!}$

同上分析，代换之后

$[k]:\displaystyle \beta_0(n) + \beta_1(n) = (ab - (n+1)c - (a+b)(n+a+b+c+1)) \alpha_0(n)$
$[k^0]: \displaystyle (n+1)\beta_0(n) + (n+a+b+c+1)\beta_1(n) = (n+a+b+c+1)ab \cdot \alpha_0(n)$

$\displaystyle (a+b+c)\beta_1(n)$
$\quad = \left((n+a+b+c+1)ab - (n+1)(ab-(n+1)c-(a+b)(n+a+b+c+1)) \right) \cdot \alpha_0(n)$

考虑到两边关于 $n$ 的系数

$[n^2]: (a+b+c)\alpha_0(n)$
$[n]: (a+b+c)(a+b+2)\alpha_0(n)$
$[n^0]: (a+b+c)(ab+1+a+b)\alpha_0(n)$

从而令 $\alpha_0(n) = -1$，那么有 $\beta_1(n) = -(n+a+1)(n+b+1)$
$\beta_0(n) = (n+1+a+b+c)(n+1+a+b)$

注意到表达式

$\displaystyle t(n, k) = \frac{(n+a+b+c+k)!}{(n+k)!(c+k)!(a-k)!(b-k)!k!}$

$\displaystyle \begin{cases}a-k \geqslant 0 \\ n+k \geqslant 0\end{cases}$，我们有 $\displaystyle \begin{cases} k \leqslant a \\ k \geqslant -n \end{cases}$

递推起点应该是 $n = -a, k = a$

$\displaystyle S(-a) = \frac{(a+b+c)!}{(c+a)!(b-a)!a!}$

那么我们有

$\displaystyle \frac{S_{n+1}}{S_n} = \frac{|\beta_0(n)|}{|\beta_1(n)|} = \frac{(n+1+a+b+c)(n+1+a+b)}{(n+1+a)(n+1+b)}$

根据递推式，$n = d$，考虑 $\displaystyle \frac{S(d-1)}{S(-a)}$，这里要往下乘 $tot = a+d$ 项

$\displaystyle\frac{S(d-1)}{S(-a)} = \frac{(b+c+1)(b+c+2)\cdots (b+c+a+d)\cdot (b+1)(b+2)\cdots (a+b+d)}{1\cdot 2 \cdots (a+d) \cdot (b-a+1)\cdots (b+d)}$

综上所述

$\displaystyle \frac{S(d-1)}{S(-a)} = \frac{(b+c+a+d)!}{(b+c)!} \frac{(a+b+d)!}{b!} \frac{(d-a)!}{(a+d)!(b+d)!}$

从而

$S(d-1) = \displaystyle \frac{(b+c+a+d)!(a+b+d)!(a+b+c)!}{a!b!(b+c)!(a+c)!(a+d)!(b+d)!}$