Algorithms for the construction of the minimal telescopers
Keith O. Geddes, Sergei A. Abramov, H. Q. Le · 2003
Zeilberger's algorithm has been shown to be a very useful tool in a wide range of applications. These include finding closed forms of definite sums of hypergeometric terms, certifying large classes of identities in combinatorics and in the theory of special functions, and asymptotic estimates. Regardless of the extensive work on the algorithm, there still exist many interesting problems arising out of the algorithm, and a number of them were not considered or solved by the “classics”. In this thesis we address two key problems: (a) the limitations in the domain of applicability of Zeilberger's algorithm and (b) the efficiency of the algorithm. We present new algorithms which help solve or alleviate these problems. For applicability, we establish a criterion for the termination of the algorithm for the rational function case, and describe an algorithm which uses this criterion to determine the applicability of Zeilberger's algorithm. We also summarize Abramov's result on applicability for the general hypergeometric case. For efficiency, we present an algorithm which computes the minimal telescopers directly and efficiently for the rational function case, and an algorithm which computes a non-trivial lower bound for the order of the telescopers for the general hypergeometric case. We describe a Maple implementation of the package Telescopers for computing the minimal Z-pairs. The package is a sub-package of the package Hypergeometric, a Maple toolbox for working with hypergeometric terms in general, and for computing closed forms of indefinite and definite sums of hypergeometric terms in particular. In the context of symbolic summation, the package Hypergeometric becomes a sub-package of the package SumTools, a Maple summation toolbox.