Séminaire Lotharingien de Combinatoire, S43c (2000), 8 pp.

Fabrizio Caruso

A Macsyma Implementation of Zeilberger's Fast Algorithm

Abstract. We present the first implementation within the Macsyma computer algebra system of Zeilberger's fast algorithm for the definite summation problem for a very large class of sequences; i.e., given a hypergeometric sequence F(n,k), we want to represent f(n)=sum_{k=0}^{n} F(n,k) in a "simpler" form. We do this by finding a linear recurrence for the summand F(n,k), from which we can obtain a homogeneous k-free recurrence for f(n). The solution of this recurrence is left as a post-processing, and it will give the "simpler" form we were looking for.

Zeilberger's fast algorithm exploits a specialized version of Gosper's algorithm for the indefinite summation problem; i.e., given a hypergeometric sequence t(k), the problem of finding another sequence T(k) such that t(k)=\Deltak T(k)=T(k+1)- T(k). The implementation of this algorithm has been carried out in Macsyma, and its details are also briefly described in this paper.

Received: January 24, 2000; Revised: May 19, 2000; Accepted: June 29, 2000.

The following versions are available: