%%  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







.
