Converging to Gosper's algorithm

DOI10.1016/J.AAM.2007.11.004MaRDI QIDQ950412zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Husam L. Saad, Peter Paule

Publication date 22 October 2008

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.3386

zbMATH Keywords

Abramov's algorithmdispersionGosper's algorithmuniversal denominator

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10)

Abstract: Given two polynomials, we find a convergence property of the GCD of the rising factorial and the falling factorial. Based on this property, we present a unified approach to computing the universal denominators as given by Gosper's algorithm and Abramov's algorithm for finding rational solutions to linear difference equations with polynomial coefficients.

Review text

Let \(K\) be a field of characteristic zero. A nonzero term \(t_n\) is called a hypergeometric term over \(K\) if there exists a rational function, \(r\in K(n)\) such that \(t_{n+1}/t_n= r(n)\). In [Proc. Natl. Acad. Sci. USA 75, 40--42 (1978; Zbl 0384.40001)] \textit{R. W. Gosper, jun.} introduced an algorithm as a procedure to find a hypergeometric term \(z_n\) satisfying \(z_{n+1}- z_n= t_n\), if it exists, or confirm the nonexistence of any solution. More generally, given a linear difference equation, \textit{S. A. Abramov} has offered in [Difference equations in the field of rational functions. Analytical and numerical methods for solving problems of mathematical physics, Work Collect., Moskva, 117--121 (1989; Zbl 0728.39002)] another algorithm. The author presents a unified approach to computing the so-called universal denominators as given by Gosper's algorithm and Abramov's algorithm for finding rational solutions to linear difference equations with polynomial coefficients.

Recommendations

• Factorization of polynomials and GCD computations for finding universal denominators
• Denominators of rational solutions of linear difference systems of an arbitrary order
• Rational summation and Gosper-Petkovšek representation
• Rational solutions of linear difference and \(q\)-differential equations with polynomial coefficients
• Rational solutions of linear difference and q-difference equations with polynomial coefficients

Cites work

• A fast algorithm for proving terminating hypergeometric identities
• A generalization of Gosper's algorithm
• A holonomic systems approach to special functions identities
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• Decision procedure for indefinite hypergeometric summation
• Greatest factorial factorization and symbolic summation
• scientific article; zbMATH DE number 4139223 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 1254263 (Why is no real title available?)
• scientific article; zbMATH DE number 1254264 (Why is no real title available?)
• scientific article; zbMATH DE number 1131976 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• Hypergeometric solutions of linear recurrences with polynomial coefficients
• Improvement of the degree setting in Gosper's algorithm
• Low complexity algorithms for linear recurrences
• Special formal series solutions of linear operator equations
• The method of creative telescoping

Cited in

(6)

• An algorithm for deciding the summability of bivariate rational functions
• On the Gosper-Petkovšek representation of rational functions
• Resultant-free computation of indefinite hyperexponential integrals
• Minimal universal denominators for linear difference equations
• Denominator bounds for higher order systems of linear recurrence equations
• Creative telescoping for hypergeometric double sums

Describes a project that uses

Uses Software

• DiffTools

This page was built for publication: Converging to Gosper's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950412)