The MARKOV-WZ METHOD ^{1}

Mohamud MOHAMMED ^{2} and Doron ZEILBERGER^{3}

Abstract: 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 convergenceacceleration formulas that can be applied to any infinite series of hypergeometric type.

Preface: Where are the Examples?

One Example is given in the Appendix, but lots and lots of examples can be found at

http://www.math.rutgers.edu/˜ 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 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 we means the Royal we.

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.

From sergey@math.mun.ca Wed Jan 7 21:38:58 2004
To:  Doron Zeilberger <zeilberg@math.rutgers.edu>
cc:  Margo Kondratieva <mkondra@math.mun.ca>
Subject:  Markov's transformation of series
MarkovWZ, MarkovAZ, and ContMarkovWZ, available from

1 First version: May 31, 2004 . This version: Aug. 3, 2004. This article is accompanied by the Maple packages

http://www.math.rutgers.edu/˜ zeilberg/Markov/marwz.html . Supported in part by the NSF.

2 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. mohamudm@math.rutgers.edu , http://www.math.rutgers.edu/~mohamudm/.

3 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu , http://www.math.rutgers.edu/~zeilberg/.

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), pre-
sented 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 in-
accurate.]
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 for-
gotten.
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
http://www.math.mun.ca/~sergey/Research/History/Markov/markov1890.html .
A particular question, which, perhaps, you can answer easily, is:  whether Sister Ce-
line 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 anyone, especially someone a hundred years ago.

Naturally, we read Markov’s mémoire([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 proposition facile a déduire par la considération d’une somme double. Here is a free translation, from French, of that proposition.

“If two functions

U_{x,z} and 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}  (1)

one has

{U_{0,0} + U_{0,1} + U_{0,2} + … + U_{0,j−1} \atop −U_{i,0} − U_{i,1} − U_{i,2} − … − U_{i,j−1}} = {V_{0,0} + V_{1,0} + V_{2,0} + … + V_{i−1,0} \atop −V_{0,j} − V_{1,j} − V_{2,j} − … − V_{i−1,j}} ,  (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

∑_{j=0}^{∞} U_{0,j} = ∑_{i=0}^{∞} V_{i,0} .  (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 ζ(3)) and the right side is a rapidly converging series. So his motivation was convergence-acceleration. Interestingly, this was one of the spin-offs(see [Z2], [AmZ1][AmZ2]) of modern WZ-theory, whose initial motivation was identity-proving.

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

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 hypergeometricity, even though all of his examples were in fact hypergeometric (either ordinary or q-). Finally he did not have 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]).

Markov’s Brilliant Idea

However, implicit in Markov’s ad-hoc method is a new (well, new to us!) idea, that, when interfaced with Gosper’s algorithm, offers a far-reaching 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.

We Have a Dream

Apéry’s amazing proofs of the irrationality of log 2, ζ(2), and ζ(3) can be recast in terms of WZtheory ([Z2],[Z3]). Naturally, one would like to generalize these to ζ(5) and beyond. A big stumbling block for the extension was that they did not appear to be natural WZ-pairs that handle ζ(5) and beyond. We will show later that there are many (in fact too many!) MWZ-pairs that can handle ζ(n) for any n ≥ 2. Alas, we do not (yet!) have irrationality proofs of ζ(5) and beyond, because there is another ingredient to Apéry’s success: a judicious 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 ζ(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 Séminaire Bourbaki. Perhaps the new flexibility of MWZ pairs, coupled with the already existing ideas of these people, will lead to a breakthrough.

Markov’s ad-hoc method

Markov starts with a 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) (∑_{i=0}^{d} A_{i}(x)z^{i}) ,  (Ansatz1)

and

V (x, z) = H(x, z) (∑_{i=0}^{d} B_{i}(x)z^{i}) ,  (Ansatz2)

(for some non-zero A_{i}(x), B_{i}(x) [0 ≤ i ≤ d] ), that satisfy

U(x + 1, z) − U(x, z) = V (x, z + 1) − V (x, z)  (W Z)

The A_{i}(x)’s and B_{i}(x)’s are undetermined ‘coefficients’, in fact functions of the single variable x. In addition, Markov poses the initial conditions A_{0}(0) = 1, A_{i}(0) = 0, i ≥ 1. Now Markov plugs (Ansatz1) and (Ansatz2) into (W Z), 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 in luck, he finds explicit expresions for the A_{i}(x)’s and B_{i}(x)’s. Finally, if successful, he deduces a convergence-acceleration formula

∑_{z=0}^{∞} H(0, z) = ∑_{x=0}^{∞} V (x, 0) ,  (Acc)

where

V (x, 0) = H(x, 0)B_{0}(0) ,

and it so happens that the series on the right-hand side converges much faster than the series on the left-hand side.

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 hypergeometric, proper-hypergeometric, holonomic, and WZ-pair. Please note that the WZ-pairs featuring in Apéry’s proofs for the irrationality of log 2, ζ(2) and ζ(3) are slightly different than the ones in this article, since the domain in [Z2] (as well as the one implicit in Apéry’s original paper[Ap]) is {n ≥ k ≥ 0}), whereas, in this article, following Markov, we use the more user-friendly domain {0 ≤ n, k < ∞}. 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.

Gosper

Gosper’s algorithm is a decision procedure that inputs a hypergeometric sequence a(k), in one variable (i.e. a sequence for which a(k + 1)/a(k) is a rational function of k) and outputs a r̄ational 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 driving force is a system of linear equations.

The first phase of Gosper is to peel-off the polynomial of largest degree, p(k) such that a(k) = p(k)\overline{a}(k), and \overline{a}(k) is a hypergeometric sequence that is minimal in some sense. So the second phase of Gosper really inputs a polynomial and a hypegometric sequence. It then proceeds to construct a certain system of inhomogeneous 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 antidifference. If it fails, then Gosper returns FAIL.

Gosper with Parameters

It turns out that the system of linear equations constructed by Gosper is also linear in the polynomial p(k). So one can just start with any-old hypergeometric a(k) and a polynomial p(k) that depends, 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 homogenous, so there is always a solution. Alas, it may return 0, which is correct (0 does indeed have a hypergeometric anti-difference), but not terribly interesting. If we get a non-zero solution, then 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.

Zeilberger

The Z-algorithm uses, as a crucial subroutine, GosperWithParameters.

Given a hypergeometric term F (n, k) in two variables, n and k, and an integer L, it tries to find a_{0}(n), a_{1}(n), …, a_{L}(n) such that

a_{0}(n)F (n, k) + a_{1}(n)F (n + 1, k) + … + a_{L}(n)F (n + L, k) ,

is gosperable with respect to k. After dividing throughout by F (n, k), adding the resulting fractions (using, in Maple, normal), and multiplying back by F (n, k), the above quantity has the form:

P OL(a_{0}, a_{1}, …, a_{L}) · ClosedF orm(n, k) ,

where P OL is a polynomial in k that depends linearly on a_{0}, a_{1}, …, 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 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.

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 series-acceleration, so let’s reconstruct his reasoning, and superpose on it our modern know-how. We are given a series that slowly converges to some (usually ‘famous’) constant, let’s call it c:

c = ∑_{k=0}^{∞} a(k) ,

where a(k) is hypergeometric. We first look for a 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 = ∑_{k=0}^{∞} H(0, k) .

Now, following Markov, fix a degree d, and write

F (n, k) = (∑_{i=0}^{d} a_{i}(n)k^{i}) H(n, k) .

We also want F (0, k) = H(0, k), so we insist that the a_{i}(n) satisfy the following initial conditions:

a_{0}(0) = 1 ; a_{i}(0) = 0 , 1 ≤ i ≤ d .

Question: Does there exist a choice of {a_{i}(n)} that makes Δ_{n}F (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 “WZ-pair”,

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) ,  (MW Z)

and by (Acc), this would entail

c = ∑_{n=0}^{∞} G(n, 0) ,

which, if all goes well, is a much faster-converging series than the original.

Answer: Having fixed the degree d, and trying the above ansatz for F (n, k), as yet with undetermined coefficients a_{i}(n) that are functions of n, forming Δ_{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 rational function whose numerator features both a_{i}(n) and a_{i}(n + 1). Because H(n, k) is not just hypergeometric but 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 GosperWithParameters, where the ‘parameters’ are both the a_{i}(n)’s and the a_{i}(n + 1)’s.

Now GosperWithParameters, if successful, will return a system of linear equations relating the ‘unknowns’ a_{i}(n) (0 ≤ i ≤ d), a_{i+1}(n) (0 ≤ i ≤ 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 first-order system of linear recurrences with polynomial coefficients

(a_{0}(n + 1), …, a_{d}(n + 1))^{T} = A(n) (a_{0}(n), …, a_{d}(n))^{T} ,  (Recurrence)

where A(n) is a (d + 1) × (d + 1) matrix with entries that are rational functions in n. Note that this 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) = ClosedF orm(n, k) · (∑_{i=0}^{d} a_{i}(n)b_{i}(n, k)) ,

where b_{i}(n, k) are certain polynomials in n and k.

Finally, plugging-in k = 0 gives

b(n) := G(n, 0) = ClosedF orm(n, 0) · (∑_{i=0}^{d} a_{i}(n)b_{i}(n, 0)) ,

and the ‘fast’ series for c,

c = ∑_{n=0}^{∞} b(n) .

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) ,  (MW Z)

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:

P roperHypergometric(n, k) · (∑_{i=0}^{d} Holonomic(n)k^{i}) .

We call these more generalized pairs MWZ-pairs.

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 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), …, 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 proof of the proof is in the eating. Whenever we succeed, we know for sure that we have a bona-fide MWZ pair, unlike, say, Miller-Rabin-style primality testing. Since, in real time, there would be lots of examples where the size of the problem is too big, and our main motivation is to prove irrationality of famous constants, (and, as consolation prizes, create super-fast accelerating series for favorite constants), the a posteriory reassurance is almost as good as an a priori assurance. But, if the readers wish to have this 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

∑_{k=0}^{∞} F (0, k) , ∑_{n=0}^{∞} G(n, 0) ,

converge, and that

lim_{n→∞} ∑_{k=0}^{∞} F (n, k) = 0 , lim_{k→∞} ∑_{n=0}^{∞} G(n, k) = 0 .

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

Bonus

In the original WZ method, the main motivation was the automated proving (and discovery) of identities and the application to 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

∑_{k} F (n, k) = Constant ,

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 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), … 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].

Potential Function and Irrationality

Just as for WZ pairs (see [Z2]), every MWZ leads to a potential function c(n, k) that satisfies

F (n, k) = c(n, k + 1) − c(n, k) , G(n, k) = c(n + 1, k) − c(n, k) ,

which, of course, is no longer closed form, and that may be given by

c(n, k) = ∑_{k′=0}^{k−1} F (0, k′) + ∑_{n′=0}^{n−1} G(n′, k) ,

or equivalently

c(n, k) = ∑_{n′=0}^{n−1} G(n′, 0) + ∑_{k′=0}^{k−1} F (n, k′) .

Note that c(n, k) are all diophantine approximations to the constant c. Indeed the definition of c is c(0, ∞) and the ‘accelerated version’ is c(∞, 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}^{∞} such that for some δ > 0, there exists a constant C such that

|\frac{e_{m}}{f_{m}} − c| ≤ \frac{C}{f_{m}^{1+δ}} ,

then we immediately have a proof that c is irrational. Unfortunately, this didn’t happen yet (even for Apéry’s spectacular sequences for log 2, ζ(2) and ζ(3), that needed weighted-averaging), but in our experiments we obtained (empirically) δ’s that, while negative, were pretty close to 0. If you take a random sequence and a random constant, δ would be −1 or very close to it, so any δ 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éry’s[Ap] brilliant method (see [Z2] and [Z3]), consists of finding a ‘clever’ averaging function b(n, k) such that

\frac{e_{n}}{f_{n}} := \frac{∑_{k=0}^{n} b(n, k)c(n, k)}{∑_{k=0}^{n} b(n, k)} ,

or in, the present, Markovian notation, where the natural habitat of c(n, k) is the discrete positive quadrant:

\frac{e_{n}}{f_{n}} := \frac{∑_{x+y=n} b(x, y)c(x, y)}{∑_{x+y=n} b(x, y)} ,

turns out to be a successful rational-approximating sequence with a positive δ. As we said above, our (and quite a few other people’s) dream is to emulate Apéry for ζ(5) and beyond.

How to (Who Knows?) Fulfill Our Dream

In addition to producing irrationality proofs, Apéry’s method also yields, as a bonus, convergenceacceleration series for the constants in question. Hitherto, even the latter were not possible for ζ(5) and beyond, but now, with the extended notion of MWZ pairs, our computer easily cranks out amazingly fast series for ζ(5), ζ(7), …, 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.

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!

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.

A User’s Manual for the Maple package MarkovWZ

This is implemented in the Maple package MarkovWZ downloadable from the webpage of this article

http://www.math.rutgers.edu/~zeilberg/Markov/marwz.html ,

that also has sample input and output.

To use the program, save it as MarkovWZ, stay in the same directory, go into Maple, and type:

read MarkovWZ; ,

and then follow the on-line instructions.

The main functions are Markov, ACC, and WtAve. The functions H1 := (−1)^{z}z!/(x + z + 1)!, for log 2, H2 := (−1)^{z}(2z!/(x + z + 1))/(2x + z + 1)! for ζ(2), H3 := (z!/(2x + z + 1)!)/(x + z + 1)^{2} for ζ(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 ζ(2), say, type:

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 A above. The third part is just the list of powers [1, k, …, 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 verbose version of Markov, with all the details, for the benefit of humans, is procedure Markov-

Paper.

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

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 A (same as in 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) = … = 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 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 verbose version of ACC, will all the details, for the benefit of humans, is procedure ACCpaper. Procedures Appx and Appxf use ACC to find numerical approximations. Procedure delt empirically (and of course, approximately) finds the above δ for a specific approximation. Procedure 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:

z2:=WtAve(Markov(H2,z,x),z,x,binomial(z+2*x,x)*binomial(x+z,z)**2,30);
z3:=WtAve(Markov(H3,z,x),z,x,binomial(z+2*x,x)**2*binomial(x+z,z)**2,30).

Typing delt(z2,Zeta(2)); and delt(z3,Zeta(3)); would yield positive numbers, confirming (empirically), Apéry’s historic constructions. There is also a new version of Zeilberger’s algorithm (Zeil), that today is part of Maple’s SumTools package. It is one of the main functions of Zeilberger’s package EKHAD. The new version uses GosperWithParameters directly, and seems to be much more efficient than EKHAD, and a little more efficient than SumTools. 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) = \frac{d}{dx}G(n, x) that uses an extension of the Almkvist-Zeilberger algorithm ([AlZ]), is implemented in MarkovAZ. The simple extension for finding pairs satisfying \frac{d}{dx}F (n, x) = G(n + 1, x) − G(n, x) is done in ContMarkovWZ. The q-analog of this paper will appear in [Mo2]. Appendix: An example As mentioned in the preface, many examples, both tersely and verbosely, are given in the Examples webpage of this article http://www.math.rutgers.edu/˜ zeilberg/Markov/Examples.html. Better still, use procedures MarkovPaper and ACCpaper in the Maple package MarkovWZ, to get as many examples as you wish. 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) := ( \begin{matrix}\frac{1}{2} & \frac{3n+2}{4} & \frac{3n(n+1)}{8}, \\ \frac{−3}{2(n+1)} & \frac{−(7n+4)}{4(n+1)} & \frac{−3n+2}{8} \\ \frac{3}{2(n+1)^{2}} & \frac{3n}{4(n+1)^{2}} & \frac{−(5n+2)}{8(n+1)} \end{matrix} ) .

In other words, a(n) = A(n − 1)A(n − 2)...A(0) times [1, 0, 0]^{T}. Let

F (n, k) = \binom{n}{k}^{3}(a_{0}(n) + a_{1}(n)k + a_{2}(n)k^{2}) .

We have, for every non-negative integer n

∑_{k} F (n, k) = 1 .

Proof: We cleverly construct

G (n, k) = \binom{n}{k}^{3}·

(−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}})

with the motive that

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) ,

(check!), and the identity follows upon summing with respect to k. QED. References

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

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

[AmZ2] T. Amdeberhan and D. Zeilberger, q-Apéry Irrationality Proofs by q-WZ Pairs, Adv. Appl. Math. 20, 275-283, (1998). [available on-line from the authors’ websites.]

[Ap] R. Apéry, “Interpolation de fractions continues et irrationalité de certaine constantes” Bulletin de la section des sciences du C.T.H.S. #3 p. 37-53, 1981.

[F] S. Fischler, Irationalité de valeurs de zêta [d’après Apéry, Rivoal, ... ], Séminaire Bourbaki-Novembre 2002, Exposé numéro 910;, to appear in Astérique. Available On-line from arXiv.org.

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

[KS2] M. Kondratieva and S. Sadov, Markov’s transformation of series and the WZ method, to

appear in Adv. Appl. Math. Available from http://xxx.arXiv.org/math.CA/0405592.

[M] A.A. Markoff, Mémoire sur la transformation des séries peu convergentes en séries très convergentes, Mémoires de L’Académie Impériale des Sciences de St.-Pétersbourg, V II^{e} Série. Tome XXXVII, N^{o} 9.

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

[Mo2] M. Mohammed, The q-Markov-WZ Method, in preparation.

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

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

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

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

[Z3] D. Zeilberger, Computerized Deconstruction, Adv. Applied Math. 30 (2003), 633-654. [available on-line from the author’s website.]