On the summation of <bi>P</bi>-recursive sequences

ABSTRACT

We consider sequences which satisfy a linear recurrence equation Ly = 0 with polynomial coefficients. A criterion, i.e., a necessary and sufficient condition is proposed for validity of the discrete Newton-Leibniz formula when a primitive (an indefinite sum) Rt of a solution t of Ly = 0 is obtained either by Gosper's algorithm or by the Accurate Summation algorithm (the operator R has rational-function coefficients, ordR = ordL−1; in the Gosper case ordL = 1, ordR = 0). Additionally we show that if Gosper's algorithm succeeds on L, ordL = 1, then Ly = 0 always has some nonzero solutions t, defined everywhere, such that the discrete Newton-Leibniz formula Ε^w_k=v t(k) = u(w+1)−u(v) is valid for u = Rt and any integer bounds v≤w.

REFERENCES

• 1: S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients, USSR Computational Mathematics and Mathematical Physics, v.29 n.6, p.7-12, 1989 [doi>10.1016/S0041-5553(89)80002-3]
• 2: S. A. Abramov, Rational solutions of linear difference and q-difference equations with polynomial coefficients, Programming and Comput. Software 21 (1995), 273--278. Transl. from Programmirovanie 21 (1995), 3--11.
• 3: S. A. Abramov, M. van Hoeij, Integration of solutions of linear functional equations, Integral transforms and Special Functions 8 (1999), 3--12.
• 4: S. A. Abramov , M. Petkovšsek, Gosper's algorithm, accurate summation, and the discrete Newton-Leibniz formula, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.5-12, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073888]
• 5: R. W. Gosper, Jr., Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75 (1978), 40--42.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
P-recursive sequence, Gosper's algorithm, accurate summation algorithm, discrete Newton-Leibniz formula, hypergeometric term