  
%marwz.tex: The Markov-WZ Method (for the ElJC)
%%a Plain TeX file by Mohamud Mohammed and Doron Zeilberger (14 pages)
 
%my macros 
\def\L{{\cal L}}
\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
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end my macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\magnification=\magstep1
\baselineskip=12pt
\hsize=6.3truein
\vsize=8.7truein
\font\footsc=cmcsc10 at 8truept
\font\footbf=cmbx10 at 8truept
\font\footrm=cmr10 at 10truept
\footline={\footsc the electronic journal of combinatorics
   {\footbf 11} (2004), \#R00\hfil\footrm\folio}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The further structure of the front page need not be exactly as below,
%% but the header must contain the names and addresses of the authors
%% as well as the submission and acceptance dates.

\font\bigrm=cmr12 at 14pt
\centerline{\bigrm The Markov-WZ Method}

\bigskip\bigskip

\centerline{Mohamud MOHAMMED and Doron ZEILBERGER\footnote*{Thanks to
Herb Wilf, the referee, Ben Kalba, and Tipesh Gadol for
many suggestions }}
\smallskip
\centerline{Department of Mathematics}
\centerline{Rutgers University, Piscataway, NJ 08854-8019, USA.}
\centerline{\tt [mohamudm, zeilberg] at math dot rutgers dot edu}

\bigskip

\centerline{\footrm Submitted: May 28, 2004;  Accepted: Aug. 3, 2004;
   Published: xxx, 2004}
\centerline{\footrm Mathematics Subject Classifications: 33F10, 05A10, 41A25}

\bigskip\bigskip

\centerline{\bf Abstract}
\smallskip
{\narrower\noindent
Andrei Markov's 1890 method
for convergence-acceleration of series bears an amazing resemblance to 
WZ theory, as was recently pointed out by M. Kondratieva
and S. Sadov. But Markov did not have Gosper and Zeilberger's
algorithms, and even if he did, he wouldn't have had a computer
to run them on. Nevertheless, his beautiful ad-hoc method,
when coupled with WZ theory and Gosper's algorithm, leads
to a new class of identities and very fast 
convergence-acceleration formulas that can be applied to  {\it any}
infinite series of hypergeometric type.
\par}

\bigskip

{\bf Preface: Where are the Examples?}
 
One Example is given in the Appendix, but lots and lots of
examples can be found at

{\bf http://www.math.rutgers.edu/\Tilde zeilberg/Markov/Examples.html}.

Many other 
interesting examples for acceleration formulas will be found in 
a forthcoming article by the first author[Mo1].

In addition, readers can generate (potentially) infinitely
many other examples
by using the Maple package {\tt MarkovWZ} downloadable from that
page. No knowledge of Maple is necessary!, just a basic knowledge
of typing! Read the on-line instructions!

The research (and of course, writing the Maple packages) is
joint work between the authors. The actual wriring was done
by the second author.
In particular {\it we} means the
Royal {\it we}.

{\bf How Andrei Andreyevich Markov (almost) Discovered WZ Pairs}

On Jan. 7, 2004, 
one of us (DZ) received an E-mail message from Sergei Sadov,
that he kindly allowed us to quote from.

{\tt
From sergey@math.mun.ca  Wed Jan  7 21:38:58 2004 \hfill\break
To: Doron Zeilberger <zeilberg@math.rutgers.edu> \hfill\break
cc: Margo Kondratieva <mkondra@math.mun.ca>
\hfill\break
Subject: Markov's transformation of series
\hfill\break
Dear Professor Zeilberger,

I am finally writing to you, which is what I ought to have done at least 16 
months ago, after narrowly missing you at ICM in Beijing. 

At the ICM-2002 we, I and my wife and coauthor Margo (I speak for both of 
us), presented a poster under the title "Summation technique forgotten for a 
century: Markov (1890) - Wilf-Zeilberger (1990)". 
The abstract can be found on 
p. 404 of the ICM Abstracts volume. [In my present view, some particulars 
in that little text are inaccurate.]

Moving to a new place, teaching, not making progress in the topic -- 
resulted in a delay, which grew indefinitely.
  
This summer, visiting Markov's home city St.Petersburg (Russia), and
combing through old textbooks on series during this new year break, we have 
collected more material around Markov's memoir of 1890, aiming to answer 
the question why it had been forgotten. 

What Markov did in his memoir, very much resembles the WZ approach.
Currently we are preparing a first larger-than-abstract size
publication. We'd like to hear your first-hand opinion on Markov's work. 

You can find the 
scanned pdf's of Markov's memoir at \hfill\break
http://www.math.mun.ca/\Tilde sergey/Research/History/Markov/markov1890.html .

A particular question, which, perhaps, you can answer easily, is: 
whether Sister Celine had cited Markov?   

I enjoyed reading some (since I didn't read all) of your Opinions
and your opinion on this subject will be greatly appreciated here! 
 
Yours truly,
Sergey
}

[Note: see [KS1] and [KS2] for the abstract and paper mentioned
in Sergey Sadov's message. The very interesting [KS2]
exposits Markov's work very thoroughly.
As for Sadov's question about Sister Celine citing
Markov, the answer is negative].

Our initial reaction was mixed. 
Objectively, it was very interesting that the so-called WZ
method seemed to have been anticipated by the great Markov,
but subjectively, it is annoying to be scooped by {\it anyone},
especially someone a hundred years ago.

Naturally, 
we read Markov's {\it m\'emoire}([M]) right away, and
sure enough, already at  the very beginning,
there was something very familiar: the definition of
a WZ-pair!, or so it seemed.
It was contained inside a {\it proposition facile a d\'eduire
par la consid\'eration d'une somme double}. Here is a free
translation, from French, of that proposition.

``If two functions 
$$
U_{x,z} \quad and \quad V_{x,z}
$$
of independent variables $x$ and $z$ are related by the condition
$$
U_{x,z} - U_{x+1,z}=V_{x,z} - V_{x,z+1}
\eqno(1)
$$
one has
$$
{{ U_{0,0} + U_{0,1} + U_{0,2} + \dots + U_{0,j-1}}
\atop
{-U_{i,0} -U_{i,1} - U_{i,2} - \dots -U_{i,j-1}}}
\,\,=\,\,
{{ V_{0,0} + V_{1,0} + V_{2,0} + \dots + V_{i-1,0}}
\atop
{-V_{0,j} -V_{1,j} - V_{2,j} - \dots -U_{i-1,j}}} \quad,
\eqno(2)
$$
where $i$ and $j$ are arbitrary positive integers.''

He then states that all the $(U,V)$'s in his memoir
will be such that when $i$ and $j$ go to infinity  the
top series converge, and the bottom series converge to $0$,
yielding the identity
$$
\sum_{j=0}^{\infty} U_{0,j}=
\sum_{i=0}^{\infty} V_{i,0} \quad.
\eqno(3)
$$

Markov then proceeded to construct interesting pairs
of functions $(U_{x,z},V_{x,z})$, that satisfy $(1)$, and
the convergence property, yielding
an identity of type $(3)$ where the left side is a classical
constant (most notably $\zeta(3)$) and the right side is a
rapidly converging series. So his motivation was
{\bf convergence-acceleration}. Interestingly, 
this was one of the spin-offs(see [Z2], [AmZ1][AmZ2]) of modern WZ-theory,
whose initial motivation was {\bf identity-proving}.

Markov's immediate motivation was to one-up Stieltjes, in
the race for numerical computations of $\zeta(3)$. Using
an appropriate `WZ-pair', he computed $\zeta(3)$ to
$33$ decimal digits, beating the previous record of 
Stieltjes.

{\bf Markov was Brilliant but He did not Discover WZ-pairs}

First, he didn't give this concept a name, say `M-pair',
equation $(1)$ is just the hypothesis of his central lemma. Second,
he did not realize, explicitly, the role of {\bf hypergeometricity},
even though all of his examples were in fact hypergeometric
(either ordinary or $q$-). Finally he did not have
{\bf Gosper's algorithm}, so all his constructions
were completely ad hoc, using, however, a very clever ansatz.
But he didn't algorithmize his method (well, you can't really
blame him, since he couldn't have possibly consulted
his son, Andrei, Jr., [one of the co-discoverers
(with Turing, Church, and Post) of the modern notion of algorithm], as
the latter was yet to be born [Andrei, Jr. was born 13 years later,
in 1903]).

\vfill\eject

{\bf Markov's Brilliant Idea}

However, implicit in Markov's ad-hoc method is a {\bf new}
(well, new to us!) idea, that, when interfaced with Gosper's
algorithm, offers a far-reaching {\bf extension} of WZ-pairs,
that we will call MWZ pairs. In this article
we will describe an algorithm for finding such pairs, that
uses `Gosper with parameters' as a subroutine in an analogous way
to Zeilberger's algorithm.

{\bf We Have a Dream}

   Ap\'ery's amazing proofs of the irrationality of 
$\log 2, \zeta(2)$, and $\zeta(3)$ can be recast in terms
of WZ-theory ([Z2],[Z3]). Naturally, one would like
to generalize these to $\zeta(5)$ and beyond. A big
stumbling block for the extension was that they did not appear
to be natural WZ-pairs that handle $\zeta(5)$ and beyond.
We will show later that there are many (in fact too many!) MWZ-pairs
that can handle $\zeta(n)$ for any $n \geq 2$. Alas, we do not
(yet!) have irrationality proofs of $\zeta(5)$ and beyond, because
there is another ingredient to Ap\'ery's success: a judicious
{\bf averaging-function}. So far, our very limited explorations
did not succeed, but we believe that a systematic search, possibly
by also allowing more general averaging functions, might ultimately
succeed.

We should mention that the race for $\zeta(5)$ and beyond is
currently a very lively field
practiced by great talents such as Almkvist, Hata,
Fischler, Rivoal, Zudilin and others. See Fischler's[F]
recent {\it S\'eminaire Bourbaki}. Perhaps the new flexibility
of MWZ pairs, coupled with the already existing ideas of these
people, will lead to a breakthrough.


{\bf Markov's ad-hoc method}

Markov starts with a {\bf kernel} $H(x,z)$, and then,
by starting with $d=0$, tries to find the smallest 
non-negative integer $d$ for which there exist
$U(x,z), V(x,z)$ of the form
$$
U(x,z)=H(x,z) \left ( \sum_{i=0}^{d} A_i(x) z^ i \right ) \quad,
\eqno(Ansatz1)
$$
and
$$
V(x,z)=H(x,z) \left ( \sum_{i=0}^{d} B_i(x) z^ i \right ) \quad,
\eqno(Ansatz2)
$$
(for {\it some non-zero } $A_i(x),B_i(x)$  [$0 \leq i \leq d$] ),
that satisfy
$$
U(x+1,z)-U(x,z)=V(x,z+1)-V(x,z) 
\eqno(WZ)
$$
The $A_i(x)$'s and $B_i(x)$'s 
are {\it undetermined} `coefficients', in fact functions
of the single variable $x$. In addition, Markov poses the
{\bf initial conditions} $A_0(0)=1$, $A_i(0)=0, i \geq 1$.
Now Markov plugs $(Ansatz1)$ and $(Ansatz2)$ into $(WZ)$,
divides throughout by
$H(x,z)$, clears denominators, and sets all the coefficients
of the powers of $z$ in the numerator equal to $0$.
This leads to a system of first-order linear recurrence equations
with polynomial coefficients for the $A_i$'s and $B_i$'s, and if
{\bf in luck}, he finds  {\bf explicit} expresions for
the $A_i(x)$'s and $B_i(x)$'s. Finally, if successful,
he deduces a {\it convergence-acceleration} formula
$$
\sum_{z=0}^{\infty} H(0,z)=\sum_{x=0}^{\infty} V(x,0) \quad,
\eqno(Acc)
$$
where
$$
V(x,0)=H(x,0)  B_0(0) \quad,
$$
and it so happens that the series on the right-hand side converges
much faster than the series on the left-hand side.

{\bf Prerequisites}

We assume that the reader is familiar with [PWZ] (available
freely on the web), and, for some of this paper, with, [Z2].
In particular, the reader should know, or be willing to look up,
the definitions of {\it hypergeometric}, 
{\it proper-hypergeometric}, {\it holonomic},
and {\it WZ-pair}. Please note that the WZ-pairs featuring
in Ap\'ery's proofs for the irrationality of $\log 2, \zeta(2)$
and $\zeta(3)$ are slightly different than the ones in this
article, since the {\it domain} in [Z2] (as well as the one
implicit in Ap\'ery's original paper[Ap]) is {$\{n \geq k \geq 0\}$),
whereas, in this article, following Markov, we use the
more user-friendly domain $\{0 \leq n,k < \infty\}$. Of course
this only amounts to a simple change of (discrete) variables
featuring in the WZ-pairs. Also, we sometimes use $x$ and $z$ instead
of $n$ and $k$, as homage to Markov, who used the former.
Finally `ClosedForm' (in this paper) is the same as Proper-Hypergeometric.

{\bf Gosper}

{\bf Gosper's algorithm} is a {\bf decision procedure} that
{\bf inputs} a {\bf hypergeometric} sequence $a(k)$, in
{\bf one} variable (i.e. a sequence for which $a(k+1)/a(k)$ is
a {\bf rational function} of $k$) and  
{\bf outputs} a {\b rational function} $r(k)$ such that
$b(k):=r(k)a(k)$ satisfies $a(k)=b(k+1)-b(k)$, if such
an $r(k)$ exists, and otherwise returns FAIL.
Its {\bf driving force} is a system of {\bf linear equations}.

The {\it first} phase of Gosper is to {\bf peel-off} the
polynomial of {\bf largest} degree, $p(k)$ such that
$a(k)=p(k) \overline{a}(k)$, and $\overline{a}(k)$ is
a hypergeometric sequence that is {\bf minimal} in some sense.
So the {\it second} phase of Gosper really inputs a
{\bf polynomial} and a {\bf hypegometric sequence}.
It then proceeds to construct a certain system of 
inhomogeneous {\it linear} equations. Then it tries
to solve that system. If it succeeds, then Gosper reports
success, and the solution of the system leads to the
{\bf anti-difference}. If it fails, then Gosper returns
{\bf FAIL}.


{\bf Gosper with Parameters}

It turns out that the system of linear equations constructed by
Gosper is also {\bf linear} in the polynomial $p(k)$. So
one can just start with any-old hypergeometric $a(k)$ and
a polynomial $p(k)$ that depends, {\it linearly}, on certain
auxiliary parameters. Then one may ask: For what choice
of these parameters (if any), is $p(k)a(k)$ gosperable?
Now we get the same system of linear equations as before,
but the set of `unknowns' consist, in addition to those 
given by Gosper, of these additional auxiliary parameters. Now the system
of linear equations is {\bf homogenous}, so there is always
a solution. Alas, it may return $0$, which is correct
($0$ does indeed have a hypergeometric anti-difference), but
{\it not} terribly interesting. If we get a {\it non-zero}
solution, then {\tt GosperWithParameters} returns the
successful choice of parameters whose plugging-in into
$p(k)$ makes $p(k)a(k)$ gosperable. It also returns the
corresponding anti-difference.

{\bf Zeilberger}

The Z-algorithm uses, as a crucial subroutine, {\bf GosperWithParameters}.

Given a hypergeometric term $F(n,k)$ in {\it two} variables,
$n$ and $k$, and an integer $L$, it tries to find
$a_0(n), a_1(n), \dots, a_L(n)$ such that
$$
a_0(n)F(n,k) + a_1(n)F(n+1,k) + \dots + 
a_L(n)F(n+L,k)  \quad,
$$
is gosperable with respect to $k$. After dividing throughout
by $F(n,k)$,  adding the resulting fractions 
(using, in Maple, {\tt normal}), and multiplying back
by $F(n,k)$, the above quantity has the form:
$$
POL(a_0,a_1, \dots, a_L) \cdot ClosedForm(n,k) \quad,
$$
where $POL$ is a polynomial in $k$ that depends {\it linearly}
on $a_0, a_1, \dots, a_L$. Of course it is also a polynomial
in $n$, but this is irrelevant right now, since $n$ is silent
(all the action is w.r.t. to $k$).
To find out whether there exists indeed a choice of (non-zero!)
$a_i$'s that makes this gosperable, we use GosperWithParameters,
that returns the successful $a_i$'s as well as the certificate
$G(n,k)$.
It was proved in [Z1] (see also [PWZ]) that there 
{\it always} exists an $L$ for which it is successful. So in
practice one starts with $L=0$ and keeps increasing
$L$ until success is reached.

{\bf Markov meets Gosper}

It so happens that Markov could have saved himself
lots of calculations (even without a computer), if he would have
known about GosperWithParameters. Coupled with the computer,
it leads to really amazing results, as we hope to show.

Markov's motivation was {\it series-acceleration}, so let's 
reconstruct his reasoning, and superpose on it our modern know-how.
We are given a series that {\it slowly} converges to some
(usually `famous') constant, let's call it $c$:
$$
c=\sum_{k=0}^{\infty} a(k) \quad,
$$
where $a(k)$ is {\it hypergeometric}.
We first look for a {\it two-variable} proper-hypergeometric term,
let's call it $H(n,k)$ such that $H(0,k)=a(k)$
(of course, there are lots of [in fact infinitely-many]) possibilities.)
So we have 
$$
c=\sum_{k=0}^{\infty} H(0,k) \quad.
$$
Now, following Markov, fix a degree $d$, and write
$$
F(n,k)=\left ( \sum_{i=0}^{d} a_i(n) k^i \right )  H(n,k) \quad .
$$
We also want $F(0,k)=H(0,k)$, so we insist that
the $a_i(n)$ satisfy the following {\it initial conditions}:
$$
a_0(0)=1 \quad; \quad a_i(0)=0 \quad ,\quad 1 \leq i \leq d \quad .
$$

{\bf Question:} Does there exist a choice of $\{a_i(n)\}$ that
makes $\Delta_nF(n,k):=F(n+1,k)-F(n,k)$ gosperable w.r.t. $k$?
If there is indeed such a choice, then for that particular
assignment, there exists a $G(n,k)$, which furthermore
is of the form $Rational(n,k)H(n,k)$, such that
$(F,G)$ is a ``{\it WZ-pair}'',
$$
F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k) \quad ,
\eqno(MWZ)
$$
and by $(Acc)$, this would entail
$$
c=\sum_{n=0}^{\infty} G(n,0) \quad,
$$
which, if all goes well, is a much faster-converging series
than the original.

{\bf Answer}: Having fixed the degree $d$, and trying the
above ansatz for $F(n,k)$, as yet with {\it undetermined}
coefficients $a_i(n)$ that are {\bf functions of n}, forming
$\Delta_n F(n,k)$ and dividing by $H(n,k)$,
simplifying $H(n+1,k)/H(n,k)$ (it is a rational function since
$H(n,k)$ is hypergeometric),
would yield
a {\bf rational function} whose numerator features
{\bf both} $a_i(n)$ and $a_i(n+1)$. 
Because $H(n,k)$ is not just hypergeometric but {\it proper}-
hypergeometric (see [PWZ] for definitions),
the denominator of the above expression
can be combined with the `purely-hypergeometric' part,
and we can input the latter, and the numerator, into
{\tt GosperWithParameters}, where the `parameters' are
{\bf both} the $a_i(n)$'s and the $a_i(n+1)$'s.

Now GosperWithParameters, if successful, will return
a system of {\bf linear} equations relating the `unknowns'
$a_i(n)$ ($0 \leq i \leq d$),  $a_{i+1}(n)$ ($0 \leq i \leq d$),
and the coefficient of the polynomial in Gosper's algorithm.
If the `co-rank' of this system of homogeneous linear equations is
$d+1$, it should be possible to express all these unknowns,
in particular the
$a_i(n+1)$'s, in terms of the $a_i(n)$'s, thereby getting
a {\bf first-order system} of {\bf linear recurrences} 
with {\bf polynomial coefficients}
$$
(a_0(n+1), \dots, a_d(n+1))^T \,\, = \,\,
{\bf A(n)} \,\, (a_0(n), \dots, a_d(n))^T \quad ,
\eqno(Recurrence)
$$
where {\bf A(n)} is a $(d+1) \times (d+1)$ matrix with entries that
are rational functions in $n$. Note that this {\it defines}
the $a_i(n)$'s (subject to the initial conditions), and in general
it is not possible to solve them `explicitly'. But `solving' is just
a human hang-up. From our, and the computer's, point of view,
$(Recurrence)$ is as explicit as $n!$, since after all, $n!$ is just
shorthand for the solution of the recurrence $a(n)=na(n-1), a(0)=1$.

In addition, the coefficients of the
polynomial that is hidden inside the original
Gosper algorithm, are also expressible in terms of the
$a_i(n)$, and hence the anti-difference $G(n,k)$ can
be expressed as 
$$
G(n,k)=ClosedForm(n,k) \cdot
\left ( \sum_{i=0}^{d} a_i(n)b_i(n,k) \right ) \quad,
$$
where $b_i(n,k)$ are certain {\bf polynomials} in $n$ and $k$.

{\bf Finally}, plugging-in $k=0$ gives
$$
b(n):=G(n,0)=ClosedForm(n,0) \cdot 
\left ( \sum_{i=0}^{d} a_i(n)b_i(n,0) \right ) \quad,
$$
and the `fast' series for $c$,
$$
c=\sum_{n=0}^{\infty} b(n) \quad .
$$

If everything works out with $d=0$, then the
``system'' $(Recurrence)$  only has one unknown function
$a_0(n)$, and $(F,G)$ is a good-old  (hypergeometric) WZ pair.
But if $d>0$ then while $(F,G)$ still satisfy 
$$
F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k) \quad,
\eqno(MWZ)
$$
{\it now} they are no longer hypergeometric.
On the other hand, they are more than
``just holonomic'', since, in fact,
both $F(n,k)$ and $G(n,k)$ have the form:

$$
ProperHypergometric(n,k) \cdot 
\left ( \sum_{i=0}^{d} Holonomic(n) k^i \right ) \quad .
$$
We call these more generalized pairs {\bf MWZ}-pairs.

{\bf What is Needed for the Markov-WZ Method to Become Official}

Like in Zeilberger's algorithm,
we need a formal proof that there exists a $d$ such that
the resulting system of linear equations outputted by
GosperWithParameters has co-rank $d+1$.
In other words, we need to prove
that for {\it any} proper-hypergeometric kernel $H(n,k)$ there
exists a non-negative integer
$d$ such that $F(n,k)$ in the form given in $(Markov)$
has a MWZ-mate. We know how to do it, but confess that we haven't
carried out the details yet. The way to do it is to consider
a generic proper-hypergeometric kernel, and `trace' the algorithm
in this general form, finding upper bounds for $d$ to guarantee
that the system of linear equations buried inside GoseprWithParameters
has a $d+1$-parameter solution, and that $a_0(n), \dots, a_d(n)$
can be used as these parameters, forcing $a_i(n+1)$'s to be
expressible in terms of these, as well as the 
coefficients of the polynomial implicit in Gosper.

On the other hand, the {\it proof of the proof is in the eating}.
Whenever we succeed, we know {\it for sure} that we have
a bona-fide MWZ pair, unlike, say, Miller-Rabin-style primality testing.
Since, in {\it real time}, there would be lots of examples where
the size of the problem is too big, and our {\it main} motivation
is to prove irrationality of famous constants,
(and, as consolation prizes,  create super-fast
accelerating series for favorite constants), the {\bf a posteriory}
reassurance is almost as good as an {\bf a priori} assurance.
But, if the readers wish to have this {\it a priori} guarantee,
they are more than welcome to carry out the details.

All this only applies to the existence of an MWZ pair.
In order to use it for convergence-acceleration, one must
check, in addition, that
$$
\sum_{k=0}^{\infty} F(0,k) \quad , \quad 
\sum_{n=0}^{\infty} G(n,0) \quad , 
$$
converge, and that 
$$
\lim_{n \rightarrow \infty} \,\,
\sum_{k=0}^{\infty} F(n,k)=0  \quad , \quad
\lim_{k \rightarrow \infty} \, \,
\sum_{n=0}^{\infty} G(n,k) =0 \quad .
$$

Of course, this is only useful if the accelerated series converges
faster than the original series, so this has to be checked as well.

{\bf Bonus}

In the original WZ method, the {\it main} motivation was
the automated proving (and discovery) of {\bf identities}
and the application to {\bf convergence-acceleration} came
later. Markov's motivation, as we said above, was the latter,
but, whenever we get an MWZ pair, we have as before
an identity
$$
\sum_{k}F(n,k) =Constant \quad,
$$ 
and similarly for $G(n,k)$. It is true that these new
identities may look weird to human eyes, since $F(n,k)$ is
not closed-form in the narrow sense of the word, but rather
features sequences $a_0(n), a_1(n), ..., a_d(n)$, satisfying
a system, but in the {\bf eyes of God} they are just as beautiful,
perhaps even more so, since they are deeper in some sense.

If in luck, it may still happen that $a_0(n), a_1(n), \dots$
are closed-form (which can be guessed empirically,
and then proved rigorously by verifying that $(Recurrence)$
is satisfied). This was the case in all the examples that
occur in Markov's original article[M].

{\bf Potential Function and Irrationality}

Just as for WZ pairs (see [Z2]), every  MWZ leads to
a {\bf potential function} $c(n,k)$ that satisfies
$$
F(n,k)=c(n,k+1)-c(n,k) \quad , \quad
G(n,k)=c(n+1,k)-c(n,k) \quad ,
$$
which, of course, is no longer closed form, and that may be given
by
$$
c(n,k)=\sum_{k'=0}^{k-1} F(0,k') +
\sum_{n'=0}^{n-1} G(n',k) \quad,
$$
or equivalently
$$
c(n,k)=\sum_{n'=0}^{n-1} G(n',0) +
\sum_{k'=0}^{k-1} F(n,k') \quad.
$$
Note that $c(n,k)$ are all {\it diophantine} approximations to
the constant $c$. Indeed the {\it definition} of $c$ is $c(0, \infty)$
and the `accelerated version' is $c(\infty, 0)$. 
If one can find a subsequence
of the doubly-infinite sequence 
$c(n,k)$, let's call it, $\{e_m/f_m\}_{m=1}^{\infty}$ such that for some
$\delta >0$, there exists a constant $C$ such that
$$
\vert {{e_m} \over {f_m}} - c \vert  \leq {{C} \over {{f_m}^{1+\delta}}} \quad,
$$
then we immediately have a proof that $c$ is irrational.
Unfortunately, this didn't happen yet
(even for Ap\'ery's spectacular
sequences for $\log 2, \zeta(2)$ and $\zeta(3)$,
that needed weighted-averaging), 
but in our experiments
we obtained (empirically) $\delta$'s that, while negative,
were pretty close to $0$. If you take a random sequence and a random
constant, $\delta$ would be $-1$ or very close to it, so any
$\delta$ closer to $0$ than to $-1$ is already a step in the right direction.

See the sample input and output files
in the webpage of this article.

Recall that
Roger Ap\'ery's[Ap] brilliant method (see [Z2] and [Z3]), consists
of finding a `clever' {\bf averaging function} $b(n,k)$ such that
$$
{{e_n} \over {f_n}}:=
{
{\sum_{k=0}^{n} b(n,k) c(n,k)}
\over
{\sum_{k=0}^{n} b(n,k)}
} \quad,
$$
or in, the present, Markovian notation, where the natural habitat
of $c(n,k)$ is the discrete positive quadrant:
$$
{{e_n} \over {f_n}}:=
{
{\sum_{x+y=n} b(x,y) c(x,y)}
\over
{\sum_{x+y=n} b(x,y)}
} \quad,
$$
turns out to be a successful rational-approximating sequence with
a positive $\delta$. As we said above, our (and quite a few other people's)
{\bf dream}
is to emulate Ap\'ery for $\zeta(5)$ and beyond.

{\bf How to (Who Knows?) Fulfill Our Dream}

In addition to producing irrationality proofs, Ap\'ery's method
also yields, as a bonus, convergence-acceleration series for the
constants in question. Hitherto, even the latter were not possible
for $\zeta(5)$ and beyond, but now, with the extended notion of
MWZ pairs, our computer easily cranks out amazingly fast
series for $\zeta(5), \zeta(7), \dots$, and many other
constants defined by hypergeometric series, that we randomly
experimented with.
Each of them
comes from a certain MWZ pair, and its associated potential
function gives diophantine approximations to the constant under
consideration. Now if we could only find a good `averaging function'
then we will be famous.

{\bf The Major Strength of the MWZ method: Generality}

There are infinitely many choices of 
hypergeometric `kernels' $H(n,k)$ extending a given hypergeometric
sequence $a(k)$ such that $H(0,k)=a(k)$. Each of these gives its
own MWZ pair. There are also infinitely many possible
averaging functions $b(n,k)$, so just keep on trying!

{\bf The Major Weakness of the MWZ method: Generality}

Since life is finite, and there are infinitely many possibilities,
a brute-force search is probably doomed to failure. But
perhaps one can develop the theory further in order to predict
potentially successful candidates for $H(n,k)$ and $b(n,k)$, that
would narrow the haystack.

{\bf A User's Manual for the Maple package MarkovWZ}

This is implemented in the Maple package
{\tt MarkovWZ} downloadable from the webpage of this article

{\tt  http://www.math.rutgers.edu/\Tilde zeilberg/Markov/marwz.html} ,

that also has sample input and output.

To use the program, save it as {\tt MarkovWZ}, stay in
the same directory, go into Maple, and type: \hfill\break
{\tt read MarkovWZ; } $\quad$,  \hfill\break
and then follow the on-line instructions.

The main functions are {\tt Markov}, {\tt ACC}, and 
{\tt WtAve}. The functions
 $H1:=(-1)^zz!/(x+z+1)!$, for $\log 2$,
$H2:=(-1)^z (2 z!/(x+z+1))/(2x+z+1)!$ for
$\zeta(2)$,
$H3:=(z!/(2x+z+1)!)/(x+z+1)^2$ for $\zeta(3)$,
and $C1:=(-1)^z(1/4)(z+1/2)!^2/(2x+z+3/2)!^2$ for
$1-Catalan$ (alas, this one does not lead (yet!) to an irrationality
proof) are built-in.
For example, to find the MWZ-pair for $\zeta(2)$, say, type:

{\tt Markov(H2,z,x);}

The output consists of four parts. The first one is 
the inputted kernel $H$ itself ($H2$ in this particular example).
The second one is the matrix {\bf A} above. The third part is just
the list of powers $[1,k, \dots, k^{d}]$, and the last part
is the vector of the $b_i$'s, rational functions in the variables
$n$ and $k$,
whose dot product with the $a_i(n)$'s (multiplied by $H$) would
give the MWZ-mate, $G$.

A {\bf verbose} version of {\tt Markov}, with all the details,
for the benefit of humans, is procedure {\tt MarkovPaper}.

Procedure {\tt ACC(H,k,n)}, finds an acceleration formula, e.g. try:

{\tt ACC((k!/(n+k+1)!)**2,k,n);} .

The output consists of four parts. The first part is simply
$H$ when $n=0$, which is the summand of the slowly-converging
series. The second part is the matrix {\bf A} (same as in {\tt Markov}),
describing the transition matrix between the $a_i$'s at $n$ and
the $a_i$'s at $n+1$, which, together with the initial conditions
$a_0(0)=1, a_1(0)= \dots =a_d(0)=0$, determine the $a_i$'s uniquely
(and make them easy to compute numerically). The third part is
a vector $(b_i(n))$ (the same as the corresponding one for {\tt Markov},
but with $k=0$ substituted), whose dot-product with the $(a_i)$ gives
the summand of the `fast' series. Finally, the fourth part
is the convergence-rate, i.e. the 
absolute value of the asymptotic ratio of consecutive terms in
the accelerating series.

A {\bf verbose} version of {\tt ACC}, will all the details,
for the benefit of humans, is procedure {\tt ACCpaper}.

Procedures {\tt Appx} and {\tt Appxf} use {\tt ACC} to find numerical
approximations. Procedure {\tt delt} empirically (and of course, approximately)
finds the above $\delta$ for a specific approximation.

Procedure {\tt WtAve(MWZ,z,x,b,L)} finds the $L$-th term in
the sequence obtained from using $b$ 
(a proper-hypergeometric expression
in $x$ and $z$) as the averaging function for the MWZ-pair MWZ.
For example, using the built-in $H2$ and $H3$, type:

{\tt z2:=WtAve(Markov(H2,z,x),z,x,binomial(z+2*x,x)*binomial(x+z,z)**2,30)};

{\tt z3:=WtAve(Markov(H3,z,x),z,x,binomial(z+2*x,x)**2*binomial(x+z,z)**2,30)}.

Typing {\tt delt(z2,Zeta(2));} and {\tt delt(z3,Zeta(3));} would yield
{\bf positive} numbers, confirming (empirically), Ap\'ery's
historic constructions.

There is also a new version of Zeilberger's algorithm
({\tt Zeil}), that today is part of Maple's {\tt SumTools} package.
It is one of the main
functions of Zeilberger's package {\tt EKHAD}. The new version uses
{\tt GosperWithParameters} directly, and seems to be much more efficient
than {\tt EKHAD}, and a little more efficient than
 {\tt SumTools}.

{\bf The Maple packages MarkovAZ and ContMarkovWZ}

The Markov analog for pairs $(F(n,x),G(n,x))$, 
such that $F(n+1,x)-F(x,n)={{d} \over {dx}}G(n,x)$ that uses
an extension of the Almkvist-Zeilberger algorithm ([AlZ]),
is implemented in {\tt MarkovAZ}. The simple
extension for finding pairs satisfying
${{d} \over {dx}}F(n,x)=G(n+1,x)-G(n,x)$ is done in
{\tt ContMarkovWZ}.

The q-analog of this paper will appear in [Mo2].

{\bf Appendix: An example}

As mentioned in the preface, many examples,
both tersely and verbosely, are given in the Examples webpage
of this article

{\bf http://www.math.rutgers.edu/\Tilde zeilberg/Markov/Examples.html}.

Better still, use procedures {\tt MarkovPaper} and
{\tt ACCpaper} in the Maple package {\tt MarkovWZ}, to get
as many examples as you wish. 


{\bf Theorem:}  Let the column-vector of functions of $n$,
$a(n):=[a_0(n), a_1(n), a_2(n)]^T$, be defined
by the initial conditions: $a(0) = [1, 0, 0]^T$,
and $a(n+1)=A(n)a(n)$, where 
$$
A(n):=
\pmatrix{ {{1} \over{2}} & {{3n+2} \over{4}} &  
{{3n(n+1)}\over {8}},\cr
{{-3} \over {2(n+1)}}
 & {{-(7n+4)} \over {4(n+1)}}& 
{{-3n+2} \over {8}} \cr
{{3} \over {2(n+1)^2}} 
& {{3n} \over {4(n+1)^2}}  & {{-(5n+2)} \over {8(n+1)}}
} \quad .
$$

In other words, $a(n)=A(n-1)A(n-2)...A(0)$ times $[1, 0, 0]^T$. Let
$$                                  
F(n, k) = {{n} \choose {k}}^3 (a_0(n) + a_1(n) k + a_2(n) k^2 ) \quad.
$$
We have, for every non-negative integer $n$
$$
\sum_{k} F(n,k)=1 \quad .
$$
{\bf Proof}: We cleverly construct
$$
G \left( n,k \right ) = 
 {n\choose k}^{3} \cdot
$$
$$
\left ( -1/2\,{\frac {a_{{0}} ( n ) {k}^{3}}
{ ( n+1-k ) ^{3}}}+
1/8\,{\frac {a_{{1}} ( n ) {k}^{3} ( 
6\,n+8-4\,k  ) }{  ( n+1-k  )^{3}}}+
1/8\,{\frac {a_{{2}} ( n ) {k}^{3} 
 ( 3\,{n}^{2}-3\,n-6+6\,nk+10\,k-4\,{k}^{2}  ) }
{  ( n+1-k  ) ^{3}}} \right ) 
$$
with the motive that
$$
  F(n + 1, k) - F(n, k) = G(n, k + 1) - G(n, k) \quad ,
$$
(check!), and the identity follows upon summing with respect to $k$. QED.

{\bf References}

[AlZ] G. Almkvist and D. Zeilberger,
{\it The method of differentiating under the
integral sign}, J. Symbolic Computation {\bf 10}, 571-591 (1990).
[available on-line from the second author's website.]

[AmZ1] T. Amdeberhan and D. Zeilberger,
{\it Hypergeometric Series Acceleration via the WZ method}
Elect. J. of Combinatorics
({\tt http://www.combinatorics.org}), 
{\bf 4(2)} [Wilf Festschrifft volume], R3 (4 pages) (1997).
[available on-line from the authors' websites.]

[AmZ2] T. Amdeberhan and D. Zeilberger,
{\it q-Ap\'ery Irrationality Proofs by q-WZ Pairs}, 
Adv. Appl. Math. {\bf 20}, 275-283, (1998).
[available on-line from the authors' websites.]

[Ap] R. Ap\'ery, 
{\it ``Interpolation de fractions continues et irrationalit\'e
de certaine constantes''}
Bulletin de la section des sciences du C.T.H.S. \#3
p. 37-53, 1981.

[F] S. Fischler, {\it Irationalit\'e de valeurs de z\^eta
[d'apr\`es Ap\'ery, Rivoal, ... ],
S\'eminaire Bourbaki- Novembre 2002, Expos\'e num\'ero 910;},
to appear in Ast\'erique.
Available On-line from {\tt arXiv.org}.

[KS1] M. Kondratieva and S. Sadov, {\it Summation techniques
forgotten for a century: Markov (1890)- Wilf-Zeilberger (1990)},
ICM-2002, {\it Abstract of Short Communications}. Higher Education
Press, Beijing, 2002, p. 404.

[KS2] M. Kondratieva and S. Sadov, {\it Markov's transformation of
series and the WZ method}, to appear in Adv. Appl. Math.
Available from {\tt http://xxx.arXiv.org/math.CA/0405592}.

[M] A.A. Markoff, {\it M\'emoire sur la transformation des s\'eries
peu convergentes en s\'eries tr\`es convergentes},
M\'emoires  de L'Acad\'emie Imp\'eriale des Sciences de St.-P\'etersbourg,
$VII^{e}$ S\'erie. {\bf Tome XXXVII, ${\bf N}^{o}$ 9}.

[Mo1] M. Mohammed, {\it Infinite families of accelerating
series for some classical constants using the MWZ  method}, in preparation.

[Mo2] M. Mohammed, {\it The q-Markov-WZ Method}, in preparation.

[PWZ] M. Petkovsek, H. S. Wilf and D. Zeilberger,
{\it A=B}, AK Peters, Wellesley, (1996).
[available on-line from the authors' websites.]

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

[Z1] D. Zeilberger,
{\it  A Fast Algorithm for proving terminating hypergeometric
identities}, Discrete Math {\bf 80}, 207-211, (1990).
[available on-line from the author's website.]

[Z2] D. Zeilberger,
{\it Closed Form (pun intended!)}, 
 in: ``Special volume in memory of Emil Grosswald", M. Knopp
and M. Sheingorn,
eds., Contemporary Mathematics {\bf 143} 579-607, AMS, Providence (1993).
[available on-line from the author's website.]

[Z3] D. Zeilberger, {\it Computerized Deconstruction}, Adv. Applied Math.
{\bf 30} (2003), 633-654. [available on-line from the author's website.]


\end














