差分数组
如果 f(k) 是 g(k) 的差分数组,即 f(k)=Δg(k)=g(k+1)−g(k)
记 ∑f(k)δk=g(k)+C,差分数组的前缀和等于原数组
i=a∑bf(k)δk=g(k)∣ab=g(b)−g(a)
比如 k<m∑(kn)(−1)k=(−1)m−1(m−1n−1)
实际上等于差分求和 ∑(kn)(−1)kδk=(−1)k−1(k−1n−1)+C
写成差分公式,就是
Δ((−1)k(kn))=(−1)k+1(k+1n)−(−1)k(kn)=(−1)k+1(k+1n+1)
超几何函数求和
F(a1,⋯,amb1,⋯,bn∣∣∣∣∣∣ z)=k⩾1∑b1k⋯bnka1k⋯amk⋅k!zk
将超几何函数看成是关于 k 的而不是关于 z 的
∑F(a1,⋯,amb1,⋯,bn∣∣∣∣∣∣ z)kδk=cF(A1,⋯,AmB1,⋯,Bn∣∣∣∣∣∣ Z)k+C
Gosper 算法执行流程
第一步
具体思想,构造法
容易发现 t(k)t(k+1)=k+1kA(),A() 为多项式
观察超几何项,不难发现,可以写成
t(k)t(k+1)=p(k)p(k+1)r(k+1)r(k)
其中 r(k) 中含有因子 (k+b),q(k) 中含有因子 (k+a)
将 r(k) 与 p(k) 约化,可以写成 p(k)p(k+1)⋅r(k+1)q(k)(1)
其中必须满足 (k+a)∣q(k),(k+b)∣r(k),并且
a−b 不是正整数 (1)
如果不满足要怎么做?假设 a−b=N>0
考虑到 r(k) 中含有因子 (k+b),并且 r(k+1) 中含有因子 (k+b+1)
p(k)p(k+1)=(k+b+1)(k+a)⋅A(),可以同时划归
由此 p(k)p(k+1)=(k+a−1)⋯(k+b+2)(k+b+1)(k+a)(k+a−1)⋯(k+b+2)
红色部分恰好相等,也就是说,可以用
p(k)←p(k)(k+a−1)N−1=p(k)(k+a−1)(k+a−2)⋯(k+b+1)
来代替 p(k)
算法第一步就是将超几何函数写成满足 (1) 的形式
第二步
将原来的超几何项 t(k) 看作是差分数组
求一个超几何项 T(k) 使得 t(k)=T(k+1)−T(k)
将未知函数 T(k) 写成
T(k)=p(k)r(k)s(k)t(k)(2)
至于为什么要写成这种形式
不妨看 t(k+1)=p(k)p(k+1)⋅r(k+1)q(k)⋅t(k)
原数组肯定有形式 T(k)=F(k)t(k),代入 t(k)=T(k+1)−T(k)
从而 t(k)=(F(k+1)p(k)p(k+1)r(k+1)q(k)−F(k))t(k)
令 F(k+1)=s(k+1)p(k+1)r(k+1)
从而 T(k)=p(k)r(k)s(k)t(k)
其中 s(k) 必须用某种方法来发现
将其带入差分就可以发现
t(k)=p(k+1)r(k+1)s(k+1)t(k+1)−p(k)r(k)s(k)t(k)
由于 t(k+1)=p(k)r(k+1)p(k+1)q(k)⋅t(k)
从而 t(k)=p(k)q(k)s(k+1)t(k)−p(k)r(k)s(k)t(k)
由此有一个重要的递归关系
p(k)=q(k)s(k+1)−r(k)s(k)(3)
如果能够找到 s(k),那么就找到了 T(k)=∑t(k)δk,否则找不到 T
下面证明 s(k) 为一个多项式
s(k)=f(k)/g(k),如果 g(k) 不是常数,并且 f(k),g(k) 之间没有公共因子
不妨设 g(k) 的因子为 (k+β),(k+β+N−1)
其中我们令 N 是使得 (k+β+N−1) 作为 g(k) 因子出现的最大整数,因为 N=1 总满足条件
所以对于一个数 β,我们总可以尝试找到这样的 N
由此方程 (3) 可以改写成
p(k)g(k+1)g(k)=q(k)f(k+1)g(k)−r(k)g(k+1)f(k)
根据上面的假设,我们有 k=−β,k=1−β−N 时,g(−β)=0, g(1−β−N)=0
由此我们可以取 k=−β, k=−β−N
r(−β)g(1−β)f(−β)=0=q(−β−N)f(1−β−N)g(−β−N)
根据最先的归纳假设,f(k) 并不含有 (k+β),(k+β+N−1) 这个公共因子
所以 f(−β)=0,f(1−β−N)=0
又因为之前我们假设 N 是 最大的使得 (k+β+N−1) 为 g(k) 因子的项
所以 kmin=1−N−β 使得 k 为 g(k)=0 的根
换句话说, g(1−β)=0, g(−β−N)=0
从而有 r(−β)=q(−β−N)=0
回顾条件 (1),我们构造的时候是令 (k+α)∣q(k), (k+β)∣r(k)
并且 α−β 不是正整数
那么当 r(−β)=0 说明 (k+β)∣r(k),(k+β+N)∣q(k)
如果我们取 α=β+N,β=β,那么就违背了算法假定条件,得出矛盾
所以 s(k) 一定是多项式
如果已知 s(k) 的次数是 d,那么很容易可以有
s(k)=αdkd+αd−1kd−1+⋯+α0,αd=0
将表达式代入 (3) 中,让 k 的对应幂指相等即可得到线性方程求解
问题了来了,如何确定 s(k) 的次数
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)
2p(k)=Q(k)(s(k+1)+s(k))+R(k)(s(k+1)−s(k))(4)
Q(k)=q(k)−r(k),R(k)=q(k)+r(k)
注意到如果 s(k) 次数为 d,那么 s(k+1)+s(k)=2αdkd+⋯ 次数也是 d
差分 s(k+1)−s(k)=Δs(k)=dαdkd−1+⋯ 次数为 d−1,用 deg 表示多项式次数
如果 deg(Q)⩾deg(R),那么 (4) 右边次数是 deg(Q)+d
此时 d=deg(p)−deg(Q)
如果 deg(Q)<deg(R)=d′,那么可以有形式
R(k)=λkd′+⋯λ=0
Q(k)=λ′kd′−1+⋯
代入 (4) 中,我们有
(2λ′αd+λdαd)kd+d′−1+⋯
分类讨论如下,注意到这里我们令 d′=deg(R),deg(p)⩽d+deg(R)−1
- 2λ′+λd=0 且 d=deg(p)−deg(R)+1
- 2λ′+λd=0 且 d>deg(p)−deg(R)+1,当且仅当 d=−2λ′/λ 并且
−2λ′/λ>deg(p)−deg(R)+1
第二种情形只有在 −2λ′/λ>deg(p)−deg(R)+1 时才需要核查
一些例子
∑(kn)(−1)kδk 的封闭形式
t(k)=(kn)(−1)k=k!(n−k)!n!(−1)k
第一步,划归
可以将比值表示成我们想要的形式,根据 (1)
t(k)t(k+1)=k+1k−n=p(k)p(k+1)r(k+1)q(k)
可以直接取 p(k)=1,q(k)=k−n,r(k)=k,这样是可以满足 q(k)/r(k) 没有 d>0 的关于 k 的因子 kd
第二步,根据 (4)
Q(k)=q(k)−r(k),R(k)=q(k)+r(k)
可以得到 Q(k)=−n,R(k)=2k−n,我们先尝试 d=deg(p)−deg(R)+1=0−1+1=0
也就是说,此时 s(k) 最高次是 0 次,此时 s(k)=α0
代入 (3),方程转化为 1=(k−n)α0−kα0,得到 s(k)=α0=−1/n
最后将求出的 s(k) 代入 (2)
T(k)=k(n−1)(kn)(−1)k=(k−1n−1)(−1)k−1
一些例子
(1) ⌈k/2⌉ 不是超几何项
(2) 求所有复数 z,使得 k!2/j=1∏k(j2+jz+1) 是可以超几何求和的