RATIONAL SUMMATION AND GOSPER-PETKOVSEK REPRESENTATION

Indefinite summation essentially deals with the problem of inverting t he difference operator Delta: f(X) --> f(X + 1) - f(X). In the case of rational functions over a field k we consider the following version o f the problem: given a epsilon k(X), determine beta, gamma epsilon k(X ) such that alpha = Delta beta+gamma, where gamma is as ''small'' as p ossible (in a suitable sense). In particular, we address the question: what can be said about the denominators of a solution (beta, gamma) b y looking at the denominator of alpha only? An ''optimal'' answer to t his question can be given in terms of the Gosper-Petkovsek representat ion for rational functions, which was originally invented for the purp ose of indefinite hypergeometric summation. This information can be us ed to construct a simple new algorithm for the rational summation prob lem. (C) 1995 Academic Press Limited