才奥伯格算法

才奥伯格算法（Zeilberger's algorithm），理学-数学-组合数学-组合恒等式的机器证明，D.才奥伯格（Doron Zeilberger，以色列，1950-07-02～  ）于1990年在高斯珀算法的基础上给出的算法。才奥伯格算法设计的目的是为了证明超几何级数的恒等式。又称邻差算子方法。假设是一个关于和的二元超几何项，也就是说与均是关于和的有理函数。想要证明如下形式的恒等式：式中与均已知。如果能写成的形式，则可以用高斯珀算法求出的不定和并得到的闭形式。在这种情况下，不但可以得到的闭形式，而且还可以将和式表示为一个关于变化的求和上界的函数。但是在很多时候，这样的是不存在的，也就是说高斯珀算法找不到。才奥伯格算法的主要任务是构造出如下形式的斜递推关系：式中是关于的多项式，是关于，的有理函数。才奥伯格算法的实现与高斯珀算法类似，也是将求解多项式系数和有理函数的问题转化为求多项式解的问题。由于是与无关的多项式，一旦才奥伯格算法成功找到上述递推关系，将该关系式对所有整数求和可得超几何和式满足的递推关系。此时超几何等式为，即可通过验证等式两边满足相同的递推关系以及初值的方法来证明。