A FAST ALGORITHM FOR PROVING TERMINATING HYPERGEOMETRIC IDENTITIES *

DORON ZEILBEREGER**

Appeared in: Discrete Math 80 (1990), 207-211.

Abstract: 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.

1. Introduction

I will describe an explicit algorithm for proving binomial coefficients identities (≡ terminating hypergeometric identities) of the form

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

where F (n, k) has the form

F (n, k) = ({n \atop k})\frac{∏_{i=1}^{A}(a_{i}n + a′_{i}k + a′′_{i})!}{∏_{i=1}^{B}(b_{i}n + b′_{i}k + b′′_{i})!}z^{k},  (2a)

where the a_{i}, a′_{i}, b_{i}, b′_{i} have to be constant, specific, (positive or negative) integers, but z, a′′_{i}, and b′′_{i} can be any complex numbers or parameters, and x! means Γ(x + 1).

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

rhs(n) = C \frac{∏Ā ; i=1(ā_{i}n + ā′_{i})!}{∏B̄ ; i=1(b̄_{i}n + b̄′_{i})!}x̄^{n},  (2b)

,

where ā_{i} and b̄_{i} are specific (positive or negative) integers, and ā′_{i}, b̄′_{i} ,C, and 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

* 1980 Mathematics Subject Classification ( 1985 Revision). Primary: 05A10, 05A19, 11B65, 33A30, 33A99. Secondary: 05A30,33A65

** Research supported in part by NSF grant DMS88-00663 [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 closed form if a(k + 1)/a(k) is a rational function in k.

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 nontrivial 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 ≡ 0, and Q(N, K, n, k)F ≡ 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 ≡ 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)R̄(N, K, N). It follows that S(N, n)F (n, k) = (K − 1)R̄(N, K, n)F (n, k). Now let G(n, k) := R̄(N, K, n)F (n, k), a certain multiple of F (n, k) by a rational function (and thus of closed form), and we get

S(N, n)F (n, k) = G(n, k + 1) − G(n, k),  (3)

and by summing (3) with respect to k we get that lhs(n) := ∑_{k} F (n, k) satisfies the linear ordinary recurrence equation with polynomial coefficients S(N, n)lhs(n) ≡ 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) ≡ rhs(n), this forces rem(N, n)rhs(n) ≡ 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),  (4)

where G(n, k) has 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) ≡ 0 provided it is true in the appropriate initial values, that are easily checked, and thus lhs(n) ≡ rhs(n), provided it is true at the appropriate initial value(s).

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 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 closed form solutions G(n, k) of the ”difference equation” (4). A general algorithm that given a 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).

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) = \frac{(n + b + c)!}{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).

4. Conclusion

The above method was dubbed creative telescopingin [P], where it was used to prove that the Apery numbers satisfy their recurrence. Only there it is described as a sequence of 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 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.

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]). References

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

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

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

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

[Bj] J. E. Bjork , ”Rings Of Differential Operators”, North-Holland, Amsterdam, 1979.

[C] B. A. Cipra, How the Grinch stole mathematics, Science 245(1989), 595. [C-F]P. Cartier and D. Foata, ”Proble‘mes combinatoires de commutation et re’arrangements”, Lecture Notes in Mathematics 85, Springer, Berlin, 1969. [G-R1] G. Gasper and M. Rahman , An indefinite bibasic summation formula and some quadratic, cubic, and quartic summation and transformation formulas, preprint. [G-S] I. Gessel and D. Stanton ,Strange evaluations of hypergeometric series, SIAM J. Math. Anal. 13 (1982), 295-308.

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

[P] A. van der Poorten, A proof that Euler missed... Apery’s proof of the irrationality of ζ(3), Math. Intell. 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, Rational functions certify combinatorial identities, J. Amer. Math. Soc., to appear.

[Z] D. Zeilberger, A holonomic systems approach to special function identities, preprint. [Z-B] D. Zeilberger and D. Bressoud , A proof of Andrews’ q-Dyson conjecture, Discrete Math.54(1985), 201-224. DEPARTMENT OF MATHEMATICS, DREXEL UNIVERSITY, PHILADELPHIA, PA19104,USA.