Rational Summation and Gosper-Petkovšek Representation

Indefinite summation essentially deals with the problem of inverting the difference operator Δ: f ( X ) → f ( X + 1) - f ( X ). In the case of rational functions over a field k we consider the following version of the problem: given α ϵ k ( X ), determine β, γ ϵ k ( X ) such that α = Δβ+γ, where γ is as "small" as possible (in a suitable sense). In particular, we address the question: what can be said about the denominators of a solution (β, γ) by looking at the denominator of α only? An "optimal" answer to this question can be given in terms of the Gosper-Petkovsek representation for rational functions, which was originally invented for the purpose of indefinite hypergeometric summation. This information can be used to construct a simple new algorithm for the rational summation problem.