差分数组

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

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

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

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

写成差分公式,就是

Δ((1)k(nk))=(1)k+1(nk+1)(1)k(nk)=(1)k+1(n+1k+1)\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}

超几何函数求和

F(a1,,amb1,,bn| z)=k1a1kamkb1kbnkzkk!\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!}

将超几何函数看成是关于 kk 的而不是关于 zz

F(a1,,amb1,,bn| z)kδk=cF(A1,,AmB1,,Bn| Z)k+C\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 算法执行流程

第一步

具体思想,构造法

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

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

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

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

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

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

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

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

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

由此 p(k+1)p(k)=(k+a)(k+a1)(k+b+2)(k+a1)(k+b+2)(k+b+1)\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) }

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

p(k)p(k)(k+a1)N1=p(k)(k+a1)(k+a2)(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)p(k)

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

第二步

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

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

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

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

不妨看 t(k+1)=p(k+1)p(k)q(k)r(k+1)t(k)\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) = F(k)t(k),代入 t(k)=T(k+1)T(k)t(k) = T(k+1) - T(k)

从而 t(k)=(F(k+1)p(k+1)p(k)q(k)r(k+1)F(k))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)

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

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

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

t(k)=r(k+1)s(k+1)t(k+1)p(k+1)r(k)s(k)t(k)p(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)}

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

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

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

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

如果能够找到 s(k)s(k),那么就找到了 T(k)=t(k)δkT(k) = \sum t(k)\delta k,否则找不到 TT

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

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

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

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

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

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

p(k)=q(k)s(k+1)r(k)s(k)+q(k)s(k)q(k)s(k)\displaystyle p(k) = q(k)s(k+1) - r(k)s(k) + q(k)s(k) - q(k)s(k)
p(k)=r(k)s(k+1)+r(k)s(k+1)+q(k)s(k+1)r(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)

2p(k)=Q(k)(s(k+1)+s(k))+R(k)(s(k+1)s(k))(4)\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),R(k)=q(k)+r(k)Q(k) = q(k) - r(k), \quad R(k) = q(k) + r(k)

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

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

  • 2λ+λd02\lambda' + \lambda d \neq 0d=deg(p)deg(R)+1d = \text{deg}(p) - \text{deg}(R)+1
  • 2λ+λd=02\lambda' + \lambda d = 0d>deg(p)deg(R)+1d > \text{deg}(p) - \text{deg}(R) + 1,当且仅当 d=2λ/λd = -2\lambda' / \lambda 并且
    2λ/λ>deg(p)deg(R)+1-2\lambda' / \lambda > \text{deg}(p) - \text{deg}(R) + 1

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

一些例子

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

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

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

t(k+1)t(k)=knk+1=p(k+1)p(k)q(k)r(k+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)=kn,r(k)=kp(k) = 1, q(k) = k-n, r(k) = k,这样是可以满足 q(k)/r(k)q(k) / r(k) 没有 d>0d > 0 的关于 kk 的因子 kdk^d

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

代入 (3)\textbf{(3)},方程转化为 1=(kn)α0kα01 = (k-n)\alpha_0 - k\alpha_0,得到 s(k)=α0=1/ns(k) = \alpha_0 = -1/n

最后将求出的 s(k)s(k) 代入 (2)\textbf{(2)}

T(k)=k(1n)(nk)(1)k=(n1k1)(1)k1\displaystyle T(k) = k \left(\frac{-1}{n} \right) \binom{n}{k}(-1)^k = \binom{n-1}{k-1} (-1)^{k-1}

一些例子

(1) k/2\displaystyle \left \lceil k/2 \right \rceil 不是超几何项

(2) 求所有复数 zz,使得 k!2/j=1k(j2+jz+1)\displaystyle k!^2 / \prod_{j = 1}^{k} (j^2 + jz + 1) 是可以超几何求和的