Fr\'ed\'eric Chyzak, Inria-Rocquencourt

New algorithms for definite summation and integration

In 1978, W. Gosper developed an algorithm to compute the indefinite sum of an hypergeometric sequence. This algorithm has been incorporated in most computer algebra systems as the basis of their summation routines. Then, in the early 1990's D. Zeilberger applied Gosper's algorithm in a clever way to the efficient calculation of definite sums of hypergeometric sequences. Zeilberger also produced a very general but slow algorithm for the general case of holonomic functions. Although this general case has not received much attention since then, it is of great interest in combinatorics and in the theory of special functions. In this talk, we review Gosper's and Zeilberger's algorithms. We then show how they can be generalized to obtain efficient algorithms in a much more general context, including summation and integration of holonomic functions and sequences.