Creative Telescoping for Parametrised Integration and Summation

Frédéric Chyzak[1]

  • [1] INRIA (France)

Les cours du CIRM (2011)

  • Volume: 2, Issue: 1, page 1-37
  • ISSN: 2108-7164

How to cite


Chyzak, Frédéric. "Creative Telescoping for Parametrised Integration and Summation." Les cours du CIRM 2.1 (2011): 1-37. <>.

affiliation = {INRIA (France)},
author = {Chyzak, Frédéric},
journal = {Les cours du CIRM},
language = {eng},
number = {1},
pages = {1-37},
publisher = {CIRM},
title = {Creative Telescoping for Parametrised Integration and Summation},
url = {},
volume = {2},
year = {2011},

AU - Chyzak, Frédéric
TI - Creative Telescoping for Parametrised Integration and Summation
JO - Les cours du CIRM
PY - 2011
VL - 2
IS - 1
SP - 1
EP - 37
LA - eng
UR -
ER -


  1. S. A. Abramov, Applicability of Zeilberger’s algorithm to hypergeometric terms, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (2002), 1-7 (electronic), ACM, New York Zbl1072.68642MR2035226
  2. S. A. Abramov, When does Zeilberger’s algorithm succeed?, Adv. in Appl. Math. 30 (2003), 424-441 Zbl1030.33011MR1973952
  3. S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients, U.S.S.R. Comput. Math. and Math. Phys. 29 (1991), 7-12 Zbl0719.65063MR1025995
  4. S. A. Abramov, Rational solutions of linear difference and q -difference equations with polynomial coefficients, Program. Comput. Software 21 (1995), 273-278 Zbl0910.65107MR1615571
  5. S. A. Abramov, H. Q. Le, Applicability of Zeilberger’s algorithm to rational functions, Formal power series and algebraic combinatorics (Moscow, 2000) (2000), 91-102, Springer, Berlin Zbl0963.65026MR1798204
  6. S. A. Abramov, H. Q. Le, A criterion for the applicability of Zeilberger’s algorithm to rational functions, Discrete Math. 259 (2002), 1-17 Zbl1023.33017MR1948770
  7. S. A. Abramov, M. Petkovšek, On the structure of multivariate hypergeometric terms, Adv. in Appl. Math. 29 (2002), 386-411 Zbl1057.33017MR1942630
  8. Moa Apagodu, The sharpening of Wilf-Zeilberger theory, (2006), ProQuest LLC, Ann Arbor, MI Zbl1108.05010MR2709554
  9. Richard Askey, The world of q , CWI Quarterly 5 (1992), 251-269 Zbl0765.33015MR1213742
  10. Moa Apagodu, Doron Zeilberger, Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. in Appl. Math. 37 (2006), 139-152 Zbl1108.05010MR2251432
  11. Gert Almkvist, Doron Zeilberger, The method of differentiating under the integral sign, J. Symbolic Comput. 10 (1990), 571-591 Zbl0717.33004MR1087980
  12. Alin Bostan, Frédéric Chyzak, Pierre Lairez, 3 pages. In preparation (2011) 
  13. Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Lucien Pech, Explicit formula for the generating series of diagonal 3D rook paths, Sém. Loth. Comb. (2011) Zbl1295.05028
  14. I. N. Bernšteĭn, Modules over a ring of differential operators. An investigation of the fundamental solutions of equations with constant coefficients, Funkcional. Anal. i Priložen. 5 (1971), 1-16 Zbl0233.47031MR290097
  15. I. N. Bernšteĭn, Analytic continuation of generalized functions with respect to a parameter, Funkcional. Anal. i Priložen. 6 (1972), 26-40 Zbl0282.46038MR320735
  16. Harald Böing, Wolfram Koepf, Algorithms for q -hypergeometric summation in computer algebra, J. Symbolic Comput. 28 (1999), 777-799 Zbl0946.65008MR1750546
  17. R. J. Blodgelt, Problem E3376, Amer. Math. Monthly (1990) 
  18. Manuel Bronstein, Marko Petkovšek, Ore rings, linear operators and factorization, Programmirovanie (1994), 27-44 Zbl0828.16035MR1291354
  19. Manuel Bronstein, Marko Petkovšek, An introduction to pseudo-linear algebra, Theoret. Comput. Sci. 157 (1996), 3-33 Zbl0868.34004MR1383396
  20. Shaoshi Chen, Frédéric Chyzak, Ruyong Feng, Ziming Li, On the Existence of Telescopers for Hyperexponential-Hypergeometric Sequences, (2011) Zbl1303.33024
  21. Shaoshi Chen, Some applications of differential-difference algebra to creative telescoping, (2011) 
  22. William Y. C. Chen, Qing-Hu Hou, Yan-Ping Mu, Applicability of the q -analogue of Zeilberger’s algorithm, J. Symbolic Comput. 39 (2005), 155-170 Zbl1126.33008MR2169798
  23. Frédéric Chyzak, An extension of Zeilberger’s fast algorithm to general holonomic functions, Discrete Math. 217 (2000), 115-134 Zbl0968.33011MR1766263
  24. Frédéric Chyzak, Fonctions holonomes en calcul formel, (1998) 
  25. Frédéric Chyzak, Gröbner bases, symbolic summation and symbolic integration, Gröbner bases and applications (Linz, 1998) 251 (1998), 32-60, Cambridge Univ. Press, Cambridge Zbl0898.68040MR1699813
  26. Frédéric Chyzak, Manuel Kauers, Bruno Salvy, A non-holonomic systems approach to special function identities, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (2009), 111-118, ACM, New York Zbl1237.33001MR2742698
  27. F. Chyzak, A. Quadrat, D. Robertz, Effective algorithms for parametrizing linear control systems over Ore algebras, Appl. Algebra Engrg. Comm. Comput. 16 (2005), 319-376 Zbl1109.93018MR2233761
  28. William Y. C. Chen, Lisa H. Sun, Extended Zeilberger’s algorithm for identities on Bernoulli and Euler polynomials, J. Number Theory 129 (2009), 2111-2132 Zbl1183.11011MR2528056
  29. Frédéric Chyzak, Bruno Salvy, Non-commutative elimination in Ore algebras proves multivariate identities, J. Symbolic Comput. 26 (1998), 187-227 Zbl0944.05006MR1635242
  30. Gustav Doetsch, Integraleigenschaften der Hermiteschen Polynome, Math. Z. 32 (1930), 587-599 Zbl56.0989.03MR1545186
  31. Shalosh B. Ekhad, Doron Zeilberger, A high-school algebra, “formal calculus”, proof of the Bieberbach conjecture [after L. Weinstein], Jerusalem combinatorics ’93 178 (1994), 113-115, Amer. Math. Soc., Providence, RI Zbl0894.30013MR1310578
  32. Shalosh B. Ekhad, Doron Zeilberger, A WZ proof of Ramanujan’s formula for  π , Geometry, Analysis, and Mechanics (1994), 107-108, RassiasJ. M.J. M., Singapore Zbl0849.33003MR1323194
  33. Shalosh B. Ekhad, Doron Zeilberger, The number of solutions of  X 2 = 0 in triangular matrices over  G F ( q ) , Electron. J. Combin. 3 (1996) Zbl0851.15010MR1364064
  34. Mary Celine Fasenmyer, Some generalized hypergeometric polynomials, (1945) Zbl0032.15402
  35. Mary Celine Fasenmyer, A note on pure recurrence relations, Amer. Math. Monthly 56 (1949), 14-17 Zbl0032.41002MR30044
  36. André Galligo, Some algorithmic questions on ideals of differential operators, EUROCAL ’85, Vol. 2 (Linz, 1985) 204 (1985), 413-421, Springer, Berlin Zbl0634.16001MR826576
  37. Ira M. Gessel, Applications of the classical umbral calculus, Algebra Universalis 49 (2003), 397-434 Zbl1092.05005MR2022347
  38. I. M. Gel’fand, M. I. Graev, V. S. Retakh, General hypergeometric systems of equations and series of hypergeometric type, Russian Math. Surveys 47 (1992), 1-88 Zbl0798.33010MR1208882
  39. Qiang-Hui Guo, Qing-Hu Hou, Lisa H. Sun, Proving hypergeometric identities by numerical verifications, J. Symbolic Comput. 43 (2008), 895-907 Zbl1173.33304MR2472539
  40. M. L. Glasser, E. Montaldi, Some integrals involving Bessel functions, J. Math. Anal. Appl. 183 (1994), 577-590 Zbl0809.33001MR1274858
  41. R. William Gosper, Decision procedure for indefinite hypergeometric summation, Proc. Nat. Acad. Sci. U.S.A. 75 (1978), 40-42 Zbl0384.40001MR485674
  42. Joachim Hornegger, Hypergeometrische Summation und polynomiale Rekursion, (1992) 
  43. Qing-Hu Hou, k -free recurrences of double hypergeometric terms, Adv. in Appl. Math. 32 (2004), 468-484 Zbl1057.33018MR2041960
  44. N. Jacobson, Pseudo-linear transformations, Ann. of Math. (2) 38 (1937), 484-507 Zbl0017.15001MR1503347
  45. Masaki Kashiwara, On the holonomic systems of linear differential equations. II, Invent. Math. 49 (1978), 121-135 Zbl0401.32005MR511186
  46. Manuel Kauers, Summation algorithms for Stirling number identities, J. Symbolic Comput. 42 (2007), 948-970 Zbl1142.11008MR2361673
  47. Tom H. Koornwinder, On Zeilberger’s algorithm and its q -analogue, Proceedings of the Seventh Spanish Symposium on Orthogonal Polynomials and Applications (VII SPOA) (Granada, 1991) 48 (1993), 91-111 Zbl0797.65011MR1246853
  48. Christoph Koutschan, A fast approach to creative telescoping, Math. Comput. Sci. 4 (2010), 259-266 Zbl1218.68205MR2775992
  49. A. Kandri-Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9 (1990), 1-26 Zbl0715.16010MR1044911
  50. Kha Le, On the q -analogue of Zeilberger’s algorithm for rational functions, Programmirovanie (2001), 49-58 Zbl0985.33014MR1867720
  51. L. Lipshitz, The diagonal of a D -finite power series is D -finite, J. Algebra 113 (1988), 373-378 Zbl0657.13024MR929767
  52. L. Lipshitz, D -finite power series, J. Algebra 122 (1989), 353-373 Zbl0695.12018MR999079
  53. John E. Majewicz, WZ-style certification and Sister Celine’s technique for Abel-type sums, J. Differ. Equations Appl. 2 (1996), 55-65 Zbl0863.05009MR1375596
  54. John E. Majewicz, WZ certification of Abel-type identities and Askey’s positivity conjecture, (1997), ProQuest LLC, Ann Arbor, MI MR2696103
  55. Mohamud Mohammed, Doron Zeilberger, Sharp upper bounds for the orders of the recurrences output by the Zeilberger and q -Zeilberger algorithms, J. Symbolic Comput. 39 (2005), 201-207 Zbl1121.33023MR2169800
  56. Hiromasa Nakayama, Kenta Nishiyama, An algorithm of computing inhomogeneous differential equations for definite integrals, Proceedings of the Third international congress conference on Mathematical software (2010), 221-232, Springer-Verlag, Berlin, Heidelberg Zbl1294.68162
  57. Toshinori Oaku, Algorithms for integrals of holonomic functions over domains defined by polynomial inequalities, (2011) Zbl1284.68683
  58. Toshinori Oaku, An algorithm of computing b -functions, Duke Math. J. 87 (1997), 115-132 Zbl0893.32009MR1440065
  59. Oystein Ore, Sur les fonctions hypergéométriques de plusieurs variables, Comptes Rendus des Séances de l’Académie des Sciences 189 (1929), 1238-1241 Zbl55.0220.03
  60. Oystein Ore, Sur la forme des fonctions hypergéométriques de plusieurs variables, Journal de Mathématiques Pures et Appliquées 9 (1930), 311-326 Zbl56.0313.13
  61. Oystein Ore, Linear equations in non-commutative fields, Ann. of Math. (2) 32 (1931), 463-477 Zbl0001.26601MR1503010
  62. Oystein Ore, Theory of non-commutative polynomials, Ann. of Math. (2) 34 (1933), 480-508 Zbl0007.15101MR1503119
  63. Toshinori Oaku, Nobuki Takayama, Algorithms for D -modules—restriction, tensor product, localization, and local cohomology groups, J. Pure Appl. Algebra 156 (2001), 267-308 Zbl0983.13008MR1808827
  64. Toshinori Oaku, Nobuki Takayama, Integrals of modules and their applications, Sūrikaisekikenkyūsho Kōkyūroku (1998), 163-169 Zbl0944.14501MR1672325
  65. Toshinori Oaku, Nobuki Takayama, Uli Walther, A localization algorithm for D -modules, J. Symbolic Comput. 29 (2000), 721-728 Zbl1012.13010MR1769663
  66. Peter Paule, Greatest factorial factorization and symbolic summation, J. Symbolic Comput. 20 (1995), 235-268 Zbl0854.68047MR1378099
  67. Peter Paule, Axel Riese, A Mathematica q -analogue of Zeilberger’s algorithm based on an algebraically motivated approach to q -hypergeometric telescoping, Special functions, -series and related topics (Toronto, ON, 1995) 14 (1997), 179-210, Amer. Math. Soc., Providence, RI Zbl0869.33010
  68. Helmut Prodinger, Descendants in heap ordered trees, or, A triumph of computer algebra, Electron. J. Combin. 3 (1996) Zbl0885.05004MR1410884
  69. Peter Paule, Markus Schorn, A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symbolic Comput. 20 (1995), 673-698 Zbl0851.68052MR1395420
  70. R. Piessens, P. Verbaeten, Numerical solution of the Abel integral equation, Nordisk Tidskr. Informationsbehandling (BIT) 13 (1973), 451-457 Zbl0266.65081MR329293
  71. Earl D. Rainville, Special functions, (1960), The Macmillan Co., New York Zbl0092.06503MR107725
  72. Axel Riese, Fine-tuning Zeilberger’s algorithm. The methods of automatic filtering and creative substituting, Symbolic computation, number theory, special functions, physics and combinatorics (Gainesville, FL, 1999) 4 (2001), 243-254, Kluwer Acad. Publ., Dordrecht Zbl1037.33018MR1880090
  73. Axel Riese, qMultiSum—a package for proving q -hypergeometric multiple summation identities, J. Symbolic Comput. 35 (2003), 349-376 Zbl1020.33007MR1962799
  74. Axel Riese, A generalization of Gosper’s algorithm to bibasic hypergeometric summation, Electron. J. Combin. 3 (1996) Zbl0885.33012MR1394550
  75. Mikio Sato, Theory of prehomogeneous vector spaces (algebraic part)—the English translation of Sato’s lecture from Shintani’s note, Nagoya Math. J. 120 (1990), 1-34 Zbl0715.22014MR1086566
  76. Mutsumi Saito, Bernd Sturmfels, Nobuki Takayama, Gröbner deformations of hypergeometric differential equations, 6 (2000), Springer-Verlag, Berlin Zbl0946.13021MR1734566
  77. Bernd Sturmfels, Nobuki Takayama, Gröbner bases and hypergeometric functions, Gröbner bases and applications (Linz, 1998) 251 (1998), 246-258, Cambridge Univ. Press, Cambridge Zbl0918.33004MR1708882
  78. R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980), 175-188 Zbl0445.05012MR587530
  79. Richard P. Stanley, Enumerative combinatorics. Vol. 2, 62 (1999), Cambridge University Press, Cambridge Zbl0928.05001MR1676282
  80. Volker Strehl, Binomial identities—combinatorial and algorithmic aspects, Discrete Math. 136 (1994), 309-346 Zbl0823.33003MR1313292
  81. James Joseph Sylvester, A method of determining by mere inspection the derivatives from two equations of any degree, Philosophical Magazine XVI (1840), 132-135 
  82. Nobuki Takayama, Gröbner basis and the problem of contiguous relations, Japan J. Appl. Math. 6 (1989), 147-160 Zbl0691.68032MR981518
  83. Nobuki Takayama, An algorithm of constructing the integral of a module — an infinite dimensional analog of Gröbner basis, Symbolic and Algebraic Computation (1990), 206-211, ACM and Addison-Wesley 
  84. Nobuki Takayama, Gröbner basis, integration and transcendental functions, Symbolic and Algebraic Computation (1990), 152-156, ACM and Addison-Wesley 
  85. Nobuki Takayama, An approach to the zero recognition problem by Buchberger algorithm, J. Symbolic Comput. 14 (1992), 265-282 Zbl0763.65007MR1187235
  86. Akalu Tefera, Improved algorithms and implementations in the multi-WZ theory, (2000), ProQuest LLC, Ann Arbor, MI Zbl0939.65035MR2701445
  87. Akalu Tefera, MultInt, a MAPLE package for multiple integration by the WZ method, J. Symbolic Comput. 34 (2002), 329-353 Zbl1015.33013MR1937465
  88. Harrison Tsai, Weyl closure of a linear differential operator, J. Symbolic Comput. 29 (2000), 747-775 Zbl1008.16026MR1769665
  89. Harrison Tsai, Algorithms for associated primes, Weyl closure, and local cohomology of D -modules, Local cohomology and its applications (Guanajuato, 1999) 226 (2002), 169-194, Dekker, New York Zbl0992.68245MR1888199
  90. Alfred van der Poorten, A proof that Euler missed ... Apéry’s proof of the irrationality of ζ ( 3 ) , Math. Intelligencer 1 (1979), 195-203 Zbl0409.10028MR547748
  91. Petrus Verbaeten, The automatic construction of pure recurrence relations, Proceedings of Eurosam 74, Sigsam Bulletin (1974), 96-98 
  92. Pierre Verbaeten, Rekursiebetrekkingen voor lineaire hypergeometrische funkties, (1976), Leuven, Belgium 
  93. Kurt Wegschaider, Computer generated proofs of binomial multi-sum identities, (1997) 
  94. Herbert S. Wilf, Doron Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “ q ”) multisum/integral identities, Invent. Math. 108 (1992), 575-633 Zbl0739.05007MR1163239
  95. Herbert S. Wilf, Doron Zeilberger, Rational function certification of multisum/integral/“ q ” identities, Bull. Amer. Math. Soc. (N.S.) 27 (1992), 148-153 Zbl0759.05007MR1145580
  96. Lily Yen, Contributions to the proof theory of hypergeometric identities, (1993) MR2689630
  97. Lily Yen, A two-line algorithm for proving terminating hypergeometric identities, J. Math. Anal. Appl. 198 (1996), 856-878 Zbl0857.33002MR1377830
  98. Lily Yen, A two-line algorithm for proving q -hypergeometric identities, J. Math. Anal. Appl. 213 (1997), 1-14 Zbl0903.33008MR1469359
  99. Doron Zeilberger, The algebra of linear partial difference operators and its applications, SIAM J. Math. Anal. 11 (1980), 919-932 Zbl0458.39002MR595820
  100. Doron Zeilberger, Sister Celine’s technique and its generalizations, J. Math. Anal. Appl. 85 (1982), 114-145 Zbl0485.05003MR647562
  101. Doron Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207-211 Zbl0701.05001MR1048463
  102. Doron Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), 321-368 Zbl0738.33001MR1090884
  103. Doron Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195-204 Zbl0738.33002MR1103727
  104. Doron Zeilberger, Towards a WZ evaluation of the Mehta integral, SIAM J. Math. Anal. 25 (1994), 812-814 Zbl0934.33002MR1266590
  105. Bao-Yin Zhang, A new elementary algorithm for proving q -hypergeometric identities, J. Symbolic Comput. 35 (2003), 293-303 Zbl1020.33006MR1962797

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.