Algorithmic identity proving and inverse problems

Official URL: https://risc01.sabanciuniv.edu/record=b2486394_(Table of contents)

In their book ‘A=B’ Marko Petkovsek, Herbert Wilf and Doron Zeilberger talked about computer generated proofs of identities which contains hypergeometric functions and four fundamental algorithms about them: Sister Celine’s Algorithm, Gosper’s Algorithm, Zeilberger’s Algorithm and Algorithm Hyper. Sister Celine’s algorithm, given a definite sum with proper hypergeometric summand finds a linear recurrence operator with polynomial coefficients which annihilates the given sum. Gosper’s algorithm, given an indefinite sum with hypergeometric summand decides whether this sum can be written as a sum of hypergeometric function and a constant. Zeilberger’s algorithm does the exact same job as Sister Celine’s algorithm. However, it is much faster. Algorithm Hyper, given a linear recurrence equation with polynomial coefficients checks whether this recurrence has hypergeometric solutions or not. In addition, Petkovsek wrote an article ‘Definite Sums as Solutions of Linear Recurrences With Polynomial Coefficients’ which tries to solve, so called Inverse Zeilberger Problem: Given a linear recurrence operator with polynomial coefficients, find a sum which is annihilated by the given linear recurrence operator. In this thesis, these four algorithms are examined in detail, and numerous examples are given. Then, an inverse problem is described, and Petkovsek’s recent paper on an instance of this particular problem is explicated. Finally, the algorithms are briefly analyzed in many aspects such as generality, time and space complexity, etc.