A Macsyma Implementation of Zeilberger's Fast Algorithm

Fabrizio Caruso

Séminaire lotharingien de combinatoire, Tome 43 (1999-2000)

Résumé

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)=\Delta_k 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.