Indefinite summation of rational functions with factorization of denominators
S. P. Polyakov · Programming and Computer Software · 2011
A computer algebra algorithm for indefinite summation of rational functions based on complete factorization of denominators is proposed. For a given f, the algorithm finds two rational functions g, r such that f = g(x + 1) − g(x) + r and the degree of the denominator of r is minimal. A modification of the algorithm is also proposed that additionally minimizes the degree of the denominator of g. Computational complexity of the algorithms without regard to denominator factorization is shown to be O(m 2), where m is the degree of the denominator of f.