\chapter[ZEILBERG: Indef \& definite summation]%
{ZEILBERG: A package for indefinite and definite summation}
\label{ZEILBERG}
\typeout{{ZEILBERG: A package for indefinite and definite summation}}
{\footnotesize
\begin{center}
Wolfram Koepf and Gregor St\"olting \\
Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D--14195 Berlin--Dahlem, Germany \\[0.05in]
e--mail: Koepf@zib.de
\end{center}
}
\ttindex{ZEILBERG}
\newcommand{\N} {{\rm {\mbox{\protect\makebox[.15em][l]{I}N}}}}
The ZEILBERG package provides an implementation of the Gosper and
Zeilberger algorithms for indefinite, and definite summation of
hypergeometric terms, respectively, with extensions for ratios of
products of powers, factorials, $\Gamma$ function terms, binomial
coefficients, and shifted factorials that are rational-linear in their
arguments.
\section{The GOSPER summation operator}
The {\tt gosper}\ttindex{gosper} operator is an implementation of the
Gosper algorithm.
\begin{itemize}
\item
{\tt gosper(a,k)} determines a closed form antidifference. If it does
not return a closed form solution, then a closed form solution does
not exist.
\item
{\tt gosper(a,k,m,n)} determines
\[
\sum_{k=m}^n a_k
\]
using Gosper's algorithm. This is only successful if Gosper's
algorithm applies.
\end{itemize}
Example:
\begin{verbatim}
gosper((-1)^(k+1)*(4*k+1)*factorial(2*k)/
(factorial(k)*4^k*(2*k-1)*factorial(k+1)),k);
k
- ( - 1) *factorial(2*k)
------------------------------------
2*k
2 *factorial(k + 1)*factorial(k)
gosper(binomial(k,n),k);
(k + 1)*binomial(k,n)
-----------------------
n + 1
\end{verbatim}
\section{EXTENDED\_GOSPER operator}
The {\tt extended\_gosper}\ttindex{extended\_gosper} operator is an
implementation of an extended version of Gosper's algorithm.
\begin{itemize}
\item
{\tt extended\_gosper(a,k)} determines an antidifference $g_k$ of $a_k$
whenever there is a number $m$ such that $h_{k}-h_{k-m}=a_k$, and $h_k$ is an
{\sl $m$-fold hypergeometric term}, i.\ e.
\[
h_{k}/h_{k-m}\quad\mbox{is a rational function with respect to $k$.}
\]
If it does not return a solution, then such a solution does not exist.
\item
{\tt extended\_gosper(a,k,m)}
determines an {\sl $m$-fold antidifference} $h_k$ of $a_k$,
i.\ e.\ $h_{k}-h_{k-m}=a_k$, if it is an $m$-fold hypergeometric term.
\end{itemize}
Examples:
\begin{verbatim}
extended_gosper(binomial(k/2,n),k);
k k - 1
(k + 2)*binomial(---,n) + (k + 1)*binomial(-------,n)
2 2
-------------------------------------------------------
2*(n + 1)
extended_gosper(k*factorial(k/7),k,7);
k
(k + 7)*factorial(---)
7
\end{verbatim}
\section{SUMRECURSION operator}
The {\tt sumrecursion}\ttindex{sumrecursion} operator is an
implementation of the (fast) Zeilberger algorithm.
\begin{itemize}
\item
{\tt sumrecursion(f,k,n)} determines a holonomic recurrence equation
for
\[
{\tt sum(n)} =\sum\limits_{k=-\infty}^\infty f(n,k)
\]
with respect to $n$. %%, applying {\tt extended\_sumrecursion} if necessary
%%(section~\ref{sec:EXTENDED_SUMRECURSION}).
The resulting expression equals zero.
\item
{\tt sumrecursion(f,k,n,j)}
searches for a holonomic recurrence equation of order $j$.%% This
%%operator does not use
%%{\tt extended\_sumrecursion} automatically.
Note that if $j$ is too large, the recurrence equation
may not be unique, and only one particular solution is returned.
\end{itemize}
\begin{verbatim}
sumrecursion(binomial(n,k),k,n);
2*sum(n - 1) - sum(n)
\end{verbatim}
%%\section{EXTENDED\_SUMRECURSION operator}
%%\label{sec:EXTENDED_SUMRECURSION}
%%
%%The {\tt extended\_sumrecursion}\ttindex{extended\_sumrecursion}
%%operator uses extension to handle hypergeometric terms. As {\tt
%%sumrecusion} uses this algorithm automatically in the case of three
%%arguments, it is only needed in the four argument case, or for
%%detailed investigations. More details may be found in the on-line
%%documentation.
\section{HYPERRECURSION operator}
If a recursion for a generalised hypergeometric function is to be
established, one can use
\begin{itemize}
\item
{\tt hyperrecursion(upper,lower,x,n)}\ttindex{hyperrecursion}
determines a holonomic recurrence equation with respect to $n$ for
\[_{p}F_{q}\left.\left(\begin{array}{cccc}
a_{1},&a_{2},&\cdots,&a_{p}\\
b_{1},&b_{2},&\cdots,&b_{q}\\
\end{array}\right| x\right) ,
\] where {\tt upper}$=\{a_{1}, a_{2}, \ldots, a_{p}\}$
is the list of upper parameters, and
{\tt lower}$=\{b_{1}, b_{2}, \ldots, b_{q}\}$
is the list of lower parameters depending on $n$.
\item
{\tt hyperrecursion(upper,lower,x,n,j)} $(j\in\N)$
searches only for a holonomic recurrence equation of order $j$. This
operator does not automatically use {\tt extended\_sumrecursion}.
\end{itemize}
\begin{verbatim}
hyperrecursion({-n,b},{c},1,n);
(b - c - n + 1)*sum(n - 1) + (c + n - 1)*sum(n)
\end{verbatim}
If a hypergeometric expression is given in hypergeometric notation, then
the use of {\tt hyperrecursion} is more natural than the use of
{\tt sumrecursion}.
Moreover the \REDUCE\ operator
\begin{itemize}
\item
{\tt hyperterm(upper,lower,x,k)}\ttindex{hyperterm} yields the
hypergeometric term
\[
\frac
{(a_{1})_{k}\cdot(a_{2})_{k}\cdots(a_{p})_{k}}
{(b_{1})_{k}\cdot(b_{2})_{k}\cdots(b_{q})_{k}\,k!}x^{k}
\]
with upper parameters {\tt upper}$=\{a_{1}, a_{2}, \ldots, a_{p}\}$,
and lower parameters {\tt lower}$=\{b_{1}, b_{2}, \ldots, b_{q}\}$
\end{itemize}
in connection with hypergeometric terms.
\section{HYPERSUM operator}
With the operator {\tt hypersum}\ttindex{hypersum}, hypergeometric
sums are directly evaluated in closed form whenever the extended
Zeilberger algorithm leads to a recurrence equation containing only
two terms:
\begin{itemize}
\item
{\tt hypersum(upper,lower,x,n)} determines a closed form representation
for\\
$_{p}F_{q}\left.\left(\begin{array}{cccc}
a_{1},&a_{2},&\cdots,&a_{p}\\
b_{1},&b_{2},&\cdots,&b_{q}\\
\end{array}\right| x\right)
$, where {\tt upper}$=\{a_{1}, a_{2}, \ldots, a_{p}\}$
is the list of upper parameters, and
{\tt lower}$=\{b_{1}, b_{2}, \ldots, b_{q}\}$
is the list of lower parameters depending on $n$. The result is given as a
hypergeometric term with respect to $n$.
If the result is a list of length $m$, we call it $m$-{\sl fold symmetric},
which is to be interpreted as follows:
Its $j^{th}$ part is the solution valid for all $n$ of the form $n=mk+j-1
\;(k\in\N_0)$.
In particular, if the resulting list contains two terms, then the
first part is the solution for even $n$, and the second part is the
solution for odd $n$.
\end{itemize}
\begin{verbatim}
hypersum({a,1+a/2,c,d,-n},{a/2,1+a-c,1+a-d,1+a+n},1,n);
pochhammer(a - c - d + 1,n)*pochhammer(a + 1,n)
-------------------------------------------------
pochhammer(a - c + 1,n)*pochhammer(a - d + 1,n)
hypersum({a,1+a/2,d,-n},{a/2,1+a-d,1+a+n},-1,n);
pochhammer(a + 1,n)
-------------------------
pochhammer(a - d + 1,n)
\end{verbatim}
Note that the operator {\tt togamma}\ttindex{togamma} converts
expressions given in factorial-$\Gamma$-binomial-Pochhammer notation
into a pure $\Gamma$ function representation:
\begin{verbatim}
togamma(hypersum({a,1+a/2,d,-n},{a/2,1+a-d,1+a+n},-1,n));
gamma(a - d + 1)*gamma(a + n + 1)
-----------------------------------
gamma(a - d + n + 1)*gamma(a + 1)
\end{verbatim}
\section{SUMTOHYPER operator}
With the operator {\tt sumtohyper}\ttindex{sumtohyper}, sums given in
factorial-$\Gamma$-binomial-Poch\-hammer notation are converted into
hypergeometric notation.
\begin{itemize}
\item
{\tt sumtohyper(f,k)} determines the hypergeometric representation
of\linebreak
$\sum\limits_{k=-\infty}^\infty f_k$, {\em i.e.\ } its output is {\tt
c*hypergeometric(upper,lower,x)}, corresponding to
the representation
\[
\sum\limits_{k=-\infty}^\infty f_k=c\cdot\;
_{p}F_{q}\left.\left(\begin{array}{cccc}
a_{1},&a_{2},&\cdots,&a_{p}\\
b_{1},&b_{2},&\cdots,&b_{q}\\
\end{array}\right| x\right)
\;,
\]
where {\tt upper}$=\{a_{1}, a_{2}, \ldots, a_{p}\}$
and {\tt lower}$=\{b_{1}, b_{2}, \ldots, b_{q}\}$
are the lists of upper and lower parameters.
\end{itemize}
Examples:
\begin{verbatim}
sumtohyper(binomial(n,k)^3,k);
hypergeometric({ - n, - n, - n},{1,1},-1)
\end{verbatim}
\section{Simplification Operators}
For the decision that an expression $a_k$ is a hypergeometric term, it is
necessary to find out whether or not $a_{k}/a_{k-1}$ is a rational
function with respect to $k$. For the purpose to decide
whether or not an expression involving powers, factorials,
$\Gamma$ function terms,
binomial coefficients, and Pochhammer symbols is a hypergeometric term,
the following simplification operators can be used:
\begin{itemize}
\item
{\tt simplify\_gamma(f)}\ttindex{simplify\_gamma} simplifies an
expression {\tt f} involving only rational, powers and $\Gamma$
function terms.
\item
{\tt simplify\_combinatorial(f)}\ttindex{simplify\_combinatorial}
simplifies an expression {\tt f} involving powers, factorials,
$\Gamma$ function terms, binomial coefficients, and Pochhammer symbols
by converting factorials, binomial coefficients, and Poch\-hammer
symbols into $\Gamma$ function terms, and applying {\tt
simplify\_gamma} to its result. If the output is not rational, it is
given in terms of $\Gamma$ functions. If factorials are preferred use
\item
{\tt gammatofactorial} (rule)\ttindex{gammatofactorial} converting $\Gamma$ function terms into
factorials using $\Gamma\:(x)\rightarrow (x-1)!$.
\item
{\tt simplify\_gamma2(f)}\ttindex{simplify\_gamma2}
uses the duplication formula of the $\Gamma$ function to simplify $f$.
\item
{\tt simplify\_gamman(f,n)}\ttindex{simplify\_gamman}
uses the multiplication formula of the $\Gamma$ function to simplify $f$.
\end{itemize}
The use of {\tt simplify\_combinatorial(f)} is a safe way to
decide the rationality for any ratio of products of powers, factorials,
$\Gamma$ function terms, binomial coefficients, and Pochhammer symbols.
Example:
\begin{verbatim}
simplify_gamma2(gamma(2*n)/gamma(n));
2*n 2*n + 1
2 *gamma(---------)
2
-----------------------
2*sqrt(pi)
\end{verbatim}