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: