Gosper-Zeilberger 算法是 Gosper 算法的推广，用于计算任意 hypergeometric 项的求和。
主要思路
对于和式
\[ S=\sum_{k=1}^nt(k) \]
如果其中的项 \(t(k)\) 是 hypergeometric 的，那么我们可以将其分解为 \(t(k)=T(k+1)-T(k)\)，从而使和式变为
\[ S=\sum_{k=1}^nt(k)=\sum_{k=1}^n[T(k+1)-T(k)]=T(n+1)-T(1) \]
算法步骤
首先我们基于 hypergeometric 项构造另一个 hypergeometric 项：
\[ \hat{t}(n,k)=\beta_0(n)t(n,k)+\beta_1(n)t(n+1,k) \]
然后对该 hypergeometric 项，先分解
\[ \frac{\hat{t}(n, k+1)}{\hat{t}(n, k)}=\frac{\hat{p}(n, k+1)}{\hat{p}(n, k)}\frac{q(k)}{r(k+1)} \]
从 \(\hat{p}(n,k)=1\) 开始，找到所有 \(\alpha, \beta\) 满足
\[ (k+\alpha)|q(k), (k+\beta)|r(k), \alpha-\beta<0 \]
当 \(\alpha-\beta>0\) 时，我们更新 \(\hat{p}(n,k)\to\hat{p}(n,k)(k+\alpha-1)(k+\alpha-2)...(k+\beta+1)\).
令 \(Q(k)=q(k)-r(k), R(k)=q(k)+r(k)\)，并作比较：
- 若 \(d_Q\geq d_R\)，则 \(d=d_p-d_Q\)
- 若 \(d_Q<d_R\)，则 \(d=d_p-d_R+1\)
其中 \(d_p, d_Q, d_R\) 分别是 \(\hat{p(k)}, Q(k), R(k)\) 中 \(k\) 的阶。注意对零值函数有特殊的取值，即若 \(f(k)=0\)，则 \(d_f=-1\)。
若 \(d<0\)，则需要进入下一轮的 Gosper-Zeilberger 算法，更新
\[ \hat{t}(n,k)=\beta_0(n)t(n,k)+\beta_1(n)t(n+1,k)+\beta_2(n)t(n+2,k) \]
反之，进入下一步。
从 Gosper 等式中求出 \(\beta_i,i=0,1,...\)：
\[ \hat{p}(n,k)=q(k)s(k+1)-r(k)s(k) \]
其中 \(d_s=d,s(k)=s_dk^d+s_{d-1}k^{d-1}+...+s_1k+s_0\).
最后，我们可以作分解：\(t(k)=T(k+1)-T(k)\)，其中 \(T(k)=\frac{r(k)s(k)t(k)}{p(k)}\).
例子
计算
\[ T(r,l)=\sum_{s=1}^M\begin{pmatrix} r \\ s \end{pmatrix}\begin{pmatrix} l-1 \\ s-1 \end{pmatrix}(-1)^{r-s} \]
Let \(t(r,l,s)=\begin{pmatrix} r \\ s \end{pmatrix}\begin{pmatrix} l-1 \\ s-1 \end{pmatrix}(-1)^{r-s}\). If we fix \(l\) and increase \(r\) by one, then we have \(t(r+1,l,s)=-\frac{r+1}{r-s+1}t(r,l,s)\), which means \[\begin{align*} \hat{t}(r,l,s)&=\beta_0t(r,l,s)+\beta_1t(r+1,l,s) \\ &=[\beta_0(r-s+1)-\beta_1(r+1)]\frac{t(r,l,s)}{r-s+1} \\ &=\hat{p}(r,l,s)\frac{t(r,l,s)}{r-s+1} \end{align*}\] where \(\beta_0\) and \(\beta_1\) are constants. So we have \[\begin{align*} \frac{\hat{t}(r,l,s+1)}{\hat{t}(r,l,s)}=\frac{\hat{p}(r,l,s+1)}{\hat{p}(r,l,s)}\left(-\frac{r-s+1}{r-s}\frac{r-s}{s+1}\frac{l-s}{s}\right)=\frac{\hat{p}(r,l,s+1)}{\hat{p}(r,l,s)}\left(-\frac{(r-s+1)(l-s)}{s(s+1)}\right) \end{align*}\] Let \(p(s)=\hat{p}(r,l,s)\), \(q(s)=-(r-s+1)(l-s)=-s^2+(r+l+1)s-l(r+1)\), \(r(s)=(s-1)s=s^2-s\), then we have \[\begin{align*} Q(s)&=q(s)-r(s)=-2s^2+(r+l+1)s-l(r+1) \\ R(s)&=q(s)+r(s)=(r+l)s-l(r+1) \end{align*}\] that is, \[deg_Q(s)=2>deg_R(s)=1\implies d=deg_p(s)-deg_q(s)=1-2=-1<0\] which means we need one more iteration of Gosper-Zeilberger algorithm. The steps are similar.
Since \(t(r+2,l,k)=\frac{r+2}{r-s+2}t(r+1,l,s)=\frac{(r+2)(r+1)}{(r-s+2)(r-s+1)}t(r,l,s)\), we have \[\begin{align*} \hat{t}(r,l,s)&=\beta_0t(r,l,s)+\beta_1t(r+1,l,s)+\beta_2t(r+2,l,s) \\ &=[\beta_0(r-s+2)(r-s+1)-\beta_1(r+1)(r-s+2)+\beta_2(r+1)(r+2)]\frac{t(r,l,s)}{(r-s+2)(r-s+1)} \\ &=\hat{p}(r,l,s)\frac{t(r,l,s)}{(r-s+2)(r-s+1)} \end{align*}\] where \(\beta_0\), \(\beta_1\) and \(\beta_2\) are constants. So we have \[\begin{align*} \frac{\hat{t}(r,l,s+1)}{\hat{t}(r,l,s)}=\frac{\hat{p}(r,l,s+1)}{\hat{p}(r,l,s)}\left(-\frac{r-s+2}{r-s}\frac{r-s}{s+1}\frac{l-s}{s}\right)=\frac{\hat{p}(r,l,s+1)}{\hat{p}(r,l,s)}\left(-\frac{(r-s+2)(l-s)}{s(s+1)}\right) \end{align*}\] Let \(p(s)=\hat{p}(r,l,s)\), \(q(s)=-(r-s+2)(l-s)=-s^2+(r+l+2)s-l(r+2)\), \(r(s)=(s-1)s=s^2-s\), then we have \[\begin{align*} Q(s)&=q(s)-r(s)=-2s^2+(r+l+3)s-l(r+2) \\ R(s)&=q(s)+r(s)=(r+l+1)s-l(r+2) \end{align*}\] that is, \[deg_Q(s)=2>deg_R(s)=1\implies d=deg_p(s)-deg_q(s)=2-2=0\] so we can let \(u(s)=u\), a constant. From the equation \(p(s)=q(s)u(s+1)-r(s)u(s)\), we have \[\begin{align*} &\beta_0(r-s+2)(r-s+1)-\beta_1(r+1)(r-s+2)+\beta_2(r+1)(r+2)=-2us^2+(r+l+3)us-l(r+2)u \\ \implies &\beta_0s^2-[(2r+3)\beta_0-(r+1)\beta_1]s+(r+1)(r+2)(\beta_0-\beta_1+\beta_2)\\&=-2us^2+(r+l+3)us-l(r+2)u \end{align*}\] which means, \[\begin{align*} \left\{\begin{array}{l} \beta_0 = -2u \\ -(2r+3)\beta_0+(r+1)\beta_1 = (r+l+3)u \\ (r+1)(r+2)(\beta_0-\beta_1+\beta_2) = -l(r+2)u \end{array}\right. \implies \left\{\begin{array}{l} \beta_0 = -2u \\ (r+1)\beta_1 = (l-3r-4)u \\ (r+1)\beta_2 = -(r+2)u \end{array}\right. \end{align*}\] We can let \(u=r+1\), so we have \[\begin{align*} \left\{\begin{array}{l} \beta_0 = -2(r+1) \\ \beta_1 = l-3r-4 \\ \beta_2 = -(r+2) \end{array}\right. \end{align*}\] Therefore, \[\begin{align*} &\beta_0t(r,l,s)+\beta_1t(r+1,l,s)+\beta_2t(r+2,l,s)=\hat{t}(r,l,s) \\ \implies &\beta_0\sum_{s=1}^Mt(r,l,s)+\beta_1\sum_{s=1}^Mt(r+1,l,s)+\beta_2\sum_{s=1}^Mt(r+2,l,s)=\sum_{s=1}^M\hat{t}(r,l,s) \\ \implies &-2(r+1)T(r,l,s)+(l-3r-4)T(r+1,l,s)-(r+2)T(r+2,l,s)=0 \\ \implies &(r+2)T(r+2,l,s)=-2(r+1)T(r,l,s)+(l-3r-4)T(r+1,l,s) \end{align*}\]
