PFAFF’S METHOD (III): COMPARISON WITH THE WZ METHOD

by George E. Andrews^{1}

Dedicated to my friend, Dominique Foata.

Abstract. In the 1990’s, the WZ method has been the method of choice in resolving new conjectures for hypergeometric identities. The object here is to compare the WZ method with Pfaff’s method. Such a comparison should (it is hoped) provide some suggestions for the further development of each method.

Submitted: December 2, 1994; Accepted: November 13, 1995

1. Introduction. The first two papers in this series raise the following obvious question: Why should anyone want to resurrect a method last used in 1797 to sum hypergeometric series when it is well-known that the WZ method [13] has swept all before it.

This latter state of affairs has been spelled out in delightful albeit idiosyncratic detail by Zeilberger in [16] and [17]. The reader is urged to consult these references for the complete understanding of his philosophy. Perhaps the case can be put succinctly by referring to his Meta-theorem [16] which asserts that the verification of \underline{any} binomial coefficient identity via the WZ method is routine.

To be fair, it should be noted that Zeilberger softens this position a bit in [17]: “This algorithm [the WZ method] can be performed successfully on all natural identities we are now aware of. It is easy, however, to concoct artificial examples for which the running time and memory are prohibitive. Undoubtedly, in the future natural identities will be encountered whose complete proof will turn out to be not worth the money.”

Typeset by AMS-TEX the electronic journal of combinatorics 3 (2) (1996), #R21 2

1Partially supported by National Science Foundation Grant DMS 8702695-04

To my mind, Zeilberger’s mathematical discoveries on this topic are powerful and important while his philosophical conclusions are quite wrong-headed.

It is certainly true that the WZ method has been effectively automated by Zeilberger [14]; however, the computational complexity of the method has not been carefully examined to my knowledge. This state of affairs will become much clearer (or perhaps less clear) in Section 5 where we discuss a theorem (eq. (5.5)), that may well not be worth the money to prove via the WZ method.

While I hope that some of the grandiose claims in [16] and [17] for the WZ method might be modified, the last thing I wish to suggest is that Pfaff’s method is a replacement. I shall emphasize my admiration for the WZ method in Section 7.

Section 2–4 will compare proofs of theorems for which both Pfaff and WZ are quite successful.

2. Pfaff’s Theorem.

When we consider Pfaff’s original theorem (known today as the Pfaff-Saalschutz summation), we find that there is little to prefer in the proofs supplied by WZ and Pfaff.

The identity in question is

(2.1)  S_{m}(a, b, c) = m ; ∑_{r=0}F_{1}(m, r) : = m ; ∑_{r=0} \frac{(−m, a, b)_{r}}{(1, c, 1 − m − c + a + b)_{r}}

= \frac{(c − b, c − a)_{m}}{(c, c − a − b)_{m}} ,

where

(2.2)  (A_{1}, …, A_{r})_{n} = r ; ∏_{j=1} n−1 ; ∏_{i=0} (A_{j} + i).

Pfaff’s proof [11; p. 51] (cf. [2; §2]) proceeds by mathematical induction with the initial value S_{0}(a, b, c) = 1 and the recurrence

(2.3) S_{m}(a, b, c) − S_{m−1}(a, b, c) =

\frac{−(1 + a + b − c)a b S_{m−1}(a + 1, b + 1, c + 1)}{c(1 + a + b − c − m)(2 + a + b − c − m)}.

the electronic journal of combinatorics 3 (2) (1996), #R21 3

The WZ method (utilizing Zeilberger’s method of creative telescoping [15]) establishes a different recurrence

(2.4) (−m + b − c)(−m + a − c)S_{m}(a, b, c)

+ (c + m)(−m + a + b − c)S_{m+1}(a, b, c) = 0

Now (2.4) is a more natural recurrence than (2.3); indeed (2.4) immediately suggests the final line of (2.1), while it comes as a surprise that the final line of (2.1) satisfies (2.3).

On the other hand, (2.3) is merely term-by-term differencing of two sums while the WZ method proves (2.4) by showing that

(2.5) (−m + b − c)(−m + a − c)F_{1}(m, r) − (c + m)(−m + a + b − c)F_{1}(m + 1, r) = G_{1}(m, r) − G_{1}(m, r − 1)

where

(2.6)  G_{1}(m, r) = (a + r)(b + r)F_{1}(m, r)

is the auxiliary function called the \underline{certificate} [13]. Equation (2.4) is then deduced by summing (2.5) from r = 0 to r = m + 1.

Thus I would suggest that neither method is innately superior in proving (2.1). Kummer’s theorem [6; §2.3] (cf. [2; §3]) was the next example considered in our

exposition of the Pfaff method. Again in this case, Pfaff’s method and the WZ method are different but no more so than in their application to (2.1).

3. Bailey’s Theorem.

The result in question [5; p. 512, eq. (c)] is

(3.1)  B_{m}(a, b) = m ; ∑_{r=0} F_{2}(m, r)

= m ; ∑_{r=0} \frac{(\frac{a}{2}, \frac{(a+1)}{2}, b + m, −m)_{r}}{(1, \frac{b}{2}, \frac{(b+1)}{2}, a + 1)_{r}}

= \frac{(b − a)_{m}}{(b)_{m}} .

the electronic journal of combinatorics 3 (2) (1996), #R21 4

The two methods now diverge completely. The WZ method produces a second order recurrence for B_{m}(a, b), namely

(3.2) (m + 1)(−m − b + a)B_{m}(a, b)

+ (−a^{2} + ba − a + 2mb + 3b + 2 + 4m + 2m^{2})B_{m+1}(a, b)

− (b + m + 1)(a + 2 + m)B_{m+2}(a, b) = 0

and proves it by showing that if

(3.3)  G_{2}(m, r) = −\frac{(a + 1 + 2r)(a + 2r)(b + m + r)(m + 1)}{(b + m)(m − r + 1)}F_{2}(m, r)

then

(3.4) (m + 1)(−m − b + a)F_{2}(m, r)

+ (−a^{2} + ba − a + 2mb + 3b + 2 + 4m + 2m^{2})F_{2}(m + 1, r)

− (b + m + 1)(a + 2 + m)F_{2}(m + 2, r)
= G_{2}(m, r) − G_{2}(m, r − 1).

Identity (3.2) then follows by summing (3.4) from r = 0 to r = m + 2 (i.e. Zeilberger’s creative telescoping [15]).

This, of course provides a perfectly valid proof of (3.1); however we note the inability of the WZ method to establish directly

(3.5)  (b + m)B_{m+1}(a, b) − (b − a + m)B_{m}(a, b) = 0.

The Pfaff method, on the other hand, cannot handle (3.1) by itself. It must simultaneously prove that [3; p. 2, eq. (2.3)]

(3.6)  C_{m}(a, b) = m ; ∑_{r=0} \frac{(\frac{a}{2}, \frac{(a+1)}{2}, b + m − 1, −m)_{r}}{(1, \frac{b}{2}, \frac{(b+1)}{2}, a)_{r}}

= \frac{(b − a)_{m}}{(b + 2m − 1)(b)_{m−1}} .

Pfaff’s method proceeds now as in Section 2. Here we find directly [2; §4]

(3.7)  B_{m}(a, b) − C_{m}(a, b) = \frac{m(b + m − a − 1)}{b(b + 1)}C_{m−1}(a + 2, b + 2),

and

(3.8)  C_{m}(a, b) − B_{m−1}(a, b) = \frac{(a + m)(1 − b − m)}{b(b + 1)}C_{m−1}(a + 2, b + 2).

Pfaff’s method then concludes by the observation that the right-hand sides of (3.1) and (3.6) also satisfy (3.7) and (3.8).

Thus Pfaff’s method requires \underline{two} first order recurrences based on \underline{two} conjectured summation identities (i.e. (3.1) and (3.6)). In some sense, both methods work twice as hard as in Section 2; however, Pfaff’s method proves twice as much for twice as much work.

4. Dougall’s Theorem.

Here again the two methods diverge. The WZ method operates without a hitch as has already been shown by Zeilberger and his computer [7].

Namely, if a + f = −m and b + c + d + e = m + 1, then

D_{m}(a, b, c, d) = m ; ∑_{r=0} F_{3}(m, r) (4.1)

= m ; ∑_{r=0} \frac{(2a, a + 1, a + b, a + c, a + d, a + e, a + f)_{r}}{(1, a, 1 + a − b, 1 + a − c, 1 + a − d, 1 + a − e, 1 + a − f)_{r}}

= \frac{(2a + 1, 1 − c − d, 1 − b − d, 1 − b − c)_{m}}{(1 − a − b − c − d, 1 + a − b, 1 + a − c, 1 + a − d)_{m}} .

The WZ-method produces the certificate function

(4.2) G_{3}(m, r) = −F_{3}(m, r)(2a + r)(1 + 2a + m)

× \frac{(a+2m+2−b−c−d)(a−b−c−d+m+1+r)(a+d+r)(a+c+r)(a+b+r)}{2(a + r)(2a + m + 1 + r)(1 + a − b − c − d + m)}

and it is then immediate that

(4.3) (−m + d − 1 + c)(b − m + d − 1)(b + c − 1 − m)(1 + 2a + m)F_{3}(m, r)
− (m+a−d+1)(a−c+1+m)(a+1+m−b)(b+c+d+a−m−1)F_{3}(m+1, r)
= G_{3}(m, r) − G_{3}(m, r − 1),

and consequently by summing (4.3) from r = 0 to m + 1 we find

(4.4)(−m + d − 1 + c)(b − m + d − 1)(b + c − 1 − m)(1 + 2a + m)D_{m}(a, b, c, d)

− (m+a−d + 1)(a−c+1+m)(a+1+m−b)(b+c+d+a−m−1)D_{m+1}(a, b, c, d) = 0 .

In contrast, Pfaff again is unable to prove the required result by itself. In this instance, one is forced to prove a much less known companion identity due to A. Lakin [10].

Namely if a + f = −m and b + c + d + e = m, then

(4.5)  E_{m}(a, b, c, d) = m ; ∑_{r=0} F_{4}(m, r)

= m ; ∑_{r=0} \frac{(2a, a + 1, a + b, a + c, a + d, a + e, a + f)_{r}}{(1, a, 1 + a − b, 1 + a − c, 1 + a − d, 1 + a − e, 1 + a − f)_{r}}

= \frac{a_{3} · (1 − b − c, 1 − b − d, 1 − c − d)_{m−1}(1 + 2a)_{m}}{(1 + a − b, 1 + a − c, 1 + a − d, −a − b − c − d)_{m}} ,

where a_{3} = a_{3}(a, b, c, d, e, f) is the third elementary symmetric function of a, b, c, d, e and f.

The Pfaff method now proceeds as before. In this case,

(4.6) D_{m}(a, b, c, d) − E_{m}(a, b, c, d)

= \frac{−(2a+1)(2a+2)(a+b)(a+c)(a+d)m D_{m−1}(a+1, b, c, d)}{(1+a−b)(1+a−c)(1+a−d)(1+2a+m)(a−m+b+c+d)(1+a−m+b+c+d)} ,

and

E_{m}(a, b, c, d) − D_{m−1}(a, b, c, d) (4.7)

= \frac{(2a + 1)(2a + 2)(a + b)(a + c)(a + d)(b + c + d − a − m)D_{m−1}(a + 1, b, c, d)}{(1 + a − b)(1 + a − c)(1 + a − d)(1 + a − m + b + c + d)(2a + m)(2a + m + 1)} .

To conclude the simultaneous proof of Dougall’s (4.1) and Lakin’s (4.5) theorems, one verifies that the right-hand sides satisfy (4.6) and (4.7) also.

In this section then, the WZ method has been fast and elegant. The Pfaff method has required the unearthing of an almost forgotten result [10]. It has produced more

the electronic journal of combinatorics 3 (2) (1996), #R21 7

but with twice the effort. If Lakin’s result had been totally forgotten, considerable computer time would have been required to find it.

It is perhaps instructive to refer to the WZ method applied to Lakin’s series. Note the complexity that a_{3}(a, b, c, d, e, f) introduces. In this instance

G_{4}(m, r) = \frac{F_{4}(m, r)}{(a + r)(a − b − c − d + m)(2a + m + 1 + r)}

× (3a + 3m + 1 − b − d − c + 2a^{2} + 5ma − 2ab − 2ad − 2ac + 2m^{2} −bm − dm − cm)(2a + r)(a + b + r)(a + c + r)(a + d + r)

(a − b − c − d + m + r)(m + 2ma + 2bcd + m^{2} + a^{2}m + c^{2}d + cd^{2}

+bc^{2} + b^{2}c + b^{2}d + bd^{2} − 2cdm − 2bdm − 2bcm − c^{2}m − d^{2}m +dm^{2} + am^{2} + bm^{2} + cm^{2} − b^{2}m − r − 2ra − r^{2}),

and the relevant final recurrence is

2(−m + c + d)(−m + d + b)(b + c − m)(1 + 2a + m)(a + b + c + d − d^{2}m

+a^{2} − 2cdm − 2bcm − 2bdm + 2cm + 2dm + cd^{2} + am^{2} + b^{2}c
+bc^{2} + b^{2}d + bd^{2} + 2bm + dm^{2} + cm^{2} + bm^{2} − c^{2}m − b^{2}m + a^{2}m
+2ma + c^{2}d + 2bcd − b^{2} − 2bc − 2bd − c^{2} − d^{2} − 2cd)E_{m}(a, b, c, d) − 2

(1 + a − d + m)(a + 1 + m − c)(1 + a − b + m)(b + c + d + a − m)(a^{2}m

+am^{2} + bm^{2} − d^{2}m + dm^{2} − c^{2}m + cm^{2} − 2bdm + cd^{2} + b^{2}d + bd^{2}
+c^{2}d + bc^{2} + 2bcd + b^{2}c − 2bcm − b^{2}m − 2cdm)E_{m+1}(a, b, c, d)
= 0.

It should be pointed out here that Pfaff’s method has been able to act with simpler recurrences in Sections 3 and 4 because it relies on shifts of parameters in addition to the shift of the index m.

5. The _{5}F_{4} Summation. (Part I).

In the first paper in this series [1], we used Pfaff’s method to prove that

(5.1)  H(m, m + 1; x, z; 0, 0, 0) = 0,

where

(5.2) H(n, m; x, z; a_{1}, a_{2}, a_{3}) =

n+m ; ∑_{r=0} \frac{(−n − m, x + m + n + 1 + a_{1}, x − z + \frac{1}{2}, x + m + a_{1}, z + n + 1)_{r}}{(1, \frac{(x+1)}{2}, 1 + \frac{x}{2}, 2z + m + n + 1 + a_{3}, a_{1} + a_{2} − a_{3} + 1 + 2x − 2z)_{r}} .

The proof resembled the Pfaff method proofs already examined in this paper. The only difference was that it was \underline{necessary} to prove \underline{twenty} identities simultaneously of which (5.1) was just one. Thus, in addition to (5.1), we also proved, for example,

(5.3)  H(n − 1, n + 1; x, z; 0, 0, 0) = P_{n},
(5.4)  H(n − 1, n + 1; x, z; 1, 0, 1) = \frac{(z + 3n + 1)(2z + 2n + 1)P_{n}}{(z + n + 1)(2z + 4n + 1)} ,

(5.5)  H(n, n; x, z; 0, −1, 0) = \frac{(x + n − 2)_{3}(z − x − n)(2z − x + 2n)_{2}P_{n}}{(x + 2n − 2)_{3}(z − x)(2z − x + n)_{2}} ,

plus sixteen similar results; here

(5.6)  P_{n} = \frac{(\frac{1}{2})_{n}(2z − x)_{2n}}{(1 + x, 1 + x − z, z + n + \frac{1}{2})_{n}} .

These twenty results were proved simultaneously by proving twenty first order recurrences quite reminiscent of the Pfaff method recurrences considered here in Sections 2–4.

For example [1; eq. (5.12)] (5.7)

\begin{matrix}H(n, n + 1; x, z; 0, 0, 0) − H(n − 1, n + 1; x, z; 1, 0, 1) \\ = \frac{−(x + 2n + 2)(x + n + 1)(z + 3n + 1)H(n − 1, n + 1; x + 2, z + 1; 0, −1, 0)}{(x + 1)(x + 2)(z + n + 1)} . \end{matrix}

To summarize, the Pfaff method is cumbersome for this problem. No single step is substantially more difficult than the steps in Pfaff’s own work (i.e. Section 2). However, the proof of twenty theorems simultaneously requires a good deal more than twenty times the effort required in Section 2. First the twenty results like (5.1) and (5.3)–(5.5) must be found empirically. Then twenty recurrences must be selected from a multitude in order to prove all twenty results.

In contrast, the application of the WZ method to prove (5.1) and (5.5) is ongoing. The question of whether WZ could prove (5.1) was raised at the Ann Arbor Conference on Combinatorics in Juen, 1994. Theoretically there is no doubt that the WZ method can produce a proof of both (5.1) and (5.5) eventually.

After the conference, Zeilberger developed a modification of the WZ method designed to exploit the shifts of parameters that are so effective in the Pfaff approach.

The following is a summary of accomplishment of the WZ method in treating (5.1) and (5.5).

First we let

(5.8)  SUM_{5}(m) = 2m+1 ; ∑_{r=0} F_{5}(m, r) = H(m, m + 1; \frac{1}{2}, \frac{1}{7}; 0, 0, 0).

Then SUM_{5}(m) satisfies the following linear recurrence equation (graciously supplied by Zeilberger)

− 32(28m + 39)(7m + 3)(14m + 51)(14m + 37)(14m + 23)(28m + 25) (5.9)

(m + 3)(m + 2)(m + 1)(48404160m^{5} + 650574960m^{4} + 3475419668m^{3} + 9220308013m^{2}+12143442283m + 6349305966) SUM_{5}(m)+(14m+51)(14m+37) (m + 3)(m + 2)(2052881608458240m^{10} + 42501662244679680m^{9} + 390743281356352512m^{8} + 2100174572137651968m^{7} + 7306673651176734016m^{6}

the electronic journal of combinatorics 3 (2) (1996), #R21 10

+ 17190295272081840272m^{5} + 27693538350246233892m^{4} + 30161825946242028661m^{3} + 21251926021693940972m^{2} +8746561907032071897m+1596513339149652990) SUM_{5}(m+1)−(11+4m)(9+4m) (14m + 51)(m + 3)(2108666434775040m^{10} + 48146953846924800m^{9} + 489608903878090752m^{8}+2918230750107019200m^{7}+11282101773457441192m^{6} + 29539117178236394078m^{5} + 52998108990043064127m^{4} + 64278081153960331000m^{3} + 50379935406843856835m^{2} + 23014310447535882468m + 4646640934819526400) SUM_{5}(m+2)+112(7m+19) (14m + 43)(15 + 4m)(11 + 4m)(7m + 27)(14m + 45)(7m + 25) (13 + 4m)(9 + 4m)(48404160m^{5} + 408554160m^{4} + 1357161428m^{3} + 2213457169m^{2} + 1768806221m + 552922828) SUM_{5}(m + 3) = 0.

This is proved by constructing a gigantic certificate function

G_{5}(m, r) = (5.10)

\frac{−48(8 + 7m + 7r)(6 + 7r)(3 + 2m + 2r)(5 + 4m + 2r) × Z_{5}(m, r) × F_{5}(m, r)}{(51 + 14m + 7r)(44 + 14m + 7r)(37 + 14m + 7r)}

× \frac{1}{(30 + 14m + 7r)(23 + 14m + 7r)(16 + 14m + 7r)(7 + 4m)(5 + 4m)}

× \frac{1}{(2m + 2 − r)(2m + 3 − r)(2m + 4 − r)(2m + 5 − r)(2m − r + 6)}

where

(5.11)  Z_{5}(m, r) =
(247499997577986751086387497363968m^{14} + …
− 3014392481949633188462695880712 r^{6}m^{9}
+ ⋯ + 780611738186705500427885113128576m^{13}),

a polynomial of 180 terms with coefficients often in the nonillions or decillions.

the electronic journal of combinatorics 3 (2) (1996), #R21 11

Zeilberger discovered that the shifts x → x − m, z → z − m greatly improve the effectiveness of the WZ-method. He was then able to obtain the following results for

(5.12)  SUM_{6}(n, x, z) = 2n+1 ; ∑_{k=0}F_{6}(n, x, z, k)
H(n, n + 1; x − n, z − n; 0, 0, 0).

Then SUM_{6}(n, \frac{1}{2}, z) satisfies

(16(18n + 65)(5 + 2n)(2n + 3)(n + 3)(n + 2)(n + 1)(2n + 3 + 4z) (5.13)

(2n + 3 − 4z) − (5 + 2n)(−1 + 2n)(n + 3)(n + 2)(2160 n^{4} + 22848 n^{3} + 89640 n^{2} − 5184 n^{2}z^{2} − 33408 n z^{2} + 155440 n + 100975 − 52976 z^{2})N+ (7 + 2n)(1 + 2n)(−1 + 2n)(n + 3) (432 n^{4} + 5160 n^{3} − 216 n^{2} z^{2} + 22920 n^{2} − 1212 n z^{2} + 44866 n + 32653 − 1628 z^{2}) N^{2} + (9 + 2n)(7 + 2n)(2n + 3)(1 + 2n)(−1 + 2n)(18n + 47)

(n + 4 + z)(n + 4 − z)N^{3}) SUM_{6}(n, \frac{1}{2}, z)

= 0,

where N f(n) = f(n + 1). The related certificate function is

(5.14)  G_{6}(n, k, \frac{1}{2}, z) = F_{6}(n, k, \frac{1}{2}, z)\frac{×24Z_{6}(n, k)}{(−2n − 2 + k)_{5}} ,

with

Z_{6}(n, k) = (5.15)
− 5616 n^{7} − 3888 k n^{7} + 3888 k^{2} n^{6} − 97776 n^{6} − 62208 k n^{6} − 411048 k n^{5}
+ 60264 k^{2} n^{5} − 716368 n^{5} − 1442840 k n^{4} − 2857148 n^{4} + 380340 k^{2} n^{4}
− 2875087 k n^{3} − 6681313 n^{3} + 1245566 k^{2} n^{3} − 9126778 n^{2} − 3205042 n^{2} k
+ 2218368 k^{2} n^{2} − 1814957 n k − 6707611 n + 2018002 k^{2} n + 721236 k^{2}
− 2029206 − 394890 k

the electronic journal of combinatorics 3 (2) (1996), #R21 12

Using his shift modification of the WZ method, Zeilberger has found a recurrence for the full S_{6}(n, x, z) thus giving a new proof of (5.1), and recently Peter Paule has obtained the relevant certificate without the shift modification. Both the recurrence and the certificate function are too long to be included here. Suffice it to say that the large polynomial (analogous to (5.11)) in n, k, x and z arising in Zeilberger’s certificate function has 944 terms by my count and occupies twelve pages of printout.

At this moment, (5.5) still not yielded to the WZ method or its modifications. However it is surely only a matter of time before improvements in MAPLE combined with larger machines will produce a recurrence satisfied by (5.5).

Suppose that we actually had in hand the mega-massive general certificate function. We would then have a proof of (5.5) with little insight gained and by means of a recurrence so huge that no hand calculation could check it.

In contrast, Pfaff’s method actually succeeds in proving (5.1) and (5.5) plus eighteen other identities. The proof is checkable by hand at each step. Also we learn that there is a cluster of identities (the computer suggests ≧ 50, [1; §6]) intimately tied up with (5.1); each of these other identities conveys more information about its structure than (5.1) because (5.1) is the only one for which the right hand side is identically zero.

6. The _{5}F_{4} Summation (Part II): The Wilf-Petkovsek Summation.

Several months after the end of the “contest” described in Section 5, Wilf and Petkovsek [in a paper published in this volume] using the WZ methodology proved in a direct and efficient way the most important special case of (5.1) (namely when z is restricted to a certain class of integers). While this is not the full (5.1), it is nonetheless quite adequate to do the entire evaluation of the Mills-Robbins-Rumsey determinant as presented in Section 7 of [1].

Given the parallelism that we have thus far described between Pfaff proofs and WZ-proofs, it is natural to ask if, inspired by the success of Wilf and Petkovsek, we can find a correspondingly easier proof of the following special case of (5.1). Let n and v be non-negative integers with v ≦ n,

(6.1)  \begin{matrix}W_{n}(v, μ) := H(v − 1, v; μ − v + 2, −n − v + 1; 0, 0, 0) \\ = n−1 ; ∑_{h=0} \frac{(1 − 2v, v + μ + 2, −n + 1, μ + 2, μ + n + 3/2)_{h}}{(1, (μ − v + 3)/2, (μ − v + 4)/2, 2 − 2n, 2μ + 2n + 3)_{h}} \end{matrix}

Then for v and n nonnegative integers,

(6.2)  W_{n}(v, μ) = \{ \begin{matrix}0 & if v < n \\ \frac{(μ + 2n + 3/2)_{n−1}(n − 1)!}{(−1 − μ)_{n−1}(1/2)_{n−1}} & if v = n. \end{matrix}

The proof of (6.2) is now quite straightforward. The bottom line follows easily from classical summations, and the top line follows directly from an application of Pfaff’s method.

To see the bottom line we note

W_{n}(n, μ) (6.3)

= _{5}F_{4} [ \begin{matrix}1 − 2n, n + μ + 2, −n + 1, μ + 2, μ + n + 3/2 ; 1 \\ (μ − n + 3)/2, (μ − n + 4)/2, −2n + 2, 2μ + 2n + 3 \end{matrix} ]

= \frac{(2 + μ + 2n)_{n−1}}{(−1 − μ)_{n−1}} n−1 ; ∑_{i=0} \frac{(2 + 2μ + 4n)_{i}(1 − n)_{i}}{(2 − 2n)_{i}(2 + μ + 2n)_{i}}

(by [6; p. 30, eq.(1) with a = 2μ + 2n + 3,

b = 2 + 2μ + 4n, c = 1, m = n − 1, w = 2 + μ + 2n])

= \frac{(μ + 2n + 3/2)_{n−1}(n − 1)!}{(−1 − μ)_{n−1}(1/2)_{n−1}}

(by [6; p. 16, §3.3, eq.(1) with a = 1,

b = 2 + 2μ + 4n, c → 1 − n)

Hence the bottom line of (6.2) is proved.

For the top line of (6.2), we proceed using Pfaff’s method:

W_{n+1}(v, μ) − W_{n}(v, μ) (6.4)

= n ; ∑_{h=0} \frac{(1 − 2v, v + μ + 2, μ + 2)_{h}}{(1, (μ − v + 3)/2, (μ − v + 4)/2)_{h}}

× \{\frac{(−n)_{h}(μ + n + 5/2)_{h}}{(−2n)_{h}(2μ + 2n + 5)_{h}} − \frac{(−n + 1)_{h}(μ + n + 3/2)_{h}}{(−2n + 2)_{h}(2μ + 2n + 3)_{h}} \}

= − n ; ∑_{h=0} \frac{(1 − 2v, v + μ + 2, μ + 2)_{h}(1 − n)_{h−1}(μ + n + 5/2)_{h−1}}{(1, (μ − v + 3)/2, (μ − v + 4)/2)_{h}(−2n)_{h+2}(2μ + 2n + 3)_{h+2}}

× h(h − 1)(μ + h + 2)n(2n + 2μ + 3)(4n + 2μ + 3)

= \frac{(4n + 2μ + 3)(2v − 1)(v − 1)(v + μ + 2)(v + μ + 3)(μ + 2)(μ + 3)(μ + 4)}{(μ − v + 3)(μ − v + 4)(μ − v + 5)(μ − v + 6)(2n − 1)(2n − 3)(μ + n + 2)(μ + n + 3)}

× W_{n−1}(v − 1, μ + 3).

Once (6.4) is established we may set v = n and use the bottom line of (6.2) to conclude

W_{n+1}(n, μ) = 0.

Then by induction on i using (6.4) recursively, we conclude that for 0 ≦ i ≦ n

W_{n+1}(n − i, μ) = 0,

i.e. the top line of (6.2) is valid.

This, then, is the result obtained by Wilf and Petkovsek and is sufficient to effect the evaluation of the Mills-Robbins-Rumsey determinant in [1].

7. A Paean to the WZ-Method.

Given the contest atmosphere created by Sections 5 and 6, it seems appropriate to devote some time to the countless instances wherein the WZ-method succeeds completely and Pfaff’s method falls on its face.

The WZ method has successfully found a recurrence for the _{6}F_{5} appearing in (8.1) of [2]. This identity was posed as a conjecture at the Ann Arbor Conference on Algebra and Combinatorics in June 1994. D. Stanton observed that it is a special case of [8; eq. (1.8)] and subsequently D. Zeilberger proved it by using the

the electronic journal of combinatorics 3 (2) (1996), #R21 15

WZ method to find a recurrence. A fuller account will appear elsewhere [4]. In addition, I have been unable to prove any “series to series” identities using Pfaff. Perhaps Whipple’s celebrated theorem [12] (cf. [6; p. 25, eq. (4)]) will be the most instructive example.

W (m) : = m ; ∑_{r=0} \frac{(2a, 1 + a, a + b, a + c, a + d, a + e, −m)_{r}}{(1, a, 1 + a − b, 1 + a − c, 1 + a − d, 1 + a − e, 1 + a + m)_{r}} (7.1)

= \frac{(1 + 2a, 1 − d − e)_{m}}{(1 + a − d, 1 + a − e)_{m}} m ; ∑_{r=0} \frac{(1 − b − c, a + d, a + e, −m)_{r}}{(1, 1 + a − b, 1 + a − c, d + e − m)_{r}}

The left-hand side of (7.1) is one parameter freer than the series in (4.1) and consequently any generalization of the recurrences in Section 4 would presumably involve a shift of a to a + 1 with b, c, d and e unaltered.

On the other hand the right-hand side is a balanced series and is thus amenable to Pfaff’s method as outlined in [1; §2] (see also Sections 2 and 3 of this paper). This approach would yield shifts of a → a + \frac{1}{2} b → b − \frac{1}{2}, c → c − \frac{1}{2}, d → d + \frac{1}{2}, e → e + \frac{1}{2}.

As a result there is no obvious, simple way of reconciling the resulting first order recurrences because of the varying parameter shifts.

In contrast, the WZ method smoothly nails Whipple’s theorem by showing that each side of (7.1) satisfies the second order recurrence

(m + 1)(2a + m + 2)(2a + m + 1)(−m − 2 + b + c + d + e)W (m) − (2a + m + 2) (7.2)

(−mde + deb + 3mda − 10 − 12a + 5b − 17m + 5d + 5e + 5c + dec + 3mae − 2db − 2dc − 2eb − 2ec + 2m^{2}b + 2m^{2}c − 14ma + 6md − 10m^{2} − 2ma^{2} − 4m^{2}a + 2m^{2}d + 2m^{2}e + 6me − 4a^{2} + 4ae + 4da − 2de − 2m^{3} + bcd + a^{2}d + a^{2}e + a^{2}b + a^{2}c + 4ac + 4ba − 2bc − ecm + 3acm − bcm + 3abm − dbm + bce − dcm − ebm + 6mb + 6mc)W (m + 1) − (m − c + 2 + a)(a − e + m + 2)(a − d + m + 2)(a − b + m + 2)W (m + 2) = 0.

the electronic journal of combinatorics 3 (2) (1996), #R21 16

The wide applicability of the WZ method [7], [13], [15], [16], [17] and its beautiful automation by Zeilberger [14] make it a method that will have a permanent place in the theory of hypergeometric series. Certainly Pfaff’s method as currently understood is no match for it in general.

8. Rejoinder.

I asked Doron Zeilberger to comment on the observations within Section 5, and the following is a very slightly edited version of his response:

“The method of creative telescoping of [15] boils down to solving a homogeneous system of linear equations with symbolic coefficients. When there are extra parameters as in Section 5 (x and z, in addition to m), the matrix of coefficients contains polynomials of the three variables (m, x, z). It is very time and memory consuming to solve such a huge system with symbolic coefficients.

“However, it is very fast to obtain the system of equations itself, and the set of variables.

“Because it is very fast to solve the system with specific values assigned to m, x, and z, and the solutions are rational functions of x, z, m, it should be possible (and most likely this has been done for other programming languages) to solve the system for sufficiently many special cases, and then combine them by ‘interpolation’ (using, for example the Fast Fourier Transform). This can also be easily parallelized, so the inability of the WZ method to do (5.5) is far from getting close to the borderline of real-time computational feasibility.

“This still doesn’t explain the ‘slack’ in the order of the recurrence. (5.5) obviously satisfies a first order recurrence, but the method of creative telescoping yields 3 orders too many, i.e. order= 4. A similar situation occurred with Ekhad and Tre’s proof of Andrews’s finite form of Rogers-Ramanujan.

“Very recently Peter Paule showed, how a slight change in the presentation of the data (taking advantage of the symmetry of the summand) gives a much shorter WZ proof, with the minimal recurrence. He also gave many other examples, all with q-series however.

the electronic journal of combinatorics 3 (2) (1996), #R21 17

“Probably a similar situation is responsible to the difficulty of the WZ-proof of (5.5). Unfortunately so far the right symmetry has not been found.”

In addition, Herb Wilf has noted that Marko Petkovsek has developed an algorithm for checking whether a given WZ recurrence might indeed reduce to one of lower order. Thus the combination of this algorithm with the WZ method would produce a first order recurrence for (5.5) once the fourth order recurrence had been determined via WZ. This algorithm would immediately reduce the second order recurrence (3.2) to the desired first order recurrence.

9. Conclusion.

The successive interchanges on how well the WZ method and Pfaff’s method perform have made an interesting contest. Each successive discovery has added insight to our knowledge of this branch of of mathematics. I would hope that one result of this work along with that of Wilf, Petkovsek and Zeilberger is a refutation of the thesis advanced by Zeilberger in [17]. Namely significant amounts of thought have directed computers in discovering mathematics; nowhere in all this did computers do it on their own.

I hope also that positive and constructive conclusions may be drawn from this work. Indeed, I should stress that this is not the first work to examine the limitations of the WZ method. Koorwinder [9] has a lengthy study of the WZ method and includes a discussion of some of its difficulties [9; Ex. 4.2]. In the paper “A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities” by Paule and M. Schorn (to appear in the Journal of Symbolic Computation) the problem of recurrence output with non-minimal order is discussed explicitly. In sect. 4.3 one finds the example

S_{d}(n) := ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{d k}{n} (d ∫ > 0)

for which Zeilberger’s algorithm outputs a recurrence of order d − 1 instead of minimal order 1, which one expect from S_{d}(n) = (−d)^{n}.

Surely, the applications of the WZ method in Section 5 (which completely sur-

prised me) suggest that some analysis of the computational complexity of the WZ

method is in order.

Also, Pfaff’s method itself deserves further scrutiny. It is rare that an elegant

method lies dormant for 200 years and then springs effectively to life.

In closing, I want to thank Doron Zeilberger for numerous helpful discussions

and for supplying all the results described in (5.8)–(5.14).

References

1. G. E. Andrews, Pfaff’s method I: the Mills-Robbins-Rumsey determinant, Discrete Math. (to appear).

2. G. E. Andrews, Pfaff’s method II: diverse applications, J. of Computational and Appl. Math., (to appear).

3. G. E. Andrews and W. H. Burge, Determinant identities, Pac. J. Math., 158 (1993), 1–14.

4. G. E. Andrews and D. Stanton, Determinants in plane partitions enumeration, (to appear).

5. W. N. Bailey, Some identities involving generalized hypergeometric series, Proc. London Math. Soc., Ser. 2, 29 (1929), 503–516.

6. W. N. Bailey, Generalized Hypergeometric Series, Cambridge University Press, London and New York, 1935. [Reprinted: Hafner, New York, 1964].

7. S. B. Ekhad and D. Zeilberger, A 21st century proof of Dougall’s hypergeometric sum identity, J. Math. Analysis and Appl., 147 (1990), 610–611.

8. I. Gessel and D. Stanton, Strange evaluations of hypergeometric series, SIAM J. Math. Anal., 13 (1982), 295–308.

9. T. H. Koornwinder, On Zeilberger’s algorithm and its q-analogue, J. Comp. and Appl. Math., 48 (1993), 91–111.

10. A. Lakin, A hypergeometric identity related to Dougall’s theorem, J. London Math. Soc., 27 (1952), 229–234.

11. J. F. Pfaff, Observationes analyticae ad L. Euler Institutiones Calculi Integralis, Vol. IV, Supplem. II et IV, Historia de 1793, Nova Acta Acad. Sci Petropolitanae 11 (1797), 38–57.

12. F. J. W. Whipple, On well-poised series, generalized hypergeometric series having parameters in pairs, each pair with the same sum, Proc. London Math. Soc. (2), 24 (1926), 247–263.

13. H. S. Wilf and D. Zeilberger, Rational functions certify combinatorial identities, J. Amer. Math. Soc., 3 (1990), 147–158.

14. D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discr. Math., 80 (1990), 207–211.

15. D. Zeilberger, The method of creative telescoping, J. Symbolic Computation, 11 (1991), 195– 204.

16. D. Zeilberger, Identities in search of identity, J. The. Comp. Sci. 117 (1993), 23–38.

17. D. Zeilberger, Theorems for a price: tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc., 40 (1993), 978–981.

THE PENNSYLVANIA STATE UNIVERSITY UNIVERSITY PARK, PA 16802