%% This article has been submitted and accepted for publication in %% THE FOATA FESTSCHRIFT, %% a special issue of THE ELECTRONIC JOURNAL OF COMBINATORICS %% dedicated to DOMINIQUE FOATA at the occasion of his 60th birthday. %% %% Author(s): GEORGE A. ANDREWS %% Title: PFAFF'S METHOD (III): COMPARISON WITH THE WZ METHOD %% Date of submission: December 2, 1994 %% TeX version: AMSTeX %% File size (approx): 32 kB %% Number of pages: 18 %% Author's email: andrews@math.psu.edu %% %% % \magnification=\magstep1 \input amstex \documentstyle{amsppt} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\pf{\hfill\hfill$\qed$} \def\det{\text{det }} \def\b{\binom} \def\c{\cite} \def\d{\Delta} \def\fr{\frac} \def\p{\prod} \def\ub{\underbar} \def\suminf{\overset{\infty}\to{\underset{n=0}\to\sum}} \def\prodni{\overset{n-1}\to{\underset{i=0}\to\prod}} \def\summr{\overset{m}\to{\underset{r=0}\to\sum}} \def\sumnjo{\overset{n-1}\to{\underset{j=0}\to\sum}} \def\prodrj{\overset{r}\to{\underset{j=1}\to\prod}} \def\frr{_{r+1}F_r} \def\mi{\!-\!} \def\pl{\!+\!} \def\l{\left} \def\r{\right} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \leftheadtext{George E. Andrews} \NoBlackBoxes \topmatter \title Pfaff's Method (III): \\ Comparison With the WZ Method \endtitle \author by \\ \\ George E. Andrews$^1$ \endauthor \dedicatory Dedicated to my friend, Dominique Foata. \enddedicatory \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. \endabstract \endtopmatter \centerline{Submitted: December 2, 1994; Accepted: November 13, 1995} \font\smcp=cmcsc8 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 3 (2) (1996), \#R21\hfill\folio} \fi} \document \baselineskip 19pt \footnote"{}"{$^1$Partially supported by National Science Foundation Grant DMS 8702695-04} \subhead 1. Introduction \endsubhead 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 \c{13} has swept all before it. This latter state of affairs has been spelled out in delightful albeit idiosyncratic detail by Zeilberger in \c{16} and \c{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 \c{16} which asserts that the verification of \ub{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 \c{17}: \block ``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.'' \endblock 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 \c{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 \c{16} and \c{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. \specialhead 2. Pfaff's Theorem. \endspecialhead 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 $$ \align S_m(a,b,c)=\summr F_1(m,r):&= \summr\;\fr{(-m,a,b)_r}{(1,c,1-m-c+a+b)_r} \tag2.1 \\ &=\fr{(c-b,c-a)_m}{(c,c-a-b)_m}, \endalign $$ where $$ (A_1,\dots,A_r)_n=\prodrj\;\prodni\;(A_j+i). \tag2.2 $$ Pfaff's proof \c{11; p. 51} (cf. \c{2; \S2}) proceeds by mathematical induction with the initial value $S_0(a,b,c)=1$ and the recurrence $$ \multline S_m(a,b,c)-S_{m-1}(a,b,c)= \\ \fr{-(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)}. \endmultline \tag2.3 $$ The WZ method (utilizing Zeilberger's method of creative telescoping \c{15}) establishes a different recurrence $$ \multline (-m+b-c)(-m+a-c)S_m(a,b,c) \\ +(c+m)(-m+a+b-c)S_{m+1}(a,b,c)=0 \endmultline \tag2.4 $$ 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 $$ \multline (-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) \endmultline \tag2.5 $$ where $$ G_1(m,r)=(a+r)(b+r)F_1(m,r) \tag2.6 $$ is the auxiliary function called the \ub{certificate} \c{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 \c{6; \S2.3} (cf. \c{2; \S3}) 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). \specialhead 3. Bailey's Theorem. \endspecialhead The result in question \c{5; p. 512, eq. (c)} is $$ \align B_m(a,b)&=\summr\;F_2(m,r) \tag3.1 \\ &=\summr\;\fr{(\fr{a}{2},\fr{(a+1)}{2},b+m,-m)_r} {(1,\fr{b}{2},\fr{(b+1)}{2},a+1)_r} \\ &=\fr{(b-a)_m}{(b)_m}\;. \endalign $$ The two methods now diverge completely. The WZ method produces a second order recurrence for $B_m(a,b)$, namely $$ \multline (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 \endmultline \tag3.2 $$ and proves it by showing that if $$ G_2(m,r)=-\fr{(a+1+2r)(a+2r)(b+m+r)(m+1)}{(b+m)(m-r+1)}F_2(m,r) \tag3.3 $$ then $$ \multline (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). \endmultline \tag3.4 $$ Identity (3.2) then follows by summing (3.4) from $r=0$ to $r=m+2$ (i.e. Zeilberger's creative telescoping \c{15}). This, of course provides a perfectly valid proof of (3.1); however we note the inability of the WZ method to establish directly $$ (b+m)B_{m+1}(a,b)-(b-a+m)B_m(a,b)=0. \tag3.5 $$ The Pfaff method, on the other hand, cannot handle (3.1) by itself. It must simultaneously prove that \c{3; p. 2, eq. (2.3)} $$ \align C_m(a,b)&=\summr\;\fr{(\fr{a}{2},\fr{(a+1)}{2},b+m-1,-m)_r} {(1,\fr{b}{2},\fr{(b+1)}{2},a)_r} \tag3.6 \\ &=\fr{(b-a)_m}{(b+2m-1)(b)_{m-1}}\;. \endalign $$ Pfaff's method proceeds now as in Section 2. Here we find directly \c{2; \S4} $$ B_m(a,b)-C_m(a,b)=\fr{m(b+m-a-1)}{b(b+1)}C_{m-1}(a+2,b+2), \tag3.7 $$ and $$ C_m(a,b)-B_{m-1}(a,b)=\fr{(a+m)(1-b-m)}{b(b+1)}C_{m-1}(a+2,b+2). \tag3.8 $$ 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 \ub{two} first order recurrences based on \ub{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. \specialhead 4. Dougall's Theorem. \endspecialhead Here again the two methods diverge. The WZ method operates without a hitch as has already been shown by Zeilberger and his computer \c7. Namely, if $a+f=-m$ and $b+c+d+e=m+1$, then $$ \align &\qquad D_m(a,b,c,d)=\summr\;F_3(m,r) \tag4.1 \\ &=\summr\fr{(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} \\ &=\fr{(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}\;. \endalign $$ The WZ-method produces the certificate function $$ \align &\qquad G_3(m,r)=-F_3(m,r)(2a+r)(1+2a+m) \tag4.2 \\ &\times\fr{(a\pl 2m\pl 2\mi b\mi c\mi d)(a\mi b\mi c\mi d\pl m\pl 1\pl r)(a\pl d\pl r)(a\pl c\pl r)(a\pl b\pl r)} {2(a+r)(2a+m+1+r)(1+a-b-c-d+m)} \endalign $$ and it is then immediate that $$ \align &\qquad(-m+d-1+c)(b-m+d-1)(b+c-1-m)(1+2a+m)F_3(m,r) \tag4.3 \\ &-(m\pl a\mi d\pl 1)(a\mi c\pl 1\pl m)(a\pl 1\pl m\mi b)(b\pl c\pl d\pl a\mi m\mi 1)F_3(m\pl 1,r) \\ &=G_3(m,r)-G_3(m,r-1), \endalign $$ and consequently by summing (4.3) from $r=0$ to $m+1$ we find $$ \align &\quad (-m+d-1+c)(b-m+d-1)(b+c-1-m)(1+2a+m)D_m(a,b,c,d) \tag4.4 \\ &-(m\pl a\mi d+1)(a\mi c\pl 1\pl m)(a\pl 1\pl m\mi b)(b\pl c\pl d\pl a\mi m\mi 1)D_{m\pl 1}(a,b,c,d) \\ &\hbox{\hskip 3in} =0\;. \endalign $$ 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 \c{10}. Namely if $a+f=-m$ and $b+c+d+e=m$, then $$ \align &\quad E_m(a,b,c,d)=\summr\;F_4(m,r) \tag4.5 \\ &=\summr\;\fr{(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} \\ &=\fr{a_3\cdot(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}\;, \endalign $$ 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, $$ \align &\qquad D_m(a,b,c,d)-E_m(a,b,c,d) \tag4.6 \\ &=\fr{\mi (2a\pl 1)(2a\pl 2)(a\pl b)(a\pl c)(a\pl d)m\,D_{m\mi 1}(a\pl 1,b,c,d)} {(1\pl a\mi b)(1\pl a\mi c)(1\pl a\mi d)(1\pl 2a\pl m)(a\mi m\pl b\pl c\pl d)(1\pl a\mi m\pl b\pl c\pl d)}\;, \endalign $$ and $$ \align &\qquad E_m(a,b,c,d)-D_{m-1}(a,b,c,d) \tag4.7 \\ &=\fr{(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)}\;. \endalign $$ 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 \c{10}. It has produced more 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 $$ \gathered G_4(m,r)=\fr{F_4(m,r)}{(a+r)(a-b-c-d+m)(2a+m+1+r)} \\ \times\;(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), \endgathered $$ and the relevant final recurrence is $$ \gathered 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^2m \\ +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. \endgathered $$ 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$. \specialhead 5. The ${\bold{_5F_4}}$ Summation. (Part I). \endspecialhead In the first paper in this series \c1, we used Pfaff's method to prove that $$ H(m,m+1;x,z;0,0,0)=0, \tag5.1 $$ where $$ \multline H(n,m;x,z;a_1,a_2,a_3)= \\ \overset{n+m}\to{\underset{r=0}\to\sum}\; \fr{(-n-m,x+m+n+1+a_1,x-z+\fr12,x+m+a_1,z+n+1)_r} {(1,\fr{(x+1)}{2},1+\fr{x}{2},2z+m+n+1+a_3,a_1+a_2-a_3+1+2x-2z)_r}\;. \endmultline \tag5.2 $$ The proof resembled the Pfaff method proofs already examined in this paper. The only difference was that it was \ub{necessary} to prove \ub{twenty} identities simultaneously of which (5.1) was just one. Thus, in addition to (5.1), we also proved, for example, $$ H(n-1,n+1;x,z;0,0,0)=P_n, \tag5.3 $$ $$ H(n-1,n+1;x,z;1,0,1)=\fr{(z+3n+1)(2z+2n+1)P_n}{(z+n+1)(2z+4n+1)}\;, \tag5.4 $$ $$ H(n,n;x,z;0,-1,0)= \fr{(x+n-2)_3(z-x-n)(2z-x+2n)_2 P_{n}}{(x+2n-2)_3(z-x)(2z-x+n)_2}\;, \tag5.5 $$ plus sixteen similar results; here $$ P_n=\fr{(\fr12)_n(2z-x)_{2n}}{(1+x,1+x-z,z+n+\fr12)_n}\;. \tag5.6 $$ 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 \c{1; eq. (5.12)} $$ \gathered H(n,n+1;x,z;0,0,0) - H(n-1,n+1;x,z;1,0,1) \\ = \fr{-(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)}\;. \endgathered \tag5.7 $$ 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 $$ \text{SUM}_5(m)=\overset{2m+1}\to{\underset{r=0}\to\sum}\;F_5(m,r) =H(m,m+1;\fr12,\fr17;0,0,0). \tag5.8 $$ Then SUM$_5(m)$ satisfies the following linear recurrence equation (graciously supplied by Zeilberger) $$ \align &-32(28m+39)(7m+3)(14m+51)(14m+37)(14m+23)(28m+25) \tag5.9 \\ &(m+3)(m+2)(m+1)(48404160m^5+650574960m^4+3475419668m^3 \\ &+9220308013m^2\pl 12143442283m+6349305966) \text{ SUM}_5(m)\pl(14m\pl 51)(14m\pl 37) \\ &(m+3)(m+2)(2052881608458240m^{10}+42501662244679680m^9 \\ &+390743281356352512m^8+2100174572137651968m^7+7306673651176734016m^6 \endalign $$ $$ \align &+17190295272081840272m^5+27693538350246233892m^4 \\ &+30161825946242028661m^3+21251926021693940972m^2 \\ &\pl 8746561907032071897m\pl 1596513339149652990) \text{ SUM}_5(m\pl1)\mi(11\pl 4m)(9\pl 4m) \\ &(14m+51)(m+3)(2108666434775040m^{10}+48146953846924800m^9 \\ &+489608903878090752m^8\pl 2918230750107019200m^7\pl 11282101773457441192m^6 \\ &+29539117178236394078m^5+52998108990043064127m^4 \\ &+64278081153960331000m^3+50379935406843856835m^2 \\ &+23014310447535882468m+4646640934819526400) \text{ SUM}_5(m\pl 2)\pl 112(7m\pl 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)\text{ SUM}_5(m+3) \\ &=0. \endalign $$ This is proved by constructing a gigantic certificate function $$ \align &G_5(m,r)= \tag 5.10 \\ &\fr{-48(8+7m+7r)(6+7r)(3+2m+2r)(5+4m+2r)\times Z_5(m,r)\times F_5(m,r)} {(51+14m+7r)(44+14m+7r)(37+14m+7r)} \\ &\times\fr{1}{(30+14m+7r)(23+14m+7r)(16+14m+7r)(7+4m)(5+4m)} \\ &\times\fr{1}{(2m+2-r)(2m+3-r)(2m+4-r)(2m+5-r)(2m-r+6)} \endalign $$ where $$ \align &Z_5(m,r)= \tag5.11 \\ &(247499997577986751086387497363968m^{14}+\dots \\ &\qquad\qquad - 3014392481949633188462695880712\;r^6 m^9 \\ &\qquad\qquad +\dots +780611738186705500427885113128576m^{13}), \endalign $$ a polynomial of 180 terms with coefficients often in the nonillions or decillions. Zeilberger discovered that the shifts $x\to x-m$, $z\to z-m$ greatly improve the effectiveness of the WZ-method. He was then able to obtain the following results for $$ \align \text{SUM}_6(n,x,z)&=\overset{2n+1}\to{\underset{k=0}\to\sum} F_6(n,x,z,k) \tag5.12 \\ &H(n,n+1;x-n,z-n;0,0,0). \endalign $$ Then SUM$_6(n,\fr12,z)$ satisfies $$ \align &(16(18n+65)(5+2n)(2n+3)(n+3)(n+2)(n+1)(2n+3+4z) \tag5.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)\text{ SUM}_6(n,\fr12,z) \\ &=0, \endalign $$ where $N\,f(n)=f(n+1)$. The related certificate function is $$ G_6(n,k,\fr12,z)=F_6(n,k,\fr12,z) \fr{\times 24 Z_6(n,k)}{(-2n-2+k)_5}, \tag5.14 $$ with $$ \align &Z_6(n,k)= \tag5.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 \endalign $$ 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 $\geqq 50$, \c{1; \S6}) 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. \specialhead 6. The $_5F_4$ Summation (Part II): The Wilf-Petkovsek Summation. \endspecialhead 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 \c{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 \leqq n$, $$ \gathered W_n(v,\mu):= H(v-1,v;\mu-v+2, - n-v+1;0,0,0) \\ = \overset{n-1}\to{\underset{h=0}\to\sum} \fr{(1-2v,v+\mu+2,-n+1,\mu+2,\mu+n+3/2)_h} {(1,(\mu-v+3)/2,(\mu-v+4)/2,2-2n,2\mu+2n+3)_h} \endgathered \tag6.1 $$ Then for $v$ and $n$ nonnegative integers, $$ W_n(v,\mu) = \cases 0 & \text{ if } v < n \\ \dfrac{(\mu+2n+3/2)_{n-1}(n-1)!}{(-1-\mu)_{n-1}(1/2)_{n-1}} & \text{ if } v = n. \endcases \tag6.2 $$ 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 $$ \align & W_n(n,\mu) \tag6.3 \\ & = \ _5F_4\bmatrix 1-2n,n+\mu+2,-n+1,\mu+2,\mu+n+3/2\;;\;1 \\ (\mu-n+3)/2,(\mu-n+4)/2,-2n+2,2\mu+2n+3 \endbmatrix \\ & = \fr{(2+\mu+2n)_{n-1}}{(-1-\mu)_{n-1}} \overset{n-1}\to{\underset{i=0}\to\sum} \fr{(2+2\mu+4n)_i(1-n)_i}{(2-2n)_i(2+\mu+2n)_i} \\ & \qquad\qquad (\text{by [6; p. 30, eq.(1) with }a = 2\mu+2n+3, \\ & \qquad\qquad b = 2+2\mu+4n,c=1,m=n-1,w=2+\mu+2n]) \\ & = \fr{(\mu+2n+3/2)_{n-1}(n-1)!}{(-1-\mu)_{n-1}(1/2)_{n-1}} \\ &\qquad\qquad (\text{by [6; p. 16, $\S$3.3, eq.(1) with }a = 1, \\ & \qquad\qquad b = 2+2\mu+4n,c \to 1 - n) \endalign $$ Hence the bottom line of (6.2) is proved. For the top line of (6.2), we proceed using Pfaff's method: $$ \align & W_{n+1}(v,\mu) - W_n(v,\mu) \tag6.4 \\ & = \overset{n}\to{\underset{h=0}\to\sum} \fr{(1-2v,v+\mu+2,\mu+2)_h}{(1,(\mu-v+3)/2,(\mu -v +4)/2)_h} \\ & \qquad \times \left\{ \fr{(-n)_h(\mu+n+5/2)_h}{(-2n)_h(2\mu+2n+5)_h} - \fr{(-n+1)_h(\mu+n+3/2)_h}{(-2n+2)_h(2\mu+2n+3)_h}\right\} \\ & = - \overset{n}\to{\underset{h=0}\to\sum} \fr{(1-2v,v+\mu+2,\mu+2)_h(1-n)_{h-1}(\mu+n+5/2)_{h-1}} {(1,(\mu-v+3)/2,(\mu-v+4)/2)_h(-2n)_{h+2}(2\mu+2n+3)_{h+2}} \\ & \qquad\times h(h-1)(\mu+h+2)n(2n+2\mu+3)(4n+2\mu+3) \\ & = \fr{(4n+2\mu+3)(2v-1)(v-1)(v+\mu+2)(v+\mu+3)(\mu+2)(\mu+3)(\mu+4)} {(\mu-v+3)(\mu-v+4)(\mu-v+5)(\mu-v+6)(2n-1)(2n-3)(\mu+n+2)(\mu+n+3)} \\ & \qquad \qquad \times W_{n-1}(v-1,\mu+3). \endalign $$ Once (6.4) is established we may set $v = n$ and use the bottom line of (6.2) to conclude $$ W_{n+1}(n,\mu) = 0. $$ Then by induction on $i$ using (6.4) recursively, we conclude that for $0 \leqq i\leqq n$ $$ W_{n+1}(n - i,\mu) = 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 \c1. \specialhead 7. A Paean to the WZ-Method. \endspecialhead 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 $_6F_5$ appearing in (8.1) of \c2. 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 \c{8; eq. (1.8)} and subsequently D. Zeilberger proved it by using the WZ method to find a recurrence. A fuller account will appear elsewhere \c4. In addition, I have been unable to prove any ``series to series'' identities using Pfaff. Perhaps Whipple's celebrated theorem \c{12} (cf. \c{6; p. 25, eq. (4)}) will be the most instructive example. $$ \align W(m):&=\summr\fr{(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} \tag7.1 \\ &=\fr{(1+2a,1-d-e)_m}{(1+a-d,1+a-e)_m}\;\summr\; \fr{(1-b-c,a+d,a+e,-m)_r}{(1,1+a-b,1+a-c,d+e-m)_r} \endalign $$ 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 \c{1; \S2} (see also Sections 2 and 3 of this paper). This approach would yield shifts of $a\to a+\fr12$ $b\to b-\fr12$, $c\to c-\fr12$, $d\to d+\fr12$, $e\to e+\fr12$. 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 $$ \align &(m+1)(2a+m+2)(2a+m+1)(-m-2+b+c+d+e)W(m)-(2a+m+2) \tag7.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. \endalign $$ The wide applicability of the WZ method \c7, \c{13}, \c{15}, \c{16}, \c{17} and its beautiful automation by Zeilberger \c{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. \specialhead 8. Rejoinder. \endspecialhead 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 \c{15} boils down to solving a {\it homogeneous} system of linear equations with {\it 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 {\it order} of the recurrence. (5.5) obviously satisfies a {\it first order} recurrence, but the method of creative telescoping yields 3 orders too many, i.e. {\it 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. ``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. \specialhead 9. Conclusion. \endspecialhead 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 \c{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 \c9 has a lengthy study of the WZ method and includes a discussion of some of its difficulties \c{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):=\sum_{k=0}^n (-1)^k {n\choose k}{d\,k\choose n} \left(d \int > 0\right) $$ 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 surprised 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). \Refs \ref \no 1 \by G. E. Andrews \paper Pfaff's method I: the Mills-Robbins-Rumsey determinant \paperinfo Discrete Math. (to appear) \endref \ref \no 2 \by G. E. Andrews \paper Pfaff's method II: diverse applications \paperinfo J. of Computational and Appl. Math., (to appear) \endref \ref \no 3 \by G. E. Andrews and W. H. Burge \paper Determinant identities \jour Pac. J. Math., \vol 158 \yr 1993 \pages 1--14 \endref \ref \no 4 \by G. E. Andrews and D. Stanton \paper Determinants in plane partitions enumeration \paperinfo (to appear) \endref \ref \no 5 \by W. N. Bailey \paper Some identities involving generalized hypergeometric series \jour Proc. London Math. Soc., Ser. 2, \vol 29 \yr 1929 \pages 503--516 \endref \ref \no 6 \by W. N. Bailey \paper Generalized Hypergeometric Series \paperinfo Cambridge University Press, London and New York, 1935. [Reprinted: Hafner, New York, 1964] \endref \ref \no 7 \by S. B. Ekhad and D. Zeilberger \paper A 21st century proof of Dougall's hypergeometric sum identity \jour J. Math. Analysis and Appl., \vol 147 \yr 1990 \pages 610--611 \endref \ref \no 8 \by I. Gessel and D. Stanton \paper Strange evaluations of hypergeometric series \jour SIAM J. Math. Anal., \vol 13 \yr 1982 \pages 295--308 \endref \ref \no 9 \by T. H. Koornwinder \paper On Zeilberger's algorithm and its $q$-analogue \jour J. Comp. and Appl. Math., \vol 48 \yr 1993 \pages 91--111 \endref \ref \no 10 \by A. Lakin \paper A hypergeometric identity related to Dougall's theorem \jour J. London Math. Soc., \vol 27 \yr 1952 \pages 229--234 \endref \ref \no 11 \by J. F. Pfaff \paper Observationes analyticae ad L. Euler Institutiones Calculi Integralis \paperinfo Vol. IV, Supplem. II et IV, Historia de 1793, Nova Acta Acad. Sci Petropolitanae 11 (1797), 38--57 \endref \ref \no 12 \by F. J. W. Whipple \paper On well-poised series, generalized hypergeometric series having parameters in pairs, each pair with the same sum \jour Proc. London Math. Soc. (2), \vol 24 \yr 1926 \pages 247--263 \endref \ref \no 13 \by H. S. Wilf and D. Zeilberger \paper Rational functions certify combinatorial identities \jour J. Amer. Math. Soc., \vol 3 \yr 1990 \pages 147--158 \endref \ref \no 14 \by D. Zeilberger \paper A fast algorithm for proving terminating hypergeometric identities \jour Discr. Math., \vol 80 \yr 1990 \pages 207--211 \endref \ref \no 15 \by D. Zeilberger \paper The method of creative telescoping \jour J. Symbolic Computation, \vol 11 \yr 1991 \pages 195--204 \endref \ref \no 16 \by D. Zeilberger \paper Identities in search of identity \jour J. The. Comp. Sci. \vol 117 \yr 1993 \pages 23--38 \endref \ref \no 17 \by D. Zeilberger \paper Theorems for a price: tomorrow's semi-rigorous mathematical culture \jour Notices of the Amer. Math. Soc., \vol 40 \yr 1993 \pages 978--981 \endref \endRefs \vskip .3in \baselineskip 12pt \noindent THE PENNSYLVANIA STATE UNIVERSITY \newline UNIVERSITY PARK, PA 16802 \enddocument .