%begin macros
\parskip=8pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
%end macros
\rm

{\bf A FAST ALGORITHM FOR PROVING TERMINATING HYPERGEOMETRIC IDENTITIES}
\footnote{*}{
\it 
1980 Mathematics Subject Classification ( 1985 Revision). Primary:
05A10, 05A19, 11B65, 33A30, 33A99. Secondary: 05A30,33A65\rm 
}

\it
DORON ZEILBEREGER\footnote{**}{
Research supported in part by NSF grant DMS88-00663
}
\rm

{\bf Appeared in:} Discrete Math {\bf 80} (1990), 207-211.

{\bf Abstract}:
\it 
An algorithm for proving
terminating hypergeometric identities, and thus binomial coefficients
identities, is presented.
It is based upon Gosper's algorithm for indefinite 
hypergeometric summation .  A MAPLE 
program implementing this algorithm succeeded in
proving almost all known identities .  Hitherto
the proof of such identities was an exclusively human endeavor.\rm 

{\bf 1. Introduction}

I will describe an explicit algorithm for {\it proving}
binomial coefficients identities ($\equiv$ terminating
hypergeometric identities) of the form

$$
 \sum_{k}  F(n,k)  =  rhs (n)   , 
\eqno(1)
$$          

where $F(n,k)$ has the form

$$
 F(n,k)=   (  { n \atop k }  ) {{ \prod_{i=1}^{A} ( a_i n + a'_i k + a''_i )!} \over { \prod_{i=1}^{B} ( b_i n + b'_i k + b''_i )!}} z^{k}  ,
\eqno(2a)
$$     

where the $a_i , a'_i , b_i , b'_i$ have to be 
{\it constant}, specific, (positive or negative) integers, but
$z, a''_i $, and $b''_i$ can be any complex numbers or
parameters,        
and $x!$ means $\Gamma (x+1)$.

The right side of (1), $rhs(n)$, may be given explicitly, in
the form

$$
 rhs(n)= C {{ \prod_{i=1}^{\bar{A}} ( \bar{a}_i n + \bar{a'}_i )!} \over { \prod_{i=1}^{\bar{B}} ( \bar{b}_i n + \bar{b'}_i )!}} \bar{x}^{n} , 
\eqno(2b)
$$  ,     

where $\bar{a}_i $ and $\bar{b}_i$ are specific (positive or negative)
integers, and $\bar{a'}_i$, $\bar{b'}_i$ ,$C$, and $\bar{x}$, are
complex numbers or parameters.  Another possibility is that the right
side is given implicitly in terms of a minimal (ordinary) linear
recurrence operator with polynomial coefficients, $conj(n,N)$ ,that
annihilates $rhs(n)$, together with the appropriate initial
conditions.  

The theory of hypergeometric series
forms a venerable part of classical
analysis([R], [Ba]) and is nowadays making a fast comeback
([An], [As]).  
The classical identities of Vandermonde-Chu,
Pfaff-Saalschutz,
Dixon, Whipple, Watson and Dougall ([Ba]) form an important part of this
theory.  Recently Gosper discovered many "strange" 
hypergeometric identities, most of which were proved by Gessel and
Stanton[G-S].  My algorithm, implemented on MAPLE (running  on
an AT\&T  3B1 UNIX PC) was able to prove all the above mentioned
classical identities and almost all those in [G-S], including
one ((6.2)) that they were unable to prove, and that was
only proved recently by Gasper and Rahman[G-R1].

A MAPLE program implementing the algorithm is available from
the author upon request.  A q-analog will appear in a forthcoming
paper.

A sequence $a(k)$ is said to have {\it closed form} if $a(k+1)/a(k)$
is a rational function in $k$.

{\bf 2. The Slow Algorithm}

In [Z] I show that I. N. Bernstein's theory of holonomic systems
([Be],[Bj]) implies algorithms for proving a large class of special
function identities, that includes all terminating hypergeometric
identities.  For the latter case I gave an explicit algorithm that
succeeded in proving some non-trivial identities, but that ran out of
memory space,
at least on my PC, on most of the deeper identities. Although
of limited practical use, this algorithm is important for
theoretical reasons, since its validity implies the validity of my
new, more efficient, algorithm.  I will therefore first recall this
slow algorithm [Z].

For any discrete function of two variables $F(n,k)$ let
$N$ and $K$ be the shift operators in the $n$ and $k$ directions
respectively: $NF(n,k):=F(n+1,k)$ and $KF(n,k):=F(n,k+1)$.
Now form $F(n+1,k)/F(n,k)=A(n,k)/B(n,k)$ and
$F(n,k+1)/F(n,k)=A'(n,k)/B'(n,k)$.  Due to the form (2a) of $F(n,k)$
it follows that $A,B,A',B'$ are polynomials in $n$ and $k$.
Let $P(N,K,n,k):=B(n,k)N-A(n,k)$ and $Q(N,K,n,k):=B'(n,k)K-A'(n,k)$.
It follows that $P(N,K,n,k)F \equiv 0$, and $Q(N,K,n,k)F \equiv 0$.  By using
an elimination algorithm in the (non-commutative) algebra of 
linear partial
difference operators with polynomial coefficients, that is an
adaptation of the classical elimination method from commutative 
algebra ([W]),
one can find operators $C(N,K,n,k)$ and $D(N,K,n,k)$ such that
$R(N,K,n):=C(N,K,n,k)P(N,K,n,k)+D(N,K,n,k)Q(N,K,n,k)$ is non-zero and 
does not involve $k$.  It follows that $R(N,K,n)F \equiv 0$.
It is then shown that $S(N,n):=R(N,1,n)$ is
non-zero and we write $R(N,K,n)=S(N,n)-(K-1) \bar{R} (N,K,N)$.
It follows that $S(N,n)F(n,k)=(K-1) \bar{R} (N,K,n) F(n,k)$.
Now let $G(n,k):= \bar{R} (N,K,n) F(n,k)$, a certain multiple of
$F(n,k)$ by a rational function 
(and thus of {\it closed form}), and we get 

$$
 S(N,n)F(n,k)=G(n,k+1)-G(n,k) , 
\eqno(3)
$$          

and by summing (3) with respect to $k$ we get that 
$lhs (n):= \sum_{k} F(n,k) $ 
satisfies the linear ordinary recurrence equation with
polynomial coefficients $S(N,n)lhs(n) \equiv 0$.  

If the conjectured 
right side of (1), $rhs(n)$, is given explicitly, by (2b), we
compute $rhs(n+1)/rhs(n)$, a certain rational function, cross multiply,
and get a first order recurrence operator annihilating $rhs(n)$,
let us call it $conj(N,n)$.  If $rhs(n)$ is not given explicitly, then
$conj(N,n)$ is given from the outset, where it is assumed that
it has minimal order.  Now use the (Euclidean) division algorithm in
the algebra of linear recurrence operators to write
$S(N,n)=qu(N,n)conj(N,n)+rem(N,n)$, where $rem(N,n)$ has smaller order
than $conj(N,n)$.  If indeed $lhs(n) \equiv rhs(n)$, this forces
$rem(N,n)rhs(n) \equiv 0$, and by the minimality of  the order of $conj(N,n)$,
$rem(N,n)$ has to be identically zero. We should thus have for some
operator $qu(N,n)$:

$$
 qu(N,n)[conj(N,n)F(n,k)]=G(n,k+1)-G(n,k)  , 
\eqno(4)
$$          

where $G(n,k)$ has {\it closed form}.
It follows, upon summing with respect to $k$, that
$qu(N,n)[conj(N,n)lhs(n)]=0$, and we conclude that
$conj(N,n)lhs(n) \equiv 0$ provided it is true in the appropriate initial
values, that are easily checked, and thus $lhs(n) \equiv rhs(n)$, provided
it is true at the appropriate initial value(s).

{\bf 3. The Fast Algorithm}

The elimination algorithm alluded to in the above section is very
time- and space- consuming.  However, note that once we have gone
through the trouble of finding $G(n,k)$ and $qu(N,n)$ the proof that
$conj(N,n) lhs(n)=0$ is an immediate consequence, modulo purely routine
verification.  Perhaps there is {\it another} way of coming up with
the winning team of $qu(N,n)$ and $G(n,k)$?  Indeed there is.  Considering
$n$ as an auxiliary parameter, and given $qu(N,n)$,
we have to look for {\it closed form} solutions $G(n,k)$ of the
"difference equation" (4).  A general algorithm that
given a {\it closed form sequence} $a(k)$, decides whether there is
a closed form solution $S(k)$ of the difference equation
$S(k)-S(k-1)=a(k)$, and finds such an $S(k)$ in the affirmative case,
was given by Gosper[Go]. The only
trouble is that we don't know $qu(N,n)$ to begin with. So we start
being optimistic and try $qu(N,n)=1$, and this works for $80\%$ of the
cases in practice.  If this fails we put 
$qu(N,n)= b_1 (n)  N  + b_0 (n)$, plug it in (4), and let
$b_0$ and $b_1$ be additional unknowns to those in Gosper's
algorithm.  If there are such $b_0$ and $b_1$, Gosper's
algorithm will tell us what they are.  If this fails too
we try $qu(N,n)= b_2 N^2 + b_1 N + b_0$, until we get
a  closed form solution $G(n,k)$ to (4), 
together with the corresponding $qu(N,n)$.

{\bf Example}: For Dixon's classical identity ([Ba]) ,

$$
  F(n,k)= (-1)^k   (  { n+b \atop n+k }  )  (  { n+c \atop c+k }  )  (  { b+c \atop b+k }  )  ,     rhs(n) = {{(n+b+c)!}\over{ n!b!c! }}    . 
$$

It follows that $conj(N,n)=(n+1)N-(n+b+c+1)$, and it took 
$74$ seconds to find $qu(N,n)=1$, and 
$G(n,k) := (k+b)(k+c)/2(n-k+1)) F(n,k)$.   

{\bf 4. Conclusion}

The above method was dubbed \it 
creative
telescoping\rm 
 in [P], where it was used to prove that the
Apery numbers satisfy their recurrence. Only there it is described
as a sequence of {\it mirabilia}. By the general considerations of section
2 we now know that there is always a miracle ( possibly modified by
the $qu(N,n)$) and thanks to Gosper's algorithm, we can always
perform the miracle, not only in principle, like in [Z], but also
in practice.

I hope that the present algorithm will relieve humans from the
tedium of devising proofs that G. H. Hardy used to call "essentially
verifications", and will encourage them to pursue elegant and insightful
proofs.  That there still is need for such proofs can be
demonstrated by Foata's beautiful proof [C-F] of Dixon's identity.
The ideas in Foata's proof lead to the
proof of a deep multi-variate identity [Z-B].  Neither the present
algorithm, nor the more general algorithms of [Z], hold for general
multi-variate identities with an arbitrary number of variables, and
it is possible that there can never be such an algorithm.

On the other hand we should not be too chauvinistic and assume that
a computer-generated proof can give {\it no} insight.  
The team human-computer
is a mighty one, and an open-minded human can draw
inspiration from all sources, even from a machine.

{\bf 5. Postcript:}
When I wrote the last sentence I did not realize how soon my prophecy
will come true. On December 24, 1988, around 11:00 pm, I received a
phone call from Herb Wilf telling me how to bring insight into
the proofs generated by my computer. Thus was born the notion
of "rational function certification" and "WZ pairs"[WZ](see also
[C]). 

{\bf References}

[An] G. E. Andrews , \it 
q-Series:Their Development And
Applications in Analysis, Number Theory, Combinatorics, Physics, and
Computer Algebra\rm 
, CBMS series {\bf 66}, Amer. Math. Soc., Providence,
1986.

[As] R. Askey, \it 
Ramanujan and hypergeometric and basic
hypergeometric series\rm 
, preprint.

[Ba] W. N. Bailey , "Generalized Hypergeometric Series",
Cambridge Math. Tracts {\bf 32}, Cambridge University Press, London,
1935. (Reprinted: Hafner, New York, 1964 .)

[Be] I. N. Bernstein , \it 
Modules over a ring of
differential operators, study of the fundamental solutions of
equations with constant coefficients\rm 
, Functional Analysis and Its
Applications, Vol {\bf 5}, No. 2(1971), Russian original :1-16,
English translation:89-101.

[Bj] J. E. Bjork , "{\it Rings Of Differential Operators}",
North-Holland, Amsterdam, 1979.

[C] B. A. Cipra, {\it How the Grinch stole mathematics}, Science
{\bf 245}(1989), 595.

[C-F]P. Cartier and D. Foata, "Proble\*`mes combinatoires de
commutation et re\*'arrangements", Lecture Notes in Mathematics
{\bf 85}, Springer, Berlin, 1969.

[G-R1] G. Gasper and M. Rahman , \it 
An indefinite
bibasic summation formula and some quadratic, cubic, and quartic
summation and transformation formulas\rm 
, preprint.

[G-S] I. Gessel and D. Stanton ,\it 
Strange evaluations
of hypergeometric series\rm 
, SIAM J. Math. Anal. {\bf 13} (1982),
295-308.

[Go] R. W. Gosper, \it 
Decision procedures for indefinite
hypergeometric summation\rm 
, Proc. Natl. Acad. Sci. USA {\bf 75}
(1978), 40-42.

[P] A. van der Poorten, \it 
A proof that Euler missed...
Apery's proof of the irrationality of $\zeta (3)$\rm 
, Math. Intell.
{\bf 1} (1979), 195-203.

[R] E. D. Rainville , "Special Functions", Macmillan, New York,
1960. (Reprinted: Chelsea, Bronx, NY, 1971).

[W] B. L. van der Waerden , "Modern Algebra", Volumes I and II,
Frederik Ungar Publ. Co., New York.

[WZ] H. S. Wilf and D. Zeilberger, \it 
Rational functions certify
combinatorial identities\rm 
, J. Amer. Math. Soc., to appear.

[Z] D. Zeilberger, \it 
A holonomic systems approach to special
function identities\rm 
, preprint.

[Z-B] D. Zeilberger and D. Bressoud , \it 
A proof of 
Andrews' q-Dyson conjecture\rm 
, Discrete Math.{\bf 54}(1985), 201-224.

DEPARTMENT OF MATHEMATICS, DREXEL UNIVERSITY, PHILADELPHIA, PA19104,USA.
\end
