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

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

The following versions are available: