Gosper's Algorithm and Rational Solutionsof First Order Recurrences

Abstract


Abstract

In this paper we give two approaches for Gosper's algorithm. Also we give analysis to the degree of rational solutions of certain first order difference equation. Furthermore, we present an approach to find rational solutions of first order recurrences.

: Gosper's algorithm, hypergeometric solution, rational solution.

1. Notations
Let be the set of natural numbers, be the field of characteristic zero, be the field of rational functions over , be the ring of polynomials over , deg( ) denotes the polynomial degree (in ) of any , . We define . We assume the result of any gcd (greatest common divisor) computation in as being normalized to a monic polynomial , i.e., the leading coefficient of being 1. Recall that a non-zero term is called a hypergeometric term over if there exists a rational function such that