
  
%multiZ.tex: 
%%a Plain TeX file by Mohamud Mohammed and Doron Zeilberger (xx 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 
Mohamud Mohammed{$^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]/.}
First version: Nov. 15, 2004.
Supported in part by the NSF.
} 
}

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

This section is a  discrete-continuous analog of [MZ].

{\bf Theorem} 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)+\sum_{p=1}^P deg(S_p) + 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(x,n)$ 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(x,n) \quad.
\eqno(GertDoron)
$$
If $F(n, \pm \infty)=0$ (and hence $G(n, \pm \infty)=0$) it follows, by integrating
from $-\infty$ to $\infty$ that
$$
a(n):=\int_{-\infty}^{\infty} 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} positive 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(x,n+i)= 
h(x)
\cdot \overline{H} (x,n) \quad ,
$$
where
$$
h(x):= \sum_{i=0}^L e_i(n) POL(n+i,x) s(x)^i t(x)^{n-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)}}
$$
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'(k)= h(x)
\eqno(ContGosper)
$$
Let $M:=deg(h)- max( deg(r'+q), deg(r)+1)$, and write $X(x)$ with
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)+2) \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
$$
L=deg(b)+deg(s)+deg(t)+\sum_{p=1}^P deg(S_p) + max( deg(a),deg(b))-1 \quad. \halmos
$$

{\bf REFERENCES}

\end








