Symbolic Summation with Single-Nested Sum Extensions

摘要

We present a streamlined and refined version of Karr's summation algorithm. Karr's original approach constructively decides the telescoping problem in ΠΣ-fields, a very general class of difference fields that can describe rational terms of arbitrarily nested indefinite sums and products. More generally, our new algorithm can decide constructively if there exists a so called single-nested ΠΣ-extension over a given ΠΣ-field in which the telescoping problem for f can be solved in terms that are not more nested than f itself. This allows to eliminate an indefinite sum over f by expressing it in terms of additional sums that are not more nested than f. Moreover, our refined algorithm contributes to definite summation: it can decide constructively if the creative telescoping problem for a fixed order can be solved in single-nested Σ~*-extensions that are less nested than the definite sum itself.