We present a streamlined version of Karr's summation algorithm.
Karr's original approach constructively decides the telescoping
problem in PiSigma-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 PiSigma-extension over a given PiSigma-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 PiSigma-extensions that are
less nested than the definite sum itself.
|