Converging to Gosper's Algorithm

2007/11/21 by William Y. C. Chen, Peter Paule, Chen, William Y. C. +3
Computer Science · Mathematics · #05A19 #33F10 #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #Mathematical functions and polynomials #Mathematics and Applications #Polynomial and algebraic computation #math.CA #math.CO #msc:05A19 #msc:33F10

paper · pdf · doi:10.48550/arxiv.0711.3386

13 pages

arxiv created 2007/11/21 · openalex publication_date 2007/11/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• A Refined Denominator Bounding Algorithm for Multivariate Linear Difference Equations
• Simple algorithm for GCD of polynomials
• Rational Solutions to the First Order Difference Equations in the Bivariate Difference Field
• On the Computation of the Galois Group of Linear Difference Equations
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors