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

dispersionGosper's algorithmuniversal denominatorAbramov's algorithm

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.

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

• 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?)
• 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
• 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
• Denominator bounds for higher order systems of linear recurrence equations
• Creative telescoping for hypergeometric double sums
• Minimal universal denominators for linear difference equations
• Resultant-free computation of indefinite hyperexponential integrals
• On the Gosper-Petkovšek representation of rational functions

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)