An algorithmic proof theory for hypergeometric (ordinary and “\(q\)”) multisum/integral identities. (English) Zbl 0739.05007
It is shown that every ‘proper-hypergeometric’ multisum/integral identity, or \(q\)-identity, with fixed number of summation and/or integration signs, possesses a short, computer-constructible proof. We give a fast algorithm for finding such proofs. Most of the identities that involve the classical special functions of mathematical physics are readily reducible to the kind of identities treated here. We give many examples of the method, including computer-generated proofs of identities of Mehta-Dyson, Selberg, Hille-Hardy, \(q\)-Saalschütz, and others. The prospect of using the method for proving multivariate identities that involve an arbitrary number of summations/integrations is discussed.
Reviewer: H.S.Wilf
MSC:
| 05A19 | Combinatorial identities, bijective combinatorics |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 11B65 | Binomial coefficients; factorials; \(q\)-identities |
| 05A30 | \(q\)-calculus and related topics |
| 33C99 | Hypergeometric functions |
| 39A10 | Additive difference equations |
Software:
DEtoolsDigital Library of Mathematical Functions:
§16.4(iii) Identities ‣ §16.4 Argument Unity ‣ Generalized Hypergeometric Functions ‣ Chapter 16 Generalized Hypergeometric Functions and Meijer 𝐺-FunctionReferences:
| [1] | [AZ] Almkvist, G., Zeilberger, D.: The method of differentiating under the integral sign, (The Maple program that implements the algorithm appeared in ACM SIGSAM Bulletin25, No. 3 (July 1991), 14–17), J. Symbolic Computation10, 571–591 (1990) · Zbl 0717.33004 · doi:10.1016/S0747-7171(08)80159-9 |
| [2] | [Ande] Anderson, G.: Letter to R. Askey |
| [3] | [Ande1] Anderson, G.: The evaluation of Selberg sums, C.R. Acad. Sci. (Ser. I: Math.)311, 469–472 (1990) · Zbl 0724.11063 |
| [4] | [An] Andrews, G.: The Theory of Partitions, Encyclopedia of Mathematics and Its Applications (G.C. Rota, Editor), vol. 2, Addison Wesley, Reading, 1976 |
| [5] | [An1] Andrews, G.: q-Series: Their Development and Applications in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra, CBMS series, vol. 66, Am. Math. Soc., Providence, 1986 |
| [6] | [Ao] Aomoto, K.: Jacobi polynomials associated with Selberg’s integrals. SIAM J. Math. Anal.18, 545–549 (1987) · Zbl 0639.33001 · doi:10.1137/0518042 |
| [7] | [As] Askey, R.A.: Orthogonal Polynomials and Special Functions, Regional Conference Series in Applied Mathematics, vol. 21, SIAM, 1975 · Zbl 0298.33008 |
| [8] | [As1] Askey, R.A.: Lost and found mathematics, MAA-AAAS invited address, Annual meeting, Columbus, OH, Aug. 1990 |
| [9] | [As2] Askey, R.A.: Ramanujan and important formulas, Srinivasa Ramanujan, a tribute (N.R. Nagarajan and T. Soundararajan, eds.), Macmillan, India, Madras, 1988 |
| [10] | [As3] Askey, R.A.: An elementary evaluation of a beta type integral, Indian J. Pure Appl. Math.14, 892–895 (1983) · Zbl 0523.33001 |
| [11] | [AsWi] Askey, R., Wilson, J.A.: Some basic hypergeometric polynomials that generalize the Jacobi polynomials, Memoirs Amer. Math. Soc.319 (1985) · Zbl 0572.33012 |
| [12] | [Ba] Bailey, W.N.: Generalized Hypergeometric Series, Cambridge Math. Tract No. 32, (Reprinted: Hafner, New York, 1964), Cambr. Univ. Press, London and New York, 1935 · Zbl 0011.02303 |
| [13] | [Ba1] Bailey, W.N.: The generating function for Jacobi polynomials, J. London Math. Soc.13, 243–246 (1938) |
| [14] | [BFH] Benson, D., Feit, W., Howe, R.: Finite linear groups, the Commodore 64, Euler, and Sylvester, Amer. Math. Monthly93, 717–720 (1986) · Zbl 0611.10013 · doi:10.2307/2322289 |
| [15] | [Be] Bernstein, I.(J.)N: Modules over rings of differential operators, a study of the fundamental solutions of equations with constant coefficients, Funct. Anal. and Appl.5, 1–16 (1971) · Zbl 0246.17008 · doi:10.1007/BF01075841 |
| [16] | [Bj] Björk, J.E.: Rings of Differential Operators, North-Holland, Amsterdam, 1979. · Zbl 0313.16027 |
| [17] | [Bo] Borel, A. et al.: Algebraic D-Modules, Academic Press, Boston, 1987. · Zbl 0642.32001 |
| [18] | [Ca] Cayley, A.: Collected Papers, vol. 12, pp. 217–219 |
| [19] | [Co] Comtet, L.: Advanced Combinatorics, Reidel, Dordrecht 1974 |
| [20] | [Cal] Carlitz, L.: Summations of products of binomial coefficients, Amer. Math. Monthly75, 906–908 (1968) · doi:10.2307/2314366 |
| [21] | [Ca2] Carlitz, L.: A binomial identity arising from a sorting problem, SIAM Review6, 20–30 (1964) · Zbl 0128.01601 · doi:10.1137/1006003 |
| [22] | [deB] de Branges, L.: A proof of the Bieberbach conjecture, Acta Math.154, 137–152 (1985) · Zbl 0573.30014 · doi:10.1007/BF02392821 |
| [23] | [Eg] Egorychev, G.P.: Integral representation and the Computation of Combinatorial Sums, vol. 59, AMS, Providence, 1984 · Zbl 0524.05001 |
| [24] | [Eh] Ehlers, F.: The Weyl algebra, in [Bo]– |
| [25] | [Ek1] Ekhad, S.B.: Short proofs of two hypergeometric summation formulas of Karlsson, Proc. Amer. Math. Soc.107, 1143–1144 (1989) · Zbl 0688.33001 · doi:10.1090/S0002-9939-1989-1019759-3 |
| [26] | [Ek2] Ekhad, S.B.: A very short proof of Dixon’s theorem, J. Comb. Theory, Ser. A54, 141–142 (1990) · Zbl 0707.05007 · doi:10.1016/0097-3165(90)90014-N |
| [27] | [Ek3] Ekhad, S.B.: A one-line proof of the Habsieger-ZeilbergerG 2 constant term identity, J. Comput. Appl. Math.34, 133–134 (1991) · Zbl 0737.33010 · doi:10.1016/0377-0427(91)90154-C |
| [28] | [Ek4] Ekhad, S.B.: Short proof of a strange combinatorial identity conjectured by Gosper, Discrete Math.90, 319–320 (1991) · Zbl 0741.05004 · doi:10.1016/0012-365X(91)90152-R |
| [29] | [Ek5] Ekhad, S.B.: A Short, elementary, and easy, WZ proof of the Askey-Gasper inequality that was used by de Branges in his proof of the Bieberbach conjecture, J. Theor. Comp. Sci (to appear) · Zbl 0780.33004 |
| [30] | [ET] Ekhad, S.B. Tre, S.: A purely, verification proof of the first Rogers-Ramanujan identity. J. Comb. Theory Ser. A54, 309–311 (1990) · Zbl 0702.05007 · doi:10.1016/0097-3165(90)90038-X |
| [31] | [Er] Erdélyi, A. et al.: The Higher Transcendental Functions, The Bateman Manuscript Project, 3 vols. McGraw-Hill, New York, 1953 |
| [32] | [Ev] Evans, R.: Identities for products of Gauss sums over finite fields, Enseign. Math.27, 197–209 (1981) · Zbl 0491.12020 |
| [33] | [EZ] Ekhad, S.B., Zeilberger, D.: A 21 st century proof of Dougall’s hypergeometric sum identity, J. Math. Anal. Appl.147, 610–611 (1990) · Zbl 0714.33002 · doi:10.1016/0022-247X(90)90375-P |
| [34] | [Fa] Fasenmyer, M.C.: Some generalized hypergeometric polynomials, Bull. Amer. Math. Soc.53, 806–812 (1947) · Zbl 0032.15402 · doi:10.1090/S0002-9904-1947-08893-5 |
| [35] | [Fo] Foata, D.: Combinatoire des identites sur les polynomes orthogonaux, Proc. ICM 83, Varsovie, 1541–1553 (1983) |
| [36] | [Fo1] Foata, D.: A combinatorial proof of the Mehler formula, J. Comb. Theory, ser. A24, 250–259 (1978) · Zbl 0401.33008 · doi:10.1016/0097-3165(78)90066-3 |
| [37] | [FG] Foata, D., Garsia, A.: A combinatorial approach to the Mehler formulas for Hermite polynomials, Relations between combinatorics and other branches of mathematics, Columbus, 1978, Amer. Math. Soc., Providence, 1979, pp. 163–179 |
| [38] | [FS] Foata, D, Strehl, V.: Une extension multilinéaire de la formule d’Erdélyi pour les produits de fonctions hypergéometriques confluentes, C.R. Acad. Sc. Paris293, 517–520 (1981) · Zbl 0478.33008 |
| [39] | [GaGo] Garvan, F., Gonnet, G., Macdonald’s constant term conjectures for the exceptional root systems, Bulletin (new series) of the Amer. Math. Soc.24, 343–347 (1991) · Zbl 0737.33011 · doi:10.1090/S0273-0979-1991-16029-5 |
| [40] | [GaRa] Gasper, G., Rahman, M.: Basic Hypergeometric Series, Encyclopedia of Mathematics and Its Applications, Cambridge Univ. Press, Cambridge, 1990 |
| [41] | [GS] Gessel, I., Stanton, D.: Short proofs of Saalschütz’ and Dixon’s theorems, J. Combin. Theory A38, 87–90 (1985) · Zbl 0559.05008 · doi:10.1016/0097-3165(85)90026-3 |
| [42] | [Goo] Good, I.J.: Short proof of a conjecture by Dyson, J. Math. Phys.11, 1884 (1970) · doi:10.1063/1.1665339 |
| [43] | [Gos] Gosper, R.W., Jr.: Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci USA75, 40–42 (1978) · Zbl 0384.40001 · doi:10.1073/pnas.75.1.40 |
| [44] | [GKP] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics, Addison-Wesley, Reading, MA, 1989 · Zbl 0668.00003 |
| [45] | [Gu] Gustafson, R.A.: A generalization of Selberg’s beta integral, Bull. (new series) Amer. Math. Soc.22, 97–105 (1990) · Zbl 0693.33001 · doi:10.1090/S0273-0979-1990-15852-5 |
| [46] | [GuMi] Gustafson, R.A., Milne, S.C.: Schur functions, Good’s identity, and hypergeometric series well poised inSU(n), Adv. in Math.57, 209–225 (1985) · Zbl 0586.33013 · doi:10.1016/0001-8708(85)90063-5 |
| [47] | [Ho] Holman, W.J. III: Summation theorems for hypergeometric series inU(n), SIAM J. Math. Anal.11, 523–532 (1980) · Zbl 0454.33010 · doi:10.1137/0511050 |
| [48] | [ISV] Ismail, M., Stanton, D., Viennot, G.: The combinatorics ofq-Hermite polynomials and the Askey-Wilson integral, Europ. J. Combin.8, 379–392 (1987) · Zbl 0642.33006 |
| [49] | [K] Koornwinder, T.H.: Handling hypergeometric series in Maple, Orthogonal Polynomials and their Applications (C. Brezinski, L. Gori and A. Ronveaux, eds.), IMACS Annals on computing and applied mathematics, Baltzer, 1991, pp. 73–80 · Zbl 0833.33001 |
| [50] | [L] Leonard Lipshitz: The diagonal of a D-finite power series is D-finite, J. Algebra13, 373–378 (1988) · Zbl 0657.13024 · doi:10.1016/0021-8693(88)90166-4 |
| [51] | [Ma] Macdonald, I.G.: Some conjectures for root systems, SIAM J. Math. Anal.13, 988–1007 (1982) · Zbl 0498.17006 · doi:10.1137/0513070 |
| [52] | [Mi] Milne, S.C.: Aq-analog of the Gauss summation theorem for hypergeometric series inU(n), Adv. Math.72, 59–131 (1988) · Zbl 0658.33005 · doi:10.1016/0001-8708(88)90019-9 |
| [53] | [O] Opdam, E.: Some applications of hypergeometric shift operators, Invent. Math.98, 1–18 (1989) · Zbl 0696.33006 · doi:10.1007/BF01388841 |
| [54] | [R] Rainville, E.D.: Special Functions (Reprinted: Chelsea, Bronx, NY, 1971)., Macmillan, New York, 1960 · Zbl 0092.06503 |
| [55] | [Ri] Richards, D.St.P.: Analogs and extensions of Selberg’s integral,q-Series and Partitions, IMA volumes in Mathematics and its Applications (D. Stanton, ed.), vol. 18, Springer, New York, 1989 · Zbl 0697.33007 |
| [56] | [Se] Selberg, A.: Bemerkninger om et multipelt integral, Norsk Math. Tidsskr.26, 71–78 (1944) |
| [57] | [Sta] Stanton, D.: A short proof of a generating function for Jacobi polynomials, Proc. Amer. Math. Soc.80, 398–400 (1980) · Zbl 0446.33016 · doi:10.1090/S0002-9939-1980-0580992-8 |
| [58] | [St] Strehl, V.: Zykel-Enumeration bei Local-Strukturien Funktionen, Universität Erlangen-Nürnberg, Germany, 1990 |
| [59] | [SzVa] Szondy and Varga: A conjectured double sum, preprint |
| [60] | [V] Verbaeten, P.: The automatic construction of pure recurrence relations, Proc. EUROSAM ’74, ACM-SIGSAM Bulletin8, 96–98 (1974) · doi:10.1145/1086837.1086854 |
| [61] | [WZ1] Wilf, H.S., Zeilberger, D.: Towards computerized proofs of identities, Bull. Amer. Math. Soc.23, 77–83 (1990) · Zbl 0718.05010 · doi:10.1090/S0273-0979-1990-15904-X |
| [62] | [WZ2] Wilf, H.S., Zeilberger, D.: Rational functions certify combinatorial identities, J. Amer. Math. Soc.3, 147–158 (1990) · Zbl 0695.05004 · doi:10.1090/S0894-0347-1990-1007910-7 |
| [63] | [Z0] Zeilberger, D.: Sister Celine’s technique and its generalizations, J. Math. Anal. Appl.85, 114–145 (1982) · Zbl 0485.05003 · doi:10.1016/0022-247X(82)90029-4 |
| [64] | [Z1] Zeilberger, D.: A holonomic systems approach to special functions identities, J. of Computational and Applied Math.32, 321–368 (1990) · Zbl 0738.33001 · doi:10.1016/0377-0427(90)90042-X |
| [65] | [Z2] Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities, Discrete Math.80, 207–211 (1990) · Zbl 0701.05001 · doi:10.1016/0012-365X(90)90120-7 |
| [66] | [Z3] Zeilberger, D.: The method of creative telescoping, J. Symbolic Computation25, 4–13 (1991) |
| [67] | [Z4] Zeilberger, D.: Closed form (pun intended!), Special volume in memory of Emil Grosswald (M. Knopp, ed.), Contemporary Mathematics (to appear) |
| [68] | [Z5] Zeilberger, D.: The method of creative telescoping forq-series, in preparation |
| [69] | [Z6] Zeilberger, D.: Aq-Foata proof of theq-Saalschütz identity, European J. Combinatorics8, 461–463 (1987) · Zbl 0643.05003 |
| [70] | [Z7] Zeilberger, D.: Towards a WZ evaluation of the Mehta integral (submitted) |
| [71] | [ZB] Zeilberger, D., Bressoud, D.: A proof of Andrews’q-Dyson conjecture, Discrete Math.54, 201–224 (1985) · Zbl 0565.33001 · doi:10.1016/0012-365X(85)90081-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
