

%multiZ.tex:
%%a Plain TeX file by Moa Apagodu and Doron Zeilberger (13 pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms
}
\centerline
{and the}
\centerline
{Sharpening of Wilf-Zeilberger Theory}
\rm
\bigskip
\centerline{ {\it
Moa APAGODU${}^1$ and Doron ZEILBERGER
\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt [mohamudm, zeilberg] at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde [mohamudm, zeilberg]/.}
\hfill \break
First version: Dec. 8, 2004.
This version: Sept. 7, 2005.
Accompanied by Maple packages: {\eighttt MultiZeilberger},
{\eighttt MultiZeilbergerDen}, {\eighttt qMultiZeilberger},
{\eighttt MultiAlmkvistZeilberger}, and {\eighttt SMAZ}, 
available from
\hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde  zeilberg/mamarim/mamarimhtml/multiZ.html}.
Supported in part by the NSF.
The former name (changed Aug. 2005) of M. Apagodu was M. Mohammed.
}
}
}

\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
{\bf Dedicated to Amitai Regev (b. Dec. 7, 1940)}

{\bf Amitai Regev and Integrals and Sums}

Superficially, this article, dedicated with friendship and admiration to
Amitai Regev, has nothing to do with either Polynomial Identity Rings,
Representation Theory, or Young tableaux, to all of 
which he made so many outstanding contributions.
But anyone who knows even a little about Amitai Regev's 
remarkable and versatile research, would know that
both sums (and multi-sums!), and especially integrals (and multi-integrals!)
show up very frequently, e.g. see [R], where one of us (DZ) collaborated
in the apppendix that consisted in an explicit evaluation of a certain
multi-integral. We should also mention that back in the early eighties,
Amitai, together with William Beckner [BR], deduced the then wide-open
Macdonald-Mehta conjecture for the classical root systems B-D from
Selberg's integral, a fact that was acknowledged in [M]
(albeit with characteristic Macdonaldian understatement). 
Hence, it is clear
that sums, multisums, integrals, and multi-integrals, are Amitai's
bread and butter, and also cup of tea, so the present work has the
potential to help him in his future research.



{\bf A Multi-Variable Zeilberger Algorithm}

{\bf Notation.} For $k$ integer,
$(z)_k:=z(z+1) \dots (z+k-1)$, if $k \geq 0$
and $(z)_k:=1/(z+k)_{-k}$ if $k<0$.
In order to avoid too many subscripts in this article, we will
denote $(z)_k$ by $RF(z\,,\,k)$. For any polynomial in $(k_1, \dots, k_r)$
and possibly other variables, $deg(f)$ denotes the {\bf total degree}
w.r.t. $(k_1, \dots, k_r)$.

{\bf Theorem mZ.} Let
$$
F(n;k_1, \dots, k_r)=POL(n;k_1, \dots, k_r) \cdot H(n; k_1, \dots, k_r) \quad ,
\eqno(MultiProperHypergeometric)
$$
where $POL(n;k_1, \dots, k_r)$  is a polynomial in $(n,k_1, \dots, k_r)$ and
$$
H(n; k_1, \dots, k_r)=
{{\prod_{j=1}^A RF(a''_j \, , \, a'_jn+\sum_{i=1}^r a_{ji} k_i)}
\over
{\prod_{j=1}^C RF(c''_j \, , \, c'_jn+\sum_{i=1}^r c_{ji} k_i)}
}\prod_{i=1}^r z_i^{k_i} \quad,
\eqno(MultiPureHypergeometric)
$$
where the $a'_j,c'_j$ are {\it non-negative} integers and the
$a_{ji}, c_{ji}$ are {\it integers}, while $a''_j,c''_j$ and
$z_1, \dots, z_r$ are {\it commuting indeterminates}.
Then there exists an integer $L$, to be {\it explicitly} constructed in
the course of the proof, and there exist
polynomials in $n$, $e_0(n), e_1(n), \dots, e_L(n)$,{
{\it not all zero}, and there also exist
$r$ rational functions of $(n, k_1, \dots, k_r)$,
$R_i(n;k_1, \dots, k_r)$ ($i=1,\dots, r$), such that
$$
G_i(n;k_1, \dots, k_r):=R_i(n;k_1, \dots, k_r)F(n;k_1, \dots, k_r)
$$
satisfy
$$
\sum_{i=0}^L e_i(n) F(n+i,k)=
\sum_{i=1}^r [G_i(n; k_1, \dots, k_{i-1},k_i+1, k_{i+1}, \dots, k_r)-
G_i(n; k_1, \dots, k_r)] \quad.
\eqno(WZtuple)
$$

{\bf Proof.} Let
$$
\overline{H}(n; k_1, \dots, k_r)=
{{\prod_{j=1}^A RF(a''_j \, , \, a'_jn+\sum_{i=1}^r a_{ji} k_i)}
\over
{\prod_{j=1}^C RF(c''_j \, , \, c'_j(n+L)+\sum_{i=1}^r c_{ji} k_i)}
}\prod_{i=1}^r z_i^{k_i} \quad,
$$
and for $i=1,\dots,r$,
$$
f_i(k_1, \dots, k_r)=
\prod_{ {{1 \leq j \leq A} \atop {a_{ji}>0}} } RF(a'_jn+a''_j+\sum_{i=1}^r a_{ji}k_i \, , \, a_{ji})
\prod_{ {{1 \leq j \leq C} \atop {c_{ji}<0}} } RF(c'_j(n+L)+c''_j+c_{ji}
+\sum_{i=1}^r c_{ji}k_i \, , \, -c_{ji})
\quad ,
$$
and
$$
g_i(k_1, \dots, k_r)=
\prod_{ {{1 \leq j \leq A} \atop {a_{ji}<0}} } RF(a'_jn+a''_j+a_{ji}
+\sum_{i=1}^r a_{ji}k_i \, , \, -a_{ji})
\prod_{ {{1 \leq j \leq C} \atop {c_{ji}>0}} }
RF(c'_j(n+L)+c''_j +\sum_{i=1}^r c_{ji}k_i \, , \, c_{ji})
\quad .
$$
Note that
$$
{
{\overline{H}(n;k_1, \dots, k_{i-1},k_i+1,k_{i+1},\cdots , k_r)} \over
{\overline{H}(n;k_1, \dots,  k_r)}
}=
{{f_i(k_1, \dots, k_r)} \over {g_i(k_1, \dots, k_r)} } z_i
\quad .
$$
Write
$$
G_i(n,k):=g_i(k_1, \dots, k_{i-1},k_i-1,k_{i+1}, \dots, k_r) \cdot
X_i(k_1, \dots, k_r) \cdot
\overline{H}(n;k_1, \dots, k_r) \cdot
\quad(Ansatz)
$$
Substituting into $(WZtuple)$ and dividing both sides by $\overline{H}(n;k_1, \dots, k_r)$, shows
that it is equivalent to
$$
\sum_{i=1}^r
[z_i \cdot f_i(k_1, \dots, k_r)
X_i(k_1, \dots, k_{i-1},k_i+1,k_{i+1}, \dots, k_r)-
g_i(k_1, \dots, k_{i-1},k_i-1,k_{i+1}, \dots, k_r) X_i(k_1, \dots, k_r)]
$$
$$
\, - \,
h(k_1, \dots, k_r) =0 \quad,
\eqno(MultiGosper)
$$
where
$$
h(k_1, \dots, k_r) :=
\sum_{i=0}^L e_i(n) POL(n+i; k_1, \dots, k_r) \cdot
{{H(n+i;k_1, \dots, k_r)} \over { \overline{H} (n;k_1, \dots, k_r) } } \quad.
$$
Note that $h(k_1, \dots, k_r)$ is a polynomial since
$$
{{H(n+i;k_1, \dots, k_r)} \over { \overline{H} (n;k_1, \dots, k_r) } }=
\prod_{j=1}^A RF(a''_j+ a'_j n + \sum_{i=1}^r a_{ji} k_i \, , \, ia'_j)
\prod_{j=1}^C RF(c''_j+ c'_j (n+i) + \sum_{i=1}^r
c_{ji} k_i \, , \, (L-i)c'_j) \quad .
$$
Now write each of the $X_i$'s in generic form, with {\it undetermined coefficients},
as polynomials in
$k_1, \dots, k_r$ of degree $M:=deg(h)-\max(\{deg(f_i),deg(g_i)\})$.
Plug them all into $(MultiGosper)$, expand this
gigantic polynomial of $k_1, \dots, k_r$, and equate
{\bf all} the coefficients to zero, getting a huge
{\bf system of linear homogeneous equations} whose
unknowns are the $e_i(n)$'s and the coefficients of the
$X_i$'s.
There are $r {{M+r} \choose {r}}+L+1$
unknowns and ${{deg(h)+r} \choose {r}}$ equations.
In order to {\bf guarantee} a {\it not-all-zero} solution we
must insist that $\#$unknowns$>$$\#$equations.
So choose $L$ to be
the smallest integer such that
$$
r {{M+r} \choose {r}}+L+1 >
{{deg(h)+r} \choose {r}} \quad,
$$
in other words
$$
L \geq
{{deg(h)+r} \choose {r}}
- r {{M+r} \choose {r}} \quad.
$$
We will now show that such an $L$ exists. Indeed,
$$
deg(h)=deg(POL)+L \cdot \max(\sum_{j=1}^A a'_j, \sum_{j=1}^C c'_j)=
b_0+b_1 L \quad ,
$$
for some specific positive integers $b_0,b_1$. Also
$$
b_2:=max(\{deg(f_i), deg(g_i)\}) \quad
$$
is some specific positive integer (independent of $L$).
We need to find an $L$ such that
$$
r {{b_0+b_1L-b_2 +r} \choose {r} }
-
{{b_0+b_1L+r} \choose {r}} +L \geq 0
\quad.
$$
For $r=1$ we get that $L= b_2$ will do, and for $r>1$ the
left side
is a polynomial of $L$
of degree $r$ with a {\it leading coefficient} that is
{\bf positive}, hence tends to $\infty$ when
$L \rightarrow \infty$,
Hence the inequality holds for sufficiently large $L$,
and the smallest such $L$ is our desired (sharp!) upper bound.

However, so far, we only ruled out the scenario that
{\it all} the $e_i(n)$'s {\bf and} {\it all} the
$X_i$'s are {\bf all} equal to $0$. Can it happen that all the $e_i(n)$'s
are equal to $0$? No way! We are doing things {\it generically}, in particular with
generic $z_i$'s, and if all the $e_i(n)$'s are zero, 
they would have to be {\it identically zero} as a function of
the $z_i$'s and all the other generic (symbolic) parameters $a''_j$ etc.
In particular if we make all the $z_i$'s zero except for a single one,
reducing the multi-sum to a {\it single sum}, 
then all the $e_i(n)$'s would still have to be identically zero.
This scenario has been ruled out in [MZ].
\halmos.

{\bf Remark 1.} The condition that the $a'_j$'s and $c'_j$'s
are {\it non-negative} integers is w.l.o.g., since one
can obtain an equivalent summand with these properties by
{\bf shadowing} (see [MZ]).

{\bf Remark 2.} Theorem mZ is both
of theoretical and practical interest. The former because it
considerably improves the upper bound for the order of the
recurrence established in [WZ]. The latter
since it gives an {\it efficient} algorithm
for computing recurrences, superseding the ad-hoc pseudo algorithm
that accompanied [WZ]. 

{\bf Remark 3.} In {\it specific} situations (as opposed to the
{\it generic} case), one may be able to get a smaller $L$,
by taking the $X_i$'s to be rational functions, rather
than mere polynomials. This is implemented in the Maple
package {\tt MultiZeilbergerDen}, where the user is allowed to pick the
denominators.

{\bf A Multi-Variable q-Zeilberger Algorithm}

{\bf q-Notation.} For $k$ integer,
$[a]_k:=(1-q^a)(1-q^{a+1})\cdots (1-q^{a+k-1})$, if $k \geq 0$
and $[a]_k:=1/[a+k]_{-k}$ if $k<0$.
In order to avoid too many subscripts, we will
denote $[a]_k$ by $qRF(a\,,\,k)$.

{\bf Theorem qmZ.} Let
$$
F(n;k_1, \dots, k_r)=POL(n;k_1, \dots, k_r)
\cdot H(n; k_1, \dots, k_r) \quad ,
\eqno(qMultiProperHypergeometric)
$$
where $POL(n;k_1, \dots, k_r)$  is a Laurent polynomial in $(q^n,q^{k_1}, \dots, q^{k_r})$,
and
$$
H(n; k_1, \dots, k_r)=
{{\prod_{j=1}^A qRF(a''_j \, , \, a'_jn+\sum_{i=1}^r a_{ji} k_i)}
\over
{\prod_{j=1}^C qRF(c''_j \, , \, c'_jn+\sum_{i=1}^r c_{ji} k_i)}
}\cdot q^{Q(n;k_1, \dots, k_r)} \cdot\prod_{i=1}^r z_i^{k_i} \quad,
\eqno(qMultiPureHypergeometric)
$$
where the $a'_j,c'_j$ are {\it non-negative} integers and the
$a_{ji}, c_{ji}$ are {\it integers}, while $a''_j,c''_j$ and
$z_1, \dots, z_r$ are {\it commuting indeterminates}, and
$Q(n;k_1, \dots, k_r)$ is a quadratic form in $(n,k_1, \dots, k_r)$.
Then there exists an integer $L$, to be {\it explicitly} constructed in
the course of the proof, and there exist $L+1$
polynomials in $q^n$, $e_0(q^n), e_1(q^n), \dots, e_L(q^n)$,
{\it not all zero}, and $r$ rational functions of $(q^n, q^{k_1}, \dots, q^{k_r})$,
$R_i(n;k_1, \dots, k_r)$ ($i=1,\dots, r$) such that
$$
G_i(n;k_1, \dots, k_r):=R_i(n;k_1, \dots, k_r)F(n;k_1, \dots, k_r)
$$
satisfy
$$
\sum_{i=0}^L e_i(q^n) F(n+i,k)=
\sum_{i=1}^r [G_i(n; k_1, \dots, k_{i-1},k_i+1, k_{i+1}, \dots, k_r)-
G_i(n; k_1, \dots, k_r)] \quad.
\eqno(qWZtuple)
$$


{\bf Plan of Proof:} q-analogize the proof of Theorem mZ,
in the same way as it was carried out for the single-sum case
in [MZ]. \halmos


{\bf Remark 4.} In many cases one can get a lower order, $L$, for
the recurrence satisfied by the sum $a(n):=\sum_{\bf k}F(n; {\bf
k})$ , by replacing $F(n; {\bf k})$ , by its {\bf Paule
Symmetrization} [P] (adapted to many variables).

\vfill\eject

{\bf Sharp Upper Bounds for the Almkvist-Zeilberger Algorithm}

This section is a  discrete-continuous analog of [MZ].
It simplifies (part of) [AZ], and provides a sharp
upper bound for the order of the outputted recurrence.

{\bf Notation.} If $f$ is  function of the continuous variable
$x$ (among possibly other continuous and/or discrete variables),
then $D_x f$ denotes the derivative of $f$ with respect to $x$,
in other words $D_x f:= {{\partial f} \over { \partial x}}$.

{\bf Theorem AZ.} Let
$$
F(n,x)=POL(n,x) \cdot H(n,x) \quad ,
\eqno(DiscreteContHypergeometric)
$$
where  $POL(n,x)$ is a polynomial of $(n,x)$,  and
$$
H(n,x)=e^{a(x)/b(x)} \cdot
\left ( \prod_{p=1}^P {S_p(x)}^{\alpha_p} \right )\cdot
\left ( { {s(x)} \over {t(x)} } \right )^n \quad ,
\eqno(PureDiscreteContHypergeometric)
$$
where $a(x),b(x),s(x),t(x)$ and
$S_p(x)$ ($1 \leq p \leq P$) are {\it polynomials} of $x$, while
the $\alpha_p$'s are commuting {\it indeterminates}.
Let
$$
L=deg(b)+deg(s)+deg(t)+ \left ( \sum_{p=1}^P deg(S_p) \right ) + max( deg(a),deg(b))-1 \quad,
$$
then there exist $L+1$ polynomials in $n$, $e_0(n),e_1(n), \dots , e_L(n)$,
{\it not all zero}, and a rational function $R(n,x)$ such that
$G(n,x):=R(n,x)F(n,x)$ satisfies
$$
\sum_{i=0}^L e_i(n) F(n+i,x)= D_x G(n,x) \quad.
\eqno(GertDoron)
$$
If $F(n,\alpha)=0$  and $F(n,\beta)=0$
(and hence $G(n,\alpha)=0$  and $G(n,\beta)=0$), it follows, by integrating
from $x=\alpha$ to $x=\beta$ that
$$
a(n):=\int_{\alpha}^{\beta} F(n,x) dx \quad,
$$
satisfies the linear recurrence equation with polynomial coefficients
$$
\sum_{i=0}^L e_i(n) a(n+i)= 0 \quad.
$$
{\bf Proof}: Let $L$, for now, be {\it any} non-negative integer.
Let
$$
\overline{H} (n,x)=e^{a(x)/b(x)} \cdot
\left ( \prod_{p=1}^P {S_p(x)}^{\alpha_p} \right ) \cdot
{ {s(x)^n} \over {t(x)^{n+L}} }  \quad .
$$
We have
$$
\sum_{i=0}^L e_i(n) F(n+i,x)=
h(x)
\cdot \overline{H} (n,x) \quad ,
$$
where
$$
h(x):= \sum_{i=0}^L e_i(n) POL(n+i,x) s(x)^i t(x)^{L-i} \quad .
$$
Let $q(x)$ and $r(x)$ be the numerator and denominator, respectively, of
the logarithmic derivative of $\overline{H}(n,x)$, i.e.
$$
{ {D_x \overline{H}(n,x)} \over {\overline{H}(n,x)} }=
{{q(x)} \over {r(x)}} \quad .
$$
Write
$$
G(n,x)=\overline{H}(n,x) \cdot r(x) \cdot X(x) \quad,
\eqno(Ansatz)
$$
where $X(x)$ is a polynomial to be determined.
Now $(GertDoron)$ is equivalent to
$$
(r'(x)+q(x)) \cdot X(x) +r(x) X'(x)= h(x) \quad .
\eqno(ContGosper)
$$
Let $M:=deg(h)- max( deg(r'+q), deg(r)-1)$, and write $X(x)$
as a polynomial in $x$ of degree $M$ with
{\it undetermined coefficients}. Plugging this into
$(ContGosper)$, and equating coefficients, results in
$deg(h)+1$ equations for $L+M+2$ unknowns. In order to guarantee
a solution, we need
$$
L+M+2 > deg(h)+1 \quad,
$$
in other words
$$
(L+M+2) - (deg(h)+1) \geq 0 \quad,
$$
in other words,
$$
L \geq max( deg(r'+q), deg(r)-1) \quad .
$$
We leave it to the reader to verify that the expression on the right is indeed
$$
L=deg(b)+deg(s)+deg(t)+
\left ( \sum_{p=1}^P deg(S_p) \right )
+ max( deg(a),deg(b))-1 \quad. \halmos
$$


{\bf A Multi-Variable Almkvist-Zeilberger Algorithm}

The above theorem, and {\bf algorithm}, can be
extended to many variables as follows.

{\bf Theorem mAZ.} Let
$$
F(n;x_1, \dots , x_d)=
POL(n;x_1, \dots, x_d) \cdot H(n;x_1, \dots, x_d) \quad ,
\eqno(MultiDiscreteContHypergeometric)
$$
where  $POL(n;x_1, \dots, x_d)$ is a polynomial of $(n,x_1, \dots, x_d)$,  and
$$
H(n;x_1, \dots, x_d)=
e^{a(x_1, \dots,x_d)/b(x_1, \dots, x_d)} \cdot
\left ( \prod_{p=1}^P {S_p(x_1, \dots, x_d)}^{\alpha_p} \right )\cdot
\left ( { {s(x_1, \dots, x_d)} \over {t(x_1, \dots, x_d)} } \right )^n \quad ,
\eqno(PureDiscreteContHypergeometric)
$$
where $a(x_1, \dots, x_d),b(x_1, \dots, x_d)$,
$s(x_1, \dots, x_d),t(x_1, \dots, x_d)$ and
$S_p(x_1, \dots, x_d)$ ($1 \leq p \leq P$) are {\it polynomials} of $(x_1, \dots, x_d)$, while
the $\alpha_p$'s are commuting {\it indeterminates}.
There exists a non-negative integer $L$, to be constructed in the proof, and
there exist
$L+1$ polynomials in $n$, $e_0(n),e_1(n), \dots , e_L(n)$,
{\it not all zero}, and  there also exist
$d$ rational functions $R_i(n;x_1, \dots, x_d)$
($i=1, \dots ,d$) such that
$$
G_i(n;x_1, \dots, x_d):=R_i(n;x_1, \dots,x_d)F(n;x_1, \dots, x_d)
$$
satisfy
$$
\sum_{i=0}^L e_i(n) F(n+i;x_1, \dots, x_d)= \sum_{i=1}^d D_{x_i} G_i(n;x_1, \dots, x_d) \quad.
\eqno(MultiGertDoron)
$$

If $F(n; \pm \infty)=0$ (and hence $G(n; \pm \infty)=0$) it follows, by integrating over $[-\infty,\infty]^d$, that
$$
a(n):=\int_{-\infty}^{\infty} \dots
\int_{-\infty}^{\infty}
F(n;x_1, \dots, x_d) dx_1 \dots dx_d \quad,
$$
satisfies the linear recurrence equation with polynomial coefficients
$$
\sum_{i=0}^L e_i(n) a(n+i)= 0 \quad.
$$
{\bf Sketch of Proof and Algorithm.}
Let $L$, for now, be {\it any} non-negative integer.
Let
$$
\overline{H} (n;x_1, \dots, x_d)=
e^{a(x_1, \dots,x_d)/b(x_1, \dots, x_d)} \cdot
\left (
\prod_{p=1}^P {S_p(x_1, \dots, x_d)}^{\alpha_p} \right )
\cdot
{ {s(x_1, \dots, x_d)^n} \over {t(x_1, \dots, x_d)^{n+L}} }  \quad .
$$
We have
$$
\sum_{i=0}^L e_i(n) F(n+i;x_1, \dots, x_d)=
h(x_1, \dots, x_d)
\cdot \overline{H} (n;x_1, \dots, x_d) \quad ,
$$
where
$$
h(x_1, \dots, x_d):= \sum_{i=0}^L e_i(n) POL(n+i;x_1, \dots, x_d) s(x_1, \dots, x_d)^i
t(x_1, \dots, x_d)^{L-i} \quad .
$$
For $i=1,\dots,d$, let
$q_i(x_1, \dots, x_d)$ and $r_i(x_1, \dots. x_d)$
be the numerator and denominator, respectively, of
the logarithmic derivative of $\overline{H}(n;x_1, \dots, x_d)$ w.r.t. $x_i$:
$$
{ {D_{x_i} \overline{H}(n;x_1, \dots, x_d)} \over {\overline{H}(n;x_1, \dots, x_d)} }=
{{q_i(x_1, \dots, x_d)} \over {r_i(x_1, \dots, x_d)}} \quad .
$$
Write, for $i=1, \dots, d$,
$$
G_i(n;x_1, \dots, x_d)=\overline{H}(n;x_1, \dots, x_d) \cdot
r_i(x_1,\dots, x_d ) \cdot X_i(x_1, \dots, x_d) \quad,
\eqno(Ansatz)
$$
where $X_i(x_1, \dots , x_d)$ are polynomials to be determined.
Now $(MultiGertDoron)$ is equivalent to
$$
\sum_{i=1}^d [
D_{x_i}r_i(x_1, \dots, x_d)+q_i(x_1, \dots, x_d)] \cdot
X_i(x_1, \dots, x_d) +r_i(x_1, \dots, x_d)
\cdot D_{x_i}X_i(x_1, \dots, x_d)
$$
$$
= h(x_1, \dots, x_d) \quad.
\eqno(MultiContGosper)
$$
The rest of the proof of the existence of $L$ is analogous to the
proof of Theorem mZ, since the degree of $h$ is of the form
`` {\bf integer+ (positive integer)$\cdot L$}'', and for sufficiently large $L$,
the number of unknowns will exceed the number of equations, and we will
be guaranteed a solution. Once again, by genericity, it is not possible for
all the $e_i(n)$'s to be zero. \halmos

{\bf Remark 6.} Theorem mAZ sharpens and improves on the work of
Akalu Tefera[T], which, in turn, was a great improvement on the
pseudo algorithm for multi-integration that accompanied [WZ].


{\bf Remark 7.} In many cases in practice, one can reduce the
order ($L$), by replacing $(Ansatz)$ by
$$
G_i(n;x_1, \dots, x_d)=\overline{H}(n;x_1, \dots, x_d) \cdot
X_i(x_1, \dots, x_d) \quad,
\eqno(Ansatz')
$$
in other words,
 not assuming that $G_i/\overline{H}$ is divisible by $r_i$.
This is how it is done in {\tt MultiAlmkvistZeilberger}.

{\bf Differential Operators}

Theorems cAZ and cmAZ below are analogs of AZ and mAZ that
treat the case where the integrand's
arguments are {\it all} continuous, including the `parameter' variable
that is not being integrated on. In this case, of course, the
output satisfies a linear {\it differential} equation with polynomial
coefficients. Theorems cAZ and cmAZ are not yet implemented in Maple.

{\bf Theorem cAZ.} Let
$$
F(x,y)=POL(x,y)\cdot H(x,y) \eqno(PureContHypergeometric)
$$
where $POL(x,y)$ is a polynomial of $(x,y)$, and
$$
H(x,y)=e^{\frac{a(x,y)}{b(x,y)}} \cdot \left(
\prod_{p=1}^{P}S_p(x,y)^{\alpha _p}\right) , \quad
\eqno(PureContHypergeometric)\, \, ,
$$
where $a(x,y),b(x,y)$ and $S_p(x,y) \, (1\leq p \leq P)$ are
polynomials of $(x,y)$ while the $ \alpha _p$ are commuting
indeterminates.

Let
$$
L:= deg(b)+\sum_{p=1}^{P}deg(S_p)+max(deg(a), deg(b))-1\, \, .
$$

There exist $L+1$ polynomials, $\displaystyle{e_0(x),
e_0(x),\ldots, e_L(x),}$ not all zero, and rational function
$R(x,y)$ such that  $\displaystyle{G(x,y):=R(x,y)F(x,y)}$
satisfies

$$
\sum_{i=0}^L e_i(x)D_{x}^iF(x,y)=D_xG(x,y),\quad.
\eqno(ContGertDoron)
$$

If $F(x,\alpha)=0$  and $F(x,\beta)=0$ (and hence $G(x,\alpha)=0$
and $G(x,\beta)=0$), it follows, by integrating from $y=\alpha$ to
$y=\beta$ that
$$
a(x):=\int_{\alpha}^{\beta} F(x,y) dy \quad,
$$
satisfies the linear differential equation with polynomial
coefficients
$$
\sum_{i=0}^L e_i(x) D^i_xa(x)= 0 \quad.
$$

{\bf Sketch of the Proof}: The proof makes repeated use of
Leibnitz rule together with induction. Let

$$
\overline {H}(x,y)= \frac{e^{\frac{a(x,y)}{b(x,y)}}} {b(x,y)^{2L}}
\cdot \left(\prod_{p=1}^{P}S_p(x,y)^{\alpha _p-L}\right ) \, \, .
$$

We have
$$
\sum_{i=0}^L e_i(x) F(x,y)= h(x) \cdot \overline{H} (x,y) \quad ,
$$
where $h(x)$ is the expression
$$
\sum_{i=0}^{L}a_i(x)\sum_{{k_1+k_2+k_3=i} \atop {k_i\geq 0}} {i
\choose k_1,k_2,k_3} (D_x^{k_1}POL(x,y))\left
(\prod_{p=1}^{P}S_p(x,y)^{L-k_2}\right )\cdot T_{k_2}(x,y) \cdot
b(x,y)^{2(L-k_3)}\cdot m_{k_3}(x,y) \, \, ,
$$
where  $m_{k_3}(x,y)$ is a polynomial in $(x,y)$ for which
$$
D_x^{k_2}\left (\prod_{p=1}^{P}{S_p(x,y)^{\alpha _p}}\right)=
\left (\prod_{p=1}^{P}S_p(x,y)^{\alpha_p-k_2}\right ) \cdot
T_{k_2}(x,y) \, \, .
$$
and $T_{k_3}(x,y)$ is a polynomial in $(x,y)$ such that
$$
D_x^{k_3}\left( e^{a(x,y)/b(x,y)}\right)=  {{m_{k_3}(x,y)} \over
{b(x,y)^{2k_3}}}e^{a(x,y)/b(x,y)}  \, \, ,
$$
respectively.

Let $q(x)$ and $r(x)$ be the numerator and denominator,
respectively, of the logarithmic derivative of
$\overline{H}(x,y)$, i.e.
$$
{{D_x \overline{H}(x,y)} \over {\overline{H}(x,y)}}= {{q(x)} \over
{r(x)}} \quad .
$$
Write
$$
G(x,y)=\overline{H}(x,y) \cdot r(x) \cdot X(x) \quad,
\eqno(Ansatz)
$$
where $X(x)$ is a polynomial to be determined. Now
$(ContGertDoron)$ is equivalent to
$$
(r'(x)+q(x)) \cdot X(x)+r(x) X'(x)= h(x) \quad . \eqno(ContGosper)
$$
Let $M:=deg(h)- max( deg(r'+q), deg(r)-1)$, and write $X(x)$ as a
polynomial in $x$ of degree $M$ with {\it undetermined
coefficients}. Plugging this into $(ContGosper)$, and equating
coefficients, results in $deg(h)+1$ equations for $L+M+2$
unknowns. In order to guarantee a solution, we need
$$
L+M+2 > deg(h)+1 \quad,
$$
in other words
$$
(L+M+2) - (deg(h)+1) \geq 0 \quad,
$$
in other words,
$$
L \geq max( deg(r'+q), deg(r)-1) \quad .
$$
We leave it to the reader to verify that the expression on the
right is indeed
$$
L=deg(b)+max(deg(a), deg(b))+\left ( \sum_{p=1}^P deg(S_p) \right
) -1 \quad. \, \, \halmos
$$

{\bf Theorem cmAZ.} Let
$$
F(x;y_1, \dots , y_d)= POL(x;y_1, \dots, y_d) \cdot H(x;y_1,
\dots, y_d) \quad , \eqno(MultiContHypergeometric)
$$
where  $POL(x;y_1, \dots, y_d)$ is a polynomial of $(x,y_1, \dots,
y_d)$,  and
$$
H(x;y_1, \dots, y_d)= e^{a(x,y_1, \dots,y_d)/b(x,y_1, \dots, y_d)}
\cdot \left ( \prod_{p=1}^P {S_p(x;y_1, \dots, y_d)}^{\alpha_p}
\right ) \quad , \eqno(MultiPureContHypergeometric)
$$
where $a(y_1, \dots, y_d),b(y_1, \dots, y_d)$, $S_p(y_1, \dots,
y_d)$ ($1 \leq p \leq P$) are {\it polynomials} of $(y_1, \dots,
y_d)$, while the $\alpha_p$'s are commuting {\it indeterminates}.
There exists a non-negative integer $L$, to be constructed in the
proof, and there exist $L+1$ polynomials in $x$, $e_0(x),e_1(x),
\dots , e_L(x)$, {\it not all zero}, and there also exist $d$
rational functions $R_i(x;y_1, \dots, y_d)$ ($i=1, \dots ,d$) such
that
$$
G_i(x;y_1, \dots, y_d):=R_i(x;y_1, \dots,y_d)F(x;y_1, \dots, y_d)
$$
satisfy
$$
\sum_{i=0}^L e_i(x) D^i_xF(x;y_1, \dots, y_d)= \sum_{i=1}^d
D_{x_i} G_i(x;y_1, \dots, y_d) \quad. \eqno(MultiContGertDoron)
$$

If $F(x; \pm \infty)=0$ (and hence $G(x; \pm \infty)=0$) it
follows, by integrating over $[-\infty,\infty]^d$, that
$$
a(x):=\int_{-\infty}^{\infty} \dots \int_{-\infty}^{\infty}
F(x;y_1, \dots, y_d) dy_1 \dots dy_d \quad,
$$
satisfies the linear recurrence equation with polynomial
coefficients
$$
\sum_{i=0}^L e_i(x) D^i_xa(x)= 0 \quad.
$$
{\bf Sketch of Proof and Algorithm.} Let $L$, for now, be {\it
any} non-negative integer. Let

$$
\overline{H} (x;y_1, \dots, y_d)= \frac{e^{a(x;y_1,
\dots,y_d)/b(x;y_1, \dots, y_d)}}{b(x;y_1, \dots, y_d)^{2L}} \cdot
\left ( \prod_{p=1}^P {S_p(x;y_1, \dots, y_d)}^{\alpha_p} \right )
\quad .
$$

We have
$$
\sum_{i=0}^L e_i(x) D^i_xF(x;y_1, \dots, y_d)= h(y_1, \dots, y_d)
\cdot \overline{H} (x;y_1, \dots, y_d) \quad ,
$$
where $h(y_1, \dots, y_d)$ is the expression given by

$$ \sum_{i=0}^{L}a_i(x)\sum_{{k_1+k_2+k_3=i}
\atop {k_i \geq 0}} {i \choose k_1,k_2,k_3}
(D_x^{k_1}POL(x;y_1,\ldots,y_d))\left
(\prod_{p=1}^{P}S_p(x;y_1,\ldots,y_d)^{L-k_2}\right ) \cdot
T_{k_2}(x;y_1,\ldots,y_d) \cdot
$$
$$
b(x;y_1,\ldots,y_d)^{2(L-k_3)}\cdot m_{k_3}(x;y_1,\ldots,y_d)\quad
,
$$

where $T_{k_2}(x;y_1,\ldots,y_d)$ is a polynomial in
$(y_1,\ldots,y_d)$ for which

$$
D_x^{k_2}\left (\prod_{p=1}^{P}{S_p(x;y_1,\ldots,y_d)^{\alpha
_p}}\right)= \left
(\prod_{p=1}^{P}S_p(x;y_1,\ldots,y_d)^{\alpha_p-k_2}\right ) \cdot
T_{k_2}(x;y_1,\ldots,y_d) \, \, .
$$
and $m_{k_3}(x;y_1,\ldots,y_d)$ is a polynomial in
$(x;y_1,\ldots,y_d)$ such that
$$
D_x^{k_3}\left (
e^{a(x;y_1,\ldots,y_d)/b(x;y_1,\ldots,y_d)}\right)=
{{m_{k_3}(x;y_1,\ldots,y_d)} \over
{b(x;y_1,\ldots,y_d)^{2k_3}}}e^{a(x;y_1,\ldots,y_d)/b(x;y_1,\ldots,y_d)}
 \, \, ,
$$
respectively.

For $i=1,\dots,d$, let $q_i(y_1, \dots, y_d)$ and $r_i(y_1, \dots.
y_d)$ be the numerator and denominator, respectively, of the
logarithmic derivative of $\overline{H}(x;y_1, \dots, y_d)$ w.r.t.
$y_i$:
$$
{ {D_{y_i} \overline{H}(x;y_1, \dots, y_d)} \over
{\overline{H}(x;y_1, \dots, y_d)} }= {{q_i(y_1, \dots, y_d)} \over
{r_i(y_1, \dots, y_d)}} \quad .
$$
Write, for $i=1, \dots, d$,
$$
G_i(x;y_1, \dots, y_d)=\overline{H}(x;y_1, \dots, y_d) \cdot
r_i(y_1,\dots, y_d ) \cdot X_i(y_1, \dots, y_d) \quad,
\eqno(Ansatz)
$$
where $X_i(y_1, \dots , y_d)$ are polynomials to be determined.
Now $(MultiContGertDoron)$ is equivalent to
$$
\sum_{i=1}^d [ D_{y_i}r_i(y_1, \dots, y_d)+q_i(y_1, \dots, y_d)]
\cdot X_i(y_1, \dots, y_d) +r_i(y_1, \dots, y_d) \cdot
D_{y_i}X_i(y_1, \dots, y_d)
$$
$$
= h(y_1, \dots, y_d) \quad. \eqno(MultiContGosper)
$$
The rest of the proof of the existence of $L$ is analogous to the
proof of Theorem mAZ, since the degree of $h$ is of the form ``
{\bf integer+ (positive integer)$\cdot L$}'', and for sufficiently
large $L$, the number of unknowns will exceed the number of
equations, and we will be guaranteed a solution. Once again, by
genericity, it is not possible for all the $e_i(x)$'s to be zero.
\halmos

{\bf Accompanying Maple packages and Examples}

The multi-Zeilberger algorithm, as described in Theorem mZ,
is implemented in the Maple package {\tt multiZeilberger}.
The refined version, where the user is allowed to specify
denominators, is given in {\tt MultiZeilbergerDen}.
The q-multi-Zeilberger algorithm, as stated in theorem
qmZ,  is implemented in the Maple package
{\tt qMultiZeilberger}, while the multi-Almkvist-Zeilberger
algorithm, as described in Theorem mAZ, is contained in
{\tt MultiAlmkvistZeilberger}. Finally
{\tt SMAZ} is a more efficient rendition for {\it symmetric}
integrands.


These five packages are available from the webpage of this
article
\hfill\break
{\tt http://www.math.rutgers.edu/\Tilde  zeilberg/
mamarim/mamarimhtml/multiZ.html}, where there is also
sample input and output. Readers can generate many more
examples on their own.


{\bf REFERENCES}

[AZ] G. Almkvist and D. Zeilberger,
{\it The method of differentiating under the
integral sign}, J. Symbolic Computation {\bf 10} (1990), 571-591.

[BR] W. Beckner and A. Regev, \it
unpublished, untitled, and undated
manuscript, c. 1980\rm

[M] I.G. Macdonald, {\it Some conjectures for root systems},
SIAM J. Math. Anal. {\bf 13}(1982), 988-1007.

[MZ] M. Mohammed and D. Zeilberger,
{\it  Sharp Upper Bounds for the Orders of The Recurrences
Outputted by the Zeilberger and q-Zeilberger Algorithms},
J. Symbolic Computation {\bf 39} (2005), 201-207.

[P] P. Paule,
{\it  Short and easy computer proofs of the Rogers-Ramanujan identities
and of identities of similar type},
Elect. J. of Combinatorics {\bf 1} (1994), R10.

[R]   A. Regev,
{\it   Combinatorial sums, identities and trace identities of the $2\times 2$ matrices},
Adv. in Math. {\bf 46} (1982), 230-240.

[T] A. Tefera,
{\it MultInt, a Maple Package for Multiple Integration by the WZ Method},
J. of Symbolic Computation {\bf34} (2002), 329-353.

[WZ] H.S. Wilf and D. Zeilberger,
{\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math.
{\bf 108} (1992), 575-633.
[available on-line from the authors' websites.]


\end




%On page 9 line 6 from bottom, ...  T_{k_3}}(x,y) ...
%supposed to be ... m_{k_3}}(x,y) ....
