<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Parameterized Telescoping Proves Algebraic Independence of Sums
Carsten Schneider
Research Institute for Symbolic Computation, J. Kepler University Linz, Altenbergerstraβe 69, A-4040 Linz, Austria
Annals of Combinatorics 14 (4) pp.533-552 December, 2010
AMS Subject Classification: 33F10; 11J81
Usually creative telescoping is used to derive recurrences for sums. In this article we show that the non-existence of a creative telescoping solution, and more generally, of a parameterized telescoping solution, proves algebraic independence of certain types of sums. Combining this fact with summation-theory shows transcendence of whole classes of sums. Moreover, this result throws new light on the question why, for example, Zeilberger's algorithm fails to find a recurrence with minimal order.
Keywords:symbolic summation, algebraic independence of sums, creative telescoping


1. Abramov, S.A.: The summation of rational functions. Zh. Vychisl. Mat. Mat. Fiz. 11, 1071--1075 (1971)

2. Abramov, S.A.: When does Zeilberger's algorithm succeed? Adv. Appl. Math. 30(3), 424--441 (2003)

3. Abramov, S.A., Petkovsek, M.: Rational normal forms and minimal decompositions of hypergeometric terms. J. Symbolic Comput. 33(5), 521--543 (2002)

4. Bauer, A., Petkovsek, M.: Multibasic and mixed hypergeometric Gosper-type algorithms. J. Symbolic Comput.
28(4-5), 711--736 (1999)

5. Bronstein, M.: On solutions of linear ordinary difference equations in their coefficient field. J. Symbolic Comput. 29(6), 841--877 (2000)

6. Gosper, R.W.: Decision procedures for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. USA 75(1), 40--42 (1978)

7. Karr, M.: Summation in finite terms. J. Assoc. Comput. Mach. 28(2), 305--350 (1981)

8. Paule, P., Nemes, I.: A canonical form guide to symbolic summation. In: Miola, A., Temperini, M. (eds.) Advances in the Design of Symbolic Computation Systems, pp. 84--110. Springer,
Vienna (1997)

9. Paule, P.: Greatest factorial factorization and symbolic summation. J. Symbolic Comput. 20(3), 235--268 (1995)

10. Paule, P.: Contiguous relations and creative telescoping. Preprint (2004)

11. Paule, P., Riese, A.: A {M}athematica q-analogue of Zeilberger's algorithm based on an algebraically motivated aproach to q-hypergeometric telescoping. In: Ismail, M., Rahman, M. (eds.) Special Functions, q-Series and Related Topics, Fields Inst. Commun., 14, pp. 179--210. AMS, Providence, RI (1997)

12. Paule, P., Schorn, M.: A Mathematica version of Zeilberger's algorithm for proving binomial coefficient identities. J. Symbolic Comput. 20(5-6), 673--698 (1995)

13. Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities. Adv. Appl. Math. 31(2), 359--378 (2003)

14. Petkovsek, M., Wilf, H.S., Zeilberger, D.: A=B. A. K. Peters, Ltd., Wellesley, MA (1996)

15. Schneider, C.: Symbolic Summation in Difference Fields. PhD Thesis, J. Kepler University, Linz (2001)

16. Schneider, C.: A collection of denominator bounds to solve parameterized linear difference equations in ΠΣ-extensions. An. Univ. Timisoara Ser. Mat.-Inform. 42(2), 163--179, (2004)

17. Schneider, C.: The summation package Sigma: underlying principles and a rhombus tiling application. Discrete Math. Theor. Comput. Sci. 6(2), 365--386 (2004)

18. Schneider, C.: Degree bounds to find polynomial solutions of parameterized linear difference equations in ΠΣ-fields. Appl. Algebra Engrg. Comm. Comput. 16(1), 1--32 (2005)

19. Schneider, C.: Product representations in ΠΣ-fields. Ann. Combin. 9(1), 75--99 (2005)

20. Schneider, C.: Solving parameterized linear difference equations in terms of indefinite nested sums and products. J. Differ. Equations Appl. 11(9), 799--821 (2005)

21. Schneider, C.: Simplifying Sums in ΠΣ*-Extensions. J. Algebra Appl. 6(3), 415--441 (2007)

22. Schneider, C.: Symbolic summation assists combinatorics. Sem. Lothar. Combin. 56, \#B56b. (2007)

23. Schneider, C.: A refined difference field theory for symbolic summation. J. Symbolic Comput. 43(9), 611--644 (2008)

24. van der Poorten, A.: A proof that Euler missed... Apéry's proof of the irrationality of ζ(3). Math. Intelligencer 1(4), 195--203 (1979)

25. Zeilberger, D.: The method of creative telescoping. J. Symbolic Comput. 11(3), 195--204 (1991)