Check-ins Using Download Hex

Artifact cc46600e4152b33eabdae4d015bb93beac53fcdc1f02260f95d76f2d7e9d0080:

\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}
REDUCE Historical
[ REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]