Konrad-Zuse-Zentrum für Informationstechnik Berlin ZIB PaperWeb

SC 94-33

Wolfram Koepf Algorithms for the Indefinite and Definite Summation Appeared under the title Algorithms for m-fold Hypergeometric Summation in: Journal of Symbolic Computation (1995) 20, 399-417.

Abstract: The celebrated Zeilberger algorithm which finds holonomic recurrence equations for definite sums of hypergeometric terms $F(n,k)$ is extended to certain nonhypergeometric terms. An expression $F(n,k)$ is called hypergeometric term if both $F(n+1,k)/F(n,k)$ and $F(n,k+1)/F(n,k)$ are rational functions. Typical examples are ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are integer-linear with respect to $n$ and $k$ in their arguments.
We consider the more general case of ratios of products of exponentials, factorials, $\Gamma$ function terms, binomial coefficients, and Pochhammer symbols that are rational-linear with respect to $n$ and $k$ in their arguments, and present an extended version of Zeilbergers algorithm for this case, using an extended version of Gospers algorithm for indefinite summation.
In a similar way the Wilf-Zeilberger method of rational function certification of integer-linear hypergeometric identities is extended to rational-linear hypergeometric identities.
The given algorithms on definite summation apply to many cases in the literature to which neither the Zeilberger approach nor the Wilf-Zeilberger method is applicable. Examples of this type are given by theorems of Watson and Whipple, and a large list of identities (``Strange evaluations of hypergeometric series) that were studied by Gessel and Stanton. It turns out that with our extended algorithms practically all hypergeometric identities in the literature can be verified.
Finally we show how the algorithms can be used to generate new identities.
REDUCE and MAPLE implementations of the given algorithms can be obtained from the author, many results of which are presented in the paper.