Artifact 21f9bb19894fc325a22a1c9b7342ac76f5088cd82aaaee31b3d863fcdefdfbfe:
- File
r36/doc/ZEILBERG.TEX
— part of check-in
[152fb3bdbb]
at
2011-10-17 17:58:33
on branch master
— svn:eol-style, svn:executable and line endings for files
in historical/r36 treegit-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1480 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: schoepf@users.sourceforge.net, size: 35905) [annotate] [blame] [check-ins using] [more...]
\documentstyle[11pt,reduce]{article} \title{{\tt ZEILBERG}\\ A Package for the Indefinite\\ and Definite Summation} \date{} \author{Wolfram Koepf\\ Gregor St\"olting \\ ZIB Berlin \\ email: {\tt Koepf@ZIB-Berlin.de} } \begin{document} \maketitle \newcommand{\N} {{\rm {\mbox{\protect\makebox[.15em][l]{I}N}}}} \newcommand{\funkdef}[3]{\left\{\!\!\!\begin{array}{cc} #1 & \!\!\!\mbox{\rm{if} $#2$ } \\ #3 & \!\!\!\mbox{\rm{otherwise}} \end{array} \right.} \section{Introduction} This package is a careful implementation of the Gosper% \footnote{The {\tt sum} package contains also a partial implementation of the Gosper algorithm.} and Zeilberger algorithms for indefinite, and definite summation of hypergeometric terms, respectively. Further, extensions of these algorithms given by the first author are covered. An expression $a_k$ is called a {\sl hypergeometric term} (or {\sl closed form}), if $a_{k}/a_{k-1}$ is a rational function with respect to $k$. Typical hypergeometric terms are ratios of products of powers, factorials, $\Gamma$ function terms, binomial coefficients, and shifted factorials (Pochhammer symbols) that are integer-linear in their arguments. The extensions of Gosper's and Zeilberger's algorithm mentioned in particular are valid for ratios of products of powers, factorials, $\Gamma$ function terms, binomial coefficients, and shifted factorials that are rational-linear in their arguments. \section{Gosper Algorithm} The Gosper algorithm \cite{Gos} is a {\sl decision procedure}, that decides by algebraic calculations whether or not a given hypergeometric term $a_k$ has a hypergeometric term antidifference $g_k$, i.\ e.\ $g_{k}-g_{k-1}=a_k$ with rational $g_k/g_{k-1}$, and returns $g_k$ if the procedure is successful, in which case we call $a_k$ {\sl Gosper-summable}. Otherwise {\sl no hypergeometric term antidifference exists}. Therefore if the Gosper algorithm does not return a closed form solution, it has {\sl proved} that no such solution exists, an information that may be quite useful and important. The Gosper algorithm is the discrete analogue of the Risch algorithm for integration in terms of elementary functions. Any antidifference is uniquely determined up to a constant, and is denoted by \[ g_k=\sum\nolimits_k a_k \;. \] Finding $g_k$ given $a_k$ is called {\sl indefinite summation}. The antidifference operator $\Sigma$ is the inverse of the downward difference operator $\nabla a_k=a_{k}-a_{k-1}$. There is an analogous summation theory corresponding to the upward difference operator $\Delta a_k=a_{k+1}-a_k$. In case, an antidifference $g_k$ of $a_k$ is known, any sum \[ \sum_{k=m}^{n} a_k=g_{n}-g_{m-1} \] can be easily calculated by an evaluation of $g$ at the boundary points like in the integration case. Note, however, that the sum \begin{equation} \sum_{k=0}^n {{n}\choose{k}} \label{eq:nchoosek} \end{equation} e.\ g.\ is not of this type since the summand ${{n}\choose{k}}$ depends on the upper boundary point $n$ explicitly. This is an example of a definite sum that we consider in the next section. Our package supports the input of powers ({\tt a\verb+^+k)}, factorials ({\tt factorial(k)}), $\Gamma$ function terms ({\tt gamma(a)}), binomial coefficients ({\tt binomial(n,k)}), shifted factorials ({\tt pochhammer(a,k)$=a(a+1)\cdots(a+k-1)=\Gamma (a+k)/\Gamma (a)$}), and partially products ({\tt prod(f,k,k1,k2)}). It takes care of the necessary simplifications, and therefore provides you with the solution of the decision problem as long as the memory or time requirements are not too high for the computer used. \section{Zeilberger Algorithm} The (fast) Zeilberger algorithm \cite{Zei2}--\cite{Zei3} deals with the {\sl definite summation} of hypergeometric terms. Zeilberger's paradigm is to find (and return) a linear homogeneous recurrence equation with polynomial coefficients (called {\sl holonomic equation}) for an {\sl infinite sum} \[ s(n)=\sum_{k=-\infty}^{\infty} f(n,k) \;, \] the summation to be understood over all integers $k$, if $f(n,k)$ is a hypergeometric term with respect to both $k$ and $n$. The existence of a holonomic recurrence equation for $s(n)$ is then generally guaranteed. If one is lucky, and the resulting recurrence equation is of first order \[ p(n)\,s(n-1)+q(n)\,s(n)=0 \quad\quad(p,q\;\mbox{polynomials}) \;, \] $s(n)$ turns out to be a hypergeometric term, and a closed form solution can be easily established using a suitable initial value, and is represented by a ratio of Pochhammer or $\Gamma$ function terms if the polynomials $p$, and $q$ can be factored. Zeilberger's algorithm does not guarantee to find the holonomic equation of lowest order, but often it does. If the resulting recurrence equation has order larger than one, this information can be used for identification purposes: Any other expression satisfying the same recurrence equation, and the same initial values, represents the same function. Note that a {\sl definite sum} $\sum\limits_{k=m_1}^{m_2} f(n,k)$ is an infinite sum if $f(n,k)=0$ for $k<m_1$ and $k>m_2$. This is often the case, an example of which is the sum (\ref{eq:nchoosek}) considered above, for which the hypergeometric recurrence equation $2 s(n-1) - s(n) = 0$ is generated by Zeilberger's algorithm, leading to the closed form solution $s(n)=2^n$. Definite summation is trivial if the corresponding indefinite sum is Gosper-summable analogously to the fact that definite integration is trivial as soon as an elementary antiderivative is known. If this is not the case, the situation is much more difficult, and it is therefore quite remarkable and non-obvious that Zeilberger's method is just a clever application of Gosper's algorithm. Our implementation is mainly based on \cite{Koornwinder} and \cite{Koepf}. More examples can be found in \cite{PS}, \cite{Strehl2}, \cite{Wil1}, and \cite{Wilf} many of which are contained in the test file {\tt zeilberg.tst}. \section{\REDUCE{} operator {\tt GOSPER}} The ZEILBERG package must be loaded by: {\small \begin{verbatim} 1: load zeilberg; \end{verbatim} }\noindent The {\tt 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: {\small \begin{verbatim} 2: 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) \end{verbatim} }\noindent This solves a problem given in SIAM Review (\cite{SR}, Problem 94--2) where it was asked to determine the infinite sum \[ S=\lim_{n\rightarrow\infty} S_n \;, \quad\quad\quad S_n=\sum_{k=1}^n \frac{(-1)^{k+1}(4k+1)(2k-1)!!}{2^k(2k-1)(k+1)!} \;, \] ($(2k-1)!!=1\cdot 3 \cdots (2k-1)=\frac{(2k)!}{2^k\,k!}$). The above calculation shows that the summand is Gosper-summable, and the limit $S=1$ is easily established using Stirling's formula. The implementation solves further deep and difficult problems some examples of which are:% {\small \begin{verbatim} 3: gosper(sub(n=n+1,binomial(n,k)^2/binomial(2*n,n))- binomial(n,k)^2/binomial(2*n,n),k); 2 ((binomial(n + 1,k) *binomial(2*n,n) 2 - binomial(2*(n + 1),n + 1)*binomial(n,k) )*(2*k - 3*n - 1) 2 3 2 *(k - n - 1) )/((2*(2*(n + 1) - k)*(2*n + 1)*k - 3*n - 7*n - 5*n - 1)*binomial(2*(n + 1),n + 1)*binomial(2*n,n)) 4: gosper(binomial(k,n),k); (k + 1)*binomial(k,n) ----------------------- n + 1 5: gosper((-25+15*k+18*k^2-2*k^3-k^4)/ (-23+479*k+613*k^2+137*k^3+53*k^4+5*k^5+k^6),k); 2 - (2*k - 15*k + 8)*k ---------------------------- 3 2 23*(k + 4*k + 27*k + 23) \end{verbatim} }\noindent The Gosper algorithm is not capable to give antidifferences depending on the harmonic numbers \[ H_k:=\sum_{j=1}^k\frac{1}{j} \;, \] e.\ g.\ $\sum_k H_k=(k+1)(H_{k+1}-1)$, but, is able to give a proof, instead, for the fact that $H_k$ does not possess a closed form evaluation: {\small \begin{verbatim} 6: gosper(1/k,k); ***** Gosper algorithm: no closed form solution exists \end{verbatim} }\noindent The following code gives the solution to a summation problem proposed in Gosper's original paper \cite{Gos}. Let \[ f_k=\prod_{j=1}^k (a+b\,j+c\,j^2) \quad\quad\mbox{and}\quad\quad g_k=\prod_{j=1}^k (e+b\,j+c\,j^2) \;. \] Then a closed form solution for \[ \sum\nolimits_k\frac{f_{k-1}}{g_{k}} \] is found by the definitions {\small \begin{verbatim} 7: operator ff,gg$ 8: let {ff(~k+~m) => ff(k+m-1)*(c*(k+m)^2+b*(k+m)+a) when (fixp(m) and m>0), ff(~k+~m) => ff(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+a) when (fixp(m) and m<0)}$ 9: let {gg(~k+~m) => gg(k+m-1)*(c*(k+m)^2+b*(k+m)+e) when (fixp(m) and m>0), gg(~k+~m) => gg(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+e) when (fixp(m) and m<0)}$ \end{verbatim} }\noindent and the calculation {\small \begin{verbatim} 10: gosper(ff(k-1)/gg(k),k); ff(k) --------------- (a - e)*gg(k) 11: clear ff,gg$ \end{verbatim} }\noindent Similarly closed form solutions of $\sum\nolimits_k\frac{f_{k-m}}{g_{k}}$ for positive integers $m$ can be obtained, as well as of $\sum_k\frac{f_{k-1}}{g_{k}}$ for \[ f_k=\prod_{j=1}^k (a+b\,j+c\,j^2+d\,j^3) \quad\quad\mbox{and}\quad\quad g_k=\prod_{j=1}^k (e+b\,j+c\,j^2+d\,j^3) \] and for analogous expressions of higher degree polynomials. \section{\REDUCE{} operator {\tt EXTENDED\_GOSPER}} The {\tt extended\verb+_+gosper} operator is an implementation of an extended version of Gosper's algorithm given by Koepf \cite{Koepf}. \begin{itemize} \item {\tt extended\verb+_+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\verb+_+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: {\small \begin{verbatim} 12: extended_gosper(binomial(k/2,n),k); k k - 1 (k + 2)*binomial(---,n) + (k + 1)*binomial(-------,n) 2 2 ------------------------------------------------------- 2*(n + 1) 13: extended_gosper(k*factorial(k/7),k,7); k (k + 7)*factorial(---) 7 \end{verbatim} }\noindent \section{\REDUCE{} operator {\tt SUMRECURSION}} The {\tt 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\verb+_+sumrecursion} if necessary, see \S~\ref{sec:EXTENDED_SUMRECURSION}. The resulting expression equals zero. \item {\tt sumrecursion(f,k,n,j)} % $(j\in\N)$ searches for a holonomic recurrence equation of order $j$. This operator does not use {\tt extended\verb+_+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} A simple example deals with Equation (\ref{eq:nchoosek})% \footnote{Note that with \REDUCE{} Version 3.5 we use the global operator {\tt summ} instead of {\tt sum} to denote the sum.} {\small \begin{verbatim} 14: sumrecursion(binomial(n,k),k,n); 2*sum(n - 1) - sum(n) \end{verbatim} }\noindent The whole {\sl hypergeometric database} of the {\sl Vandermonde, Gau{\ss}, Kummer, Saalsch\"utz, Dixon, Clausen} and {\sl Dougall identities} (see \cite{Wilf}), and many more identities (see e.\ g.\ \cite{Koepf}), can be obtained using {\tt sumrecursion}. As examples, we consider the difficult cases of Clausen and Dougall:% {\small \begin{verbatim} 15: summand:=factorial(a+k-1)*factorial(b+k-1)/(factorial(k)* factorial(-1/2+a+b+k))*factorial(a+n-k-1)*factorial(b+n-k-1)/ (factorial(n-k)*factorial(-1/2+a+b+n-k))$ 16: sumrecursion(summand,k,n); (2*a + 2*b + 2*n - 1)*(2*a + 2*b + n - 1)*sum(n)*n - 2*(2*a + n - 1)*(a + b + n - 1)*(2*b + n - 1)*sum(n - 1) 17: summand:=pochhammer(d,k)*pochhammer(1+d/2,k)*pochhammer(d+b-a,k)* pochhammer(d+c-a,k)*pochhammer(1+a-b-c,k)*pochhammer(n+a,k)* pochhammer(-n,k)/(factorial(k)*pochhammer(d/2,k)* pochhammer(1+a-b,k)*pochhammer(1+a-c,k)*pochhammer(b+c+d-a,k)* pochhammer(1+d-a-n,k)*pochhammer(1+d+n,k))$ 18: sumrecursion(summand,k,n); (2*a - b - c - d + n)*(b + n - 1)*(c + n - 1)*(d + n)*sum(n - 1) + (a - b - c - d - n + 1)*(a - b + n)*(a - c + n)*(a - d + n - 1) *sum(n) \end{verbatim} }\noindent corresponding to the statements \[ _4 F_3\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{c} a\;, b\;, 1/2-a-b-n\;, -n \end{array}}\\[1mm] \multicolumn{1}{c}{\begin{array}{c} 1/2+a+b \;, 1-a-n\;, 1-b-n \end{array}}\end{array} \!\!\!\! \right| 1\right) =\frac{(2a)_n\,(a+b)_n\,(2b)_n} {(2a+2b)_n\,(a)_n\,(b)_n} \] and \[ _7 F_6\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{c} d\;, 1+d/2\;, d+b-a\;, d+c-a\;, 1+a-b-c\;, n+a\;, -n \end{array}}\\[1mm] \multicolumn{1}{c}{\begin{array}{c} d/2\;, 1+a-b\;, 1+a-c\;, b+c+d-a \;, 1+d-a-n\;, 1+d+n \end{array}}\end{array} \!\!\!\! \right| 1\right) \] \[ =\frac{(d+1)_n\,(b)_n\,(c)_n\,(1+2\,a-b-c-d)_n} {(a-d)_n\,(1+a-b)_n\,(1+a-c)_n\,(b+c+d-a)_n} \] (compare next section), respectively. Other applications of the Zeilberger algorithm are connected with the verification of identities. To prove the identity \[ \sum_{k=0}^n {{n}\choose{k}}^3 = \sum_{k=0}^n {{n}\choose{k}}^2 {{2k}\choose{n}} \;, \] e.\ g., we may prove that both sums satisfy the same recurrence equation {\small \begin{verbatim} 19: sumrecursion(binomial(n,k)^3,k,n); 2 2 2 (7*n - 7*n + 2)*sum(n - 1) + 8*(n - 1) *sum(n - 2) - sum(n)*n 20: sumrecursion(binomial(n,k)^2*binomial(2*k,n),k,n); 2 2 2 (7*n - 7*n + 2)*sum(n - 1) + 8*(n - 1) *sum(n - 2) - sum(n)*n \end{verbatim} }\noindent and finally check the initial conditions: {\small \begin{verbatim} 21: sub(n=0,k=0,binomial(n,k)^3); 1 22: sub(n=0,k=0,binomial(n,k)^2*binomial(2*k,n)); 1 23: sub(n=1,k=0,binomial(n,k)^3)+sub(n=1,k=1,binomial(n,k)^3); 2 24: sub(n=1,k=0,binomial(n,k)^2*binomial(2*k,n))+ sub(n=1,k=1,binomial(n,k)^2*binomial(2*k,n)); 2 \end{verbatim} }\noindent \section{\REDUCE{} operator {\tt EXTENDED\_SUMRECURSION}} \label{sec:EXTENDED_SUMRECURSION} The {\tt extended\verb+_+sumrecursion} operator is an implementation of an extension of the (fast) Zeilberger algorithm given by Koepf \cite{Koepf}. \begin{itemize} \item {\tt extended\verb+_+sumrecursion(f,k,n,m,l)} determines a holonomic recurrence equation for ${\tt sum(n)} =\sum\limits_{k=-\infty}^\infty f(n,k)$ with respect to $n$ if $f(n,k)$ is an {\sl $(m,l)$-fold hypergeometric term} with respect to $(n,k)$, i.\ e.\ \[ \frac{F(n,k)}{F(n-m,k)} \quad \mbox{and} \quad \frac{F(n,k)}{F(n,k-l)} \] are rational functions with respect to both $n$ and $k$. The resulting expression equals zero. \item {\tt sumrecursion(f,k,n)} invokes {\tt extended\verb+_+sumrecursion(f,k,n,m,l)} with suitable values $m$ and $l$, and covers therefore the extended algorithm completely. \end{itemize} Examples: {\small \begin{verbatim} 25: extended_sumrecursion(binomial(n,k)*binomial(k/2,n),k,n,1,2); sum(n - 1) + 2*sum(n) \end{verbatim} }\noindent which can be obtained automatically by {\small \begin{verbatim} 26: sumrecursion(binomial(n,k)*binomial(k/2,n),k,n); sum(n - 1) + 2*sum(n) \end{verbatim} }\noindent Similarly, we get {\small \begin{verbatim} 27: extended_sumrecursion(binomial(n/2,k),k,n,2,1); 2*sum(n - 2) - sum(n) 28: sumrecursion(binomial(n/2,k),k,n); 2*sum(n - 2) - sum(n) 29: sumrecursion(hyperterm({a,b,a+1/2-b,1+2*a/3,-n}, {2*a+1-2*b,2*b,2/3*a,1+a+n/2},4,k)/(factorial(n)*2^(-n)/ factorial(n/2))/hyperterm({a+1,1},{a-b+1,b+1/2},1,n/2),k,n); sum(n - 2) - sum(n) \end{verbatim} }\noindent In the last example, the progam chooses $m=2$, and $l=1$ to derive the resulting recurrence equation (see \cite{Koepf}, Table 3, (1.3)). \section{\REDUCE{} operator {\tt HYPERRECURSION}} Sums to which the Zeilberger algorithm applies, in general are special cases of the {\sl generalized hypergeometric function} \[ _{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) := \sum_{k=0}^\infty \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} \label{eq:coefficientformula} \] with upper parameters $\{a_{1}, a_{2}, \ldots, a_{p}\}$, and lower parameters $\{b_{1}, b_{2}, \ldots, b_{q}\}$. If a recursion for a generalized hypergeometric function is to be established, you can use the following \REDUCE{} operator: \begin{itemize} \item {\tt hyperrecursion(upper,lower,x,n)} 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$. If Zeilberger's algorithm does not apply, {\tt extended\verb+_+sumrecursion} of \S~\ref{sec:EXTENDED_SUMRECURSION} is used. \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 use {\tt extended\verb+_+sumrecursion} automatically. \end{itemize} Therefore {\small \begin{verbatim} 30: hyperrecursion({-n,b},{c},1,n); (b - c - n + 1)*sum(n - 1) + (c + n - 1)*sum(n) \end{verbatim} }\noindent establishes the Vandermonde identity \[ _2 F_1\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{cc} -n\;, & b \end{array}}\\[1mm] \multicolumn{1}{c}{ c} \end{array} \!\!\!\! \right| 1\right) =\frac{(c-b)_n}{(c)_n} \;, \] whereas {\small \begin{verbatim} 31: hyperrecursion({d,1+d/2,d+b-a,d+c-a,1+a-b-c,n+a,-n}, {d/2,1+a-b,1+a-c,b+c+d-a,1+d-a-n,1+d+n},1,n); (2*a - b - c - d + n)*(b + n - 1)*(c + n - 1)*(d + n)*sum(n - 1) + (a - b - c - d - n + 1)*(a - b + n)*(a - c + n)*(a - d + n - 1) *sum(n) \end{verbatim} }\noindent proves Dougall's identity, again. 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 you may use the \REDUCE{} operator \begin{itemize} \item {\tt hyperterm(upper,lower,x,k)} that 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. The operator {\tt sumrecursion} can also be used to obtain three-term recurrence equations for systems of orthogonal polynomials with the aid of known hypergeometric representations. By (\cite{NSU}, (2.7.11a)), the discrete Krawtchouk polynomials $k_n^{(p)}(x,N)$ have the hypergeometric representation \[ k_n^{(p)}(x,N)= (-1)^n\,p^n\,{{N}\choose{n}}\; _2 F_1\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{cc} -n\;, & -x \end{array}}\\[1mm] \multicolumn{1}{c}{ -N} \end{array} \!\!\!\! \right| \frac{1}{p}\right) \;, \] and therefore we declare {\small \begin{verbatim} 32: krawtchoukterm:= (-1)^n*p^n*binomial(NN,n)*hyperterm({-n,-x},{-NN},1/p,k)$ \end{verbatim} }\noindent and get the three three-term recurrence equations {\small \begin{verbatim} 33: sumrecursion(krawtchoukterm,k,n); ((2*p - 1)*n - nn*p - 2*p + x + 1)*sum(n - 1) - (n - nn - 2)*(p - 1)*sum(n - 2)*p - sum(n)*n 34: sumrecursion(krawtchoukterm,k,x); (2*(x - 1)*p + n - nn*p - x + 1)*sum(x - 1) - ((x - 1) - nn)*sum(x)*p - (p - 1)*(x - 1)*sum(x - 2) 35: sumrecursion(krawtchoukterm,k,NN); ((p - 2)*nn + n + x + 1)*sum(nn - 1) + (n - nn)*(p - 1)*sum(nn) + (nn - x - 1)*sum(nn - 2) \end{verbatim} }\noindent with respect to the parameters $n$, $x$, and $N$ respectively. \section{\REDUCE{} operator {\tt HYPERSUM}} With the operator {\tt 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} Examples \cite{Koepf}: {\small \begin{verbatim} 36: 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) 37: 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} }\noindent Note that the operator {\tt togamma} converts expressions given in factorial-$\Gamma$-binomial-Pochhammer notation into a pure $\Gamma$ function representation: {\small \begin{verbatim} 38: togamma(ws); gamma(a - d + 1)*gamma(a + n + 1) ----------------------------------- gamma(a - d + n + 1)*gamma(a + 1) \end{verbatim} }\noindent Here are some $m$-fold symmetric results: {\small \begin{verbatim} 39: hypersum({-n,-n,-n},{1,1},1,n); n/2 2 n 1 n ( - 27) *pochhammer(---,---)*pochhammer(---,---) 3 2 3 2 {----------------------------------------------------, n 2 factorial(---) 2 0} 40: hypersum({-n,n+3*a,a},{3*a/2,(3*a+1)/2},3/4,n); 2 n 1 n pochhammer(---,---)*pochhammer(---,---) 3 3 3 3 {-----------------------------------------------------, 3*a + 2 n 3*a + 1 n pochhammer(---------,---)*pochhammer(---------,---) 3 3 3 3 0, 0} \end{verbatim} }\noindent These results correspond to the formulas (compare \cite{Koepf}) \[ _3 F_2\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{c} -n\;, -n\;, -n \end{array}}\\[1mm] \multicolumn{1}{c}{\begin{array}{c} 1 \;, 1 \end{array}}\end{array} \!\!\!\! \right| 1\right) = \funkdef{0}{n\;\mbox{odd}}{\displaystyle \frac{(1/3)_{n/2}\,(2/3)_{n/2}}{(n/2)!^2}\,(-27)^{n/2} } \] and \[ _3 F_2\left. \!\! \left( \!\!\!\! \begin{array}{c} \multicolumn{1}{c}{\begin{array}{c} -n\;, n+3a\;, a \end{array}}\\[1mm] \multicolumn{1}{c}{\begin{array}{c} 3a/2\;,(3a+1)/2 \end{array}}\end{array} \!\!\!\! \right| \frac{3}{4}\right) = \funkdef{0}{n\neq 0 {\mbox{ (mod }} 3)}{\displaystyle \frac{(1/3)_{n/3}\,(2/3)_{n/3}} {(a+1/3)_{n/3}\,(a+2/3)_{n/3}} } \!\!\!\!\!\!\!\!. \] \section{\REDUCE{} operator {\tt SUMTOHYPER}} With the operator {\tt 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$, 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: {\small \begin{verbatim} 41: sumtohyper(binomial(n,k)^3,k); hypergeometric({ - n, - n, - n},{1,1},-1) 42: sumtohyper(binomial(n,k)/2^n-sub(n=n-1,binomial(n,k)/2^n),k); - n + 2 - n - hypergeometric({----------, - n,1},{1,------},-1) 2 2 ------------------------------------------------------ n 2 \end{verbatim} }\noindent \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\verb+_+gamma(f)} simplifies an expression {\tt f} involving only rational, powers and $\Gamma$ function terms according to a recursive application of the simplification rule $\Gamma\:(a+1)=a\,\Gamma\:(a)$ to the expression tree. Since all $\Gamma$ arguments with integer difference are transformed, this gives a decision procedure for rationality for integer-linear $\Gamma$ term product ratios. \item {\tt simplify\verb+_+combinatorial(f)} 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\verb+_+gamma} to its result. If the output is not rational, it is given in terms of $\Gamma$ functions. If you prefer factorials you may use \item {\tt gammatofactorial} (rule) converting $\Gamma$ function terms into factorials using $\Gamma\:(x)\rightarrow (x-1)!$. \item {\tt simplify\verb+_+gamma2(f)} uses the duplication formula of the $\Gamma$ function to simplify $f$. \item {\tt simplify\verb+_+gamman(f,n)} uses the multiplication formula of the $\Gamma$ function to simplify $f$. \end{itemize} The use of {\tt simplify\verb+_+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: {\small \begin{verbatim} 43: simplify_combinatorial(sub(k=k+1,krawtchoukterm)/krawtchoukterm); (k - n)*(k - x) -------------------- (k - nn)*(k + 1)*p \end{verbatim} }\noindent From this calculation, we see again that the upper parameters of the hypergeometric representation of the Krawtchouk polynomials are given by $\{-n,-x\}$, its lower parameter is $\{-N\}$, and the argument of the hypergeometric function is $1/p$. Other examples are {\small \begin{verbatim} 44: simplify_combinatorial(binomial(n,k)/binomial(2*n,k-1)); gamma( - (k - 2*n - 2))*gamma(n + 1) ---------------------------------------- gamma( - (k - n - 1))*gamma(2*n + 1)*k 45: ws where gammatofactorial; factorial( - k + 2*n + 1)*factorial(n) ---------------------------------------- factorial( - k + n)*factorial(2*n)*k 46: simplify_gamma2(gamma(2*n)/gamma(n)); 2*n 2*n + 1 2 *gamma(---------) 2 ----------------------- 2*sqrt(pi) 47: simplify_gamman(gamma(3*n)/gamma(n),3); 3*n 3*n + 2 3*n + 1 3 *gamma(---------)*gamma(---------) 3 3 ---------------------------------------- 2*sqrt(3)*pi \end{verbatim} }\noindent \section{Tracing} If you set {\small \begin{verbatim} 48: on zb_trace; \end{verbatim} }\noindent tracing is enabled, and you get intermediate results, see \cite{Koepf}. Example for the Gosper algorithm: {\small \begin{verbatim} 49: gosper(pochhammer(k-n,n),k); k - 1 a(k)/a(k-1):= ----------- k - n - 1 Gosper algorithm applicable p:= 1 q:= k - 1 r:= k - n - 1 degreebound := 0 1 f:= ------- n + 1 Gosper algorithm successful pochhammer(k - n,n)*k ----------------------- n + 1 \end{verbatim} }\noindent \vspace*{3mm}\noindent Example for the Zeilberger algorithm: \vspace*{3mm} {\footnotesize \begin{verbatim} 50: sumrecursion(binomial(n,k)^2,k,n); 2 n F(n,k)/F(n-1,k):= ---------- 2 (k - n) 2 (k - n - 1) F(n,k)/F(n,k-1):= -------------- 2 k Zeilberger algorithm applicable applying Zeilberger algorithm for order:= 1 2 2 2 p:= zb_sigma(1)*k - 2*zb_sigma(1)*k*n + zb_sigma(1)*n + n 2 2 q:= k - 2*k*n - 2*k + n + 2*n + 1 2 r:= k degreebound := 1 2*k - 3*n + 2 f:= --------------- n 2 2 2 3 2 - 4*k *n + 2*k + 8*k*n - 4*k*n - 3*n + 2*n p:= ------------------------------------------------- n Zeilberger algorithm successful 4*sum(n - 1)*n - 2*sum(n - 1) - sum(n)*n 51: off zb_trace; \end{verbatim} }\noindent \section{Global Variables and Switches} The following global variables and switches can be used in connection with the {\tt ZEILBERG} package: \begin{itemize} \item {\tt zb\verb+_+trace}, switch; default setting {\tt off}. Turns tracing on and off. \item {\tt zb\verb+_+direction}, variable; settings: {\tt down}, {\tt up}; default setting {\tt down}. In the case of the Gosper algorithm, either a downward or a forward antidifference is calculated, i.\ e., {\tt gosper} finds $g_k$ with either \[ a_k=g_k-g_{k-1} \quad\quad\mbox{or}\quad\quad a_k=g_{k+1}-g_{k}, \] respectively. In the case of the Zeilberger algorithm, either a downward or an upward recurrence equation is returned. Example: {\small \begin{verbatim} 52: zb_direction:=up$ 53: sumrecursion(binomial(n,k)^2,k,n); sum(n + 1)*n + sum(n + 1) - 4*sum(n)*n - 2*sum(n) 54: zb_direction:=down$ \end{verbatim} }\noindent \item {\tt zb\verb+_+order}, variable; settings: any nonnegative integer; default setting~{\tt 5}. Gives the maximal order for the recurrence equation that {\tt sumrecursion} searches for. \item {\tt zb\verb+_+factor}, switch; default setting {\tt on}. If {\tt off}, the factorization of the output usually producing nicer results is suppressed. \item {\tt zb\verb+_+proof}, switch; default setting {\tt off}. If {\tt on}, then several intermediate results are stored in global variables: \item {\tt gosper\verb+_+representation}, variable; default setting {\tt nil}. If a {\tt gosper} command is issued, and if the Gosper algorithm is applicable, then the variable {\tt gosper\verb+_+representation} is set to the list of polynomials (with respect to $k$) {\tt \{p,q,r,f\}} corresponding to the representation \[ \frac{a_k}{a_{k-1}}=\frac{p_k}{p_{k-1}}\,\frac{q_k}{r_k} \;, \quad\quad\quad g_k=\frac{q_{k+1}}{p_k}\,f_k\,a_k \;, \] see \cite{Gos}. Examples: {\small \begin{verbatim} 55: on zb_proof; 56: gosper(k*factorial(k),k); (k + 1)*factorial(k) 57: gosper_representation; {k,k,1,1} 58: gosper( 1/(k+1)*binomial(2*k,k)/(n-k+1)*binomial(2*n-2*k,n-k),k); ((2*k - n + 1)*(2*k + 1)*binomial( - 2*(k - n), - (k - n)) *binomial(2*k,k))/((k + 1)*(n + 2)*(n + 1)) 59: gosper_representation; {1, (2*k - 1)*(k - n - 2), (2*k - 2*n - 1)*(k + 1), - (2*k - n + 1) ------------------} (n + 2)*(n + 1) \end{verbatim} }\noindent \item {\tt zeilberger\verb+_+representation}, variable; default setting {\tt nil}. If a {\tt sumrecursion} command is issued, and if the Zeilberger algorithm is successful, then the variable {\tt zeilberger\verb+_+representation} is set to the final Gosper representation used, see \cite{Koornwinder}. \end{itemize} \section{Messages} The following messages may occur: \begin{itemize} \item {\tt ***** Gosper algorithm:\ no closed form solution exists} Example input: {\tt gosper(factorial(k),k)}. \item {\tt ***** Gosper algorithm not applicable} Example input: {\tt gosper(factorial(k/2),k)}. The term ratio $a_k/a_{k-1}$ is not rational. \item {\tt ***** illegal number of arguments} Example input: {\tt gosper(k)}. \item {\tt ***** Zeilberger algorithm fails.\ Enlarge zb\verb+_+order} Example input: {\tt sumrecursion(binomial(n,k)*binomial(6*k,n),k,n)} For this example a setting {\tt zb\verb+_+order:=6} is needed. \item {\tt ***** Zeilberger algorithm not applicable} Example input: {\tt sumrecursion(binomial(n/2,k),k,n)} One of the term ratios $f(n,k)/f(n-1,k)$ or $f(n,k)/f(n,k-1)$ is not rational. \item {\tt ***** SOLVE given inconsistent equations} You can ignore this message that occurs with Version 3.5. \end{itemize} \begin{thebibliography}{99} \bibitem{Gos} Gosper Jr., R.\ W.: Decision procedure for indefinite hypergeometric summation. Proc.\ Natl.\ Acad.\ Sci.\ USA {\bf 75}, 1978, 40--42. \bibitem{Koepf} Koepf, W.: Algorithms for the indefinite and definite summation. Konrad-Zuse-Zentrum Berlin (ZIB), Preprint SC 94-33, 1994. \bibitem{Koornwinder} Koornwinder, T.\ H.: On Zeilberger's algorithm and its $q$-analogue: a rigorous description. J.\ of Comput.\ and Appl.\ Math.\ {\bf 48}, 1993, 91--111. \bibitem{NSU} Nikiforov, A.\ F., Suslov, S.\ K,\ and Uvarov, V.\ B.: {\sl Classical orthogonal polynomials of a discrete variable.} Springer-Verlag, Berlin--Heidelberg--New York, 1991. \bibitem{PS} Paule, P.\ and Schorn, M.: A {\sc Mathematica} version of Zeilberger's algorithm for proving binomial coefficient identities. J.\ Symbolic Computation, 1994, to appear. \bibitem{SR} Problem 94--2, SIAM Review {\bf 36}, March 1994. \bibitem{Strehl2} Strehl, V.: Binomial sums and identities. Maple Technical Newsletter {\bf 10}, 1993, 37--49. \bibitem{Wil1} Wilf, H.\ S.: {\sl Generatingfunctionology}. Academic Press, Boston, 1990. \bibitem{Wilf} Wilf, H.\ S.: Identities and their computer proofs. ``SPICE'' Lecture Notes, August 31--September 2, 1993. Anonymous ftp file {\tt pub/wilf/lecnotes.ps} on the server {\tt ftp.cis.upenn.edu}. \bibitem{Zei2} Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities. Discrete Math.\ {\bf 80}, 1990, 207--211. \bibitem{Zei3} Zeilberger, D.: The method of creative telescoping. J.\ Symbolic Computation {\bf 11}, 1991, 195--204. \end{thebibliography} \end{document}