Symbolic Summation In Differential Fields

We seek to understand a general method for finding a closed form for a given sum that acts as itís ``antidifference`` in the same way that an integral has an antiderivative. Once an antidifference is found, then given the limits of the sum, it suffices to evaluate the antidifference at the given limits. When the summand is hypergeometric, Gosperís algorithm finds the antidifference, if it exists.

Many frequently encountered sequences however are not hypergeometric, such as the harmonic numbers and their generalizations. In this case the summation is done by Karr's algorithm. The algorithm finds antidifferences by redefining the problem in terms of difference fields (a field equipped with an automorphism.) Once translated into a difference field setting, Karrís algorithm finds a solution to the corresponding difference equation, and if no solution is found, adjoins a symbolic solution which represents the sequence we are trying to sum up. Carsten Schneider expanded Karrís method of solving first order difference equations to higher order equations in special cases.

Karrís original papers leave out several of the key proofs needed to implement the algorithm. We attempt fill in these gaps by solving two major problems: the equivalence problem and the homogenous group membership problem. Solving these two problems is essential to finding the polynomial degree bounds and denominator bounds for solutions of difference equations.


  1. Senior Thesis by Javier Vazquez-Trejo, SCS, CMU, 2014.

Last updated Wednesday, May 07, 2014