Simplification of definite sums of rational functions by creative symmetrizing method

ABSTRACT

We propose a strategy for simplification of definite sums of rational functions which, for a given input rational function F(n, k), constructs two rational functions G(n) and T(n, k) such that∑k=0ⁿF(n, k) = G(n) + ∑k=0ⁿT(n, k),where the degree of the denominator w.r.t. k of T(n, k) is "small". The strategy is based on well-known algorithms which solve the indefinite sum of rational functions and on the creative symmetrizing method. It provides a tool for finding closed forms for some instances of definite sums of rational functions where Zeilberger's creative telescoping method is not applicable.

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: Yiu-Kwong Man , Francis J. Wright, Fast polynomial dispersion computation and its application to indefinite summation, Proceedings of the international symposium on Symbolic and algebraic computation, p.175-180, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190413]
• 5: P. Paule. Short and easy computer proofs of the Rogers-Ramanujan identities and of identities of similar type. Electron. J. Combin., 1, 1994.
• 6: Peter Paule, Greatest factorial factorization and symbolic summation, Journal of Symbolic Computation, v.20 n.3, p.235-268, Sept. 1995 [doi>10.1006/jsco.1995.1049]
• 7: P. Paule and A. Riese. A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated approach to q-hypergeometric telescoping. Special Functions, q-Series and Related Topics, Fields Inst. Commun., 14:179-210, 1997.
• 8: M. Petkovšek, H. Wilf, and D. Zeilberger. A=B. A. K. Peters, Massachusetts, 1996.
• 9: 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]
• 10: 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.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Rational approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Algorithms, Documentation, Standardization