Applicability of Zeilberger's algorithm to hypergeometric terms

ABSTRACT

A terminating condition of the well-known Zeilberger's algorithm for a given hypergeometric term T(n, k) is presented. It is shown that the only information on T(n, k) that one needs in order to determine in advance whether this algorithm will succeed is the rational function T(n, k + 1)/T(n, k).

REFERENCES

• 1: S. Abramov. Rational component of the solutions of a first-order linear recurrence relation with a rational right-hand side. USSR Comput. Math. Phys., Transl. from Zh. vychisl. mat. mat. fyz., 14:1035-1039, 1975.
• 2: S. A. Abramov, Indefinite sums of rational functions, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.303-308, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220386]
• 3: S. Abramov and H. Le. Applicability of Zeilberger's algorithm to rational functions. In Proc. Formal Power Series and Algebraic Combinatorics, pages 91-102. Springer-Verlag LNCS, 2000.
• 4: S. Abramov and M. Petkovšek. Canonical representations of hypergeometric terms. In Proc. Formal Power Series and Algebraic Combinatorics, pages 1-10. Arizona State University, 2001.
• 5: Sergei A. Abramov , M. Petkovsek, Minimal decomposition of indefinite hypergeometric sums, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.7-14, July 2001, London, Ontario, Canada [doi>10.1145/384101.384103]
• 6: S. Abramov and M. Petkovšek. Proof of a conjecture of Wilf and Zeilberger. University of Ljubljana, Preprint series, 39, 2001.
• 7: S. A. Abramov , M. Petkovšek, On the structure of multivariate hypergeometric terms, Advances in Applied Mathematics, v.29 n.3, p.386-411, October 2002 [doi>10.1016/S0196-8858(02)00022-2 ]
• 8: H. Gould. Combinatorial Identities. Morgantown, W. Va, 1972.
• 9: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 10: O. Ore. Sur la forme de fonctions hypergeometriques de plusiers variables. J. math. pure et appl., 9:311-327, no 4, 1930.
• 11: Marko Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, Journal of Symbolic Computation, v.14 n.2-3, p.243-264, Aug./Sept. 1992 [doi>10.1016/0747-7171(92)90038-6]
• 12: M. Petkovšek, H. Wilf, and D. Zeilberger. A=B. A. K. Peters, Massachusetts, 1996.
• 13: Roberto Pirastu , Volker Strehl, Rational summation and Gosper-Petkovsˇek, Journal of Symbolic Computation, v.20 n.5-6, p.617-635, Nov./Dec. 1995 [doi>10.1006/jsco.1995.1068 ]
• 14: M. Sato. Theory of prehomogeneous vector spaces (algebraic part). Nagoya Math. J, 120:1-34, 1990.
• 15: P. Verbaeten. The automatic construction of pure recurrence relations. In Proc. EUROCAL'74, ACM-SIGSAM Bulletin, pages 96-98. ACM Press, 1995.
• 16: H. Wilf and D. Zeilberger. An algorithmic proof theory for hypergeometric (ordinary and "q") multisum/integral identities. Inventiones Mathematicae, 108:575-633, 1992.
• 17: Doron Zeilberger, The method of creative telescoping, Journal of Symbolic Computation, v.11 n.3, p.195-204, March 1991 [doi>10.1016/S0747-7171(08)80044-2]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions
      G.2.2 Graph Theory
          Subjects: Hypergraphs

General Terms:
Algorithms, Documentation