In mathematics, Gosper's algorithm, due to Bill Gosper, is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose one has a(1) + ... + a(n) = S(n) − S(0), where S(n) is a hypergeometric term (i.e., S(n + 1)/S(n) is a rational function of n); then necessarily a(n) is itself a hypergeometric term, and given the formula for a(n) Gosper's algorithm finds that for S(n).
Step 1: Find a polynomial p such that, writing b(n) = a(n)/p(n), the ratio b(n)/b(n − 1) has the form q(n)/r(n) where q and r are polynomials and no q(n) has a nontrivial factor with r(n + j) for j = 0, 1, 2, ... . (This is always possible, whether or not the series is summable in closed form.)
Step 2: Find a polynomial ƒ such that S(n) = q(n + 1)/p(n) ƒ(n) a(n). If the series is summable in closed form then clearly a rational function ƒ with this property exists; in fact it must always be a polynomial, and an upper bound on its degree can be found. Determining ƒ (or finding that there is no such ƒ) is then a matter of solving a system of linear equations. [1]
Gosper's algorithm can be used to discover Wilf–Zeilberger pairs, where they exist. Suppose that F(n + 1, k) − F(n, k) = G(n, k + 1) − G(n, k) where F is known but G is not. Then feed a(k) := F(n + 1, k) − F(n, k) into Gosper's algorithm. (Treat this as a function of k whose coefficients happen to be functions of n rather than numbers; everything in the algorithm works in this setting.) If it successfully finds S(k) with S(k) − S(k − 1) = a(k), then we are done: this is the required G. If not, there is no such G.
Gosper's algorithm finds (where possible) a hypergeometric closed form for the indefinite sum of hypergeometric terms. It can happen that there is no such closed form, but that the sum over alln, or some particular set of values of n, has a closed form. This question is only meaningful when the coefficients are themselves functions of some other variable. So, suppose a(n,k) is a hypergeometric term in both n and k: that is, a(n, k)/a(n − 1,k) and a(n, k)/a(n, k − 1) are rational functions of n and k. Then Zeilberger's algorithm and Petkovšek's algorithm may be used to find closed forms for the sum over k of a(n, k).
Bill Gosper discovered this algorithm in the 1970s while working on the Macsyma computer algebra system at SAIL and MIT.
In mathematics, a field F is algebraically closed if every non-constant polynomial in F[x] has a root in F.
In mathematics, a polynomial is an expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example in three variables is x3 + 2xyz2 − yz + 1.
In mathematics, a generating function is a way of encoding an infinite sequence of numbers by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.
In algebra, the partial fraction decomposition or partial fraction expansion of a rational fraction is an operation that consists of expressing the fraction as a sum of a polynomial and one or several fractions with a simpler denominator.
In symbolic computation, the Risch algorithm is a method of indefinite integration used in some computer algebra systems to find antiderivatives. It is named after the American mathematician Robert Henry Risch, a specialist in computer algebra who developed it in 1968.
In mathematics, a generalized hypergeometric series is a power series in which the ratio of successive coefficients indexed by n is a rational function of n. The series, if convergent, defines a generalized hypergeometric function, which may then be defined over a wider domain of the argument by analytic continuation. The generalized hypergeometric series is sometimes just called the hypergeometric series, though this term also sometimes just refers to the Gaussian hypergeometric series. Generalized hypergeometric functions include the (Gaussian) hypergeometric function and the confluent hypergeometric function as special cases, which in turn have many particular special functions as special cases, such as elementary functions, Bessel functions, and the classical orthogonal polynomials.
In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form
In mathematics, hypergeometric identities are equalities involving sums over hypergeometric terms, i.e. the coefficients occurring in hypergeometric series. These identities occur frequently in solutions to combinatorial problems, and also in the analysis of algorithms.
In mathematics, the Gaussian or ordinary hypergeometric function2F1(a,b;c;z) is a special function represented by the hypergeometric series, that includes many other special functions as specific or limiting cases. It is a solution of a second-order linear ordinary differential equation (ODE). Every second-order linear ODE with three regular singular points can be transformed into this equation.
In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
Herbert Saul Wilf was a mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He wrote numerous books and research papers. Together with Neil Calkin he founded The Electronic Journal of Combinatorics in 1994 and was its editor-in-chief until 2001.
In mathematics, and more specifically in analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable dimension condition in terms of D-modules theory. More precisely, a holonomic function is an element of a holonomic module of smooth functions. Holonomic functions can also be described as differentiably finite functions, also known as D-finite functions. When a power series in the variables is the Taylor expansion of a holonomic function, the sequence of its coefficients, in one or several indices, is also called holonomic. Holonomic sequences are also called P-recursive sequences: they are defined recursively by multivariate recurrences satisfied by the whole sequence and by suitable specializations of it. The situation simplifies in the univariate case: any univariate sequence that satisfies a linear homogeneous recurrence relation with polynomial coefficients, or equivalently a linear homogeneous difference equation with polynomial coefficients, is holonomic.
Mary Celine Fasenmyer, RSM was an American mathematician and Catholic religious sister. She is most noted for her work on hypergeometric functions and linear algebra.
In mathematics, specifically combinatorics, a Wilf–Zeilberger pair, or WZ pair, is a pair of functions that can be used to certify certain combinatorial identities. WZ pairs are named after Herbert S. Wilf and Doron Zeilberger, and are instrumental in the evaluation of many sums involving binomial coefficients, factorials, and in general any hypergeometric series. A function's WZ counterpart may be used to find an equivalent and much simpler sum. Although finding WZ pairs by hand is impractical in most cases, Gosper's algorithm provides a sure method to find a function's WZ counterpart, and can be implemented in a symbolic manipulation program.
In mathematics, the Dyson conjecture is a conjecture about the constant term of certain Laurent polynomials, proved independently in 1962 by Wilson and Gunson. Andrews generalized it to the q-Dyson conjecture, proved by Zeilberger and Bressoud and sometimes called the Zeilberger–Bressoud theorem. Macdonald generalized it further to more general root systems with the Macdonald constant term conjecture, proved by Cherednik.
Petkovšek's algorithm is a computer algebra algorithm that computes a basis of hypergeometric terms solution of its input linear recurrence equation with polynomial coefficients. Equivalently, it computes a first order right factor of linear difference operators with polynomial coefficients. This algorithm was developed by Marko Petkovšek in his PhD-thesis 1992. The algorithm is implemented in all the major computer algebra systems.
In mathematics a P-recursive equation can be solved for polynomial solutions. Sergei A. Abramov in 1989 and Marko Petkovšek in 1992 described an algorithm which finds all polynomial solutions of those recurrence equations with polynomial coefficients. The algorithm computes a degree bound for the solution in a first step. In a second step an ansatz for a polynomial of this degree is used and the unknown coefficients are computed by a system of linear equations. This article describes this algorithm.
In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989.
In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equationswith polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive or D-finite.
Gosper, Jr., Ralph William "Bill" (January 1978) [1977-09-26]. "Decision procedure for indefinite hypergeometric summation" (PDF). Proceedings of the National Academy of Sciences of the United States of America . Mathematics. Xerox, Palo Alto Research Center, Palo Alto, California, USA. 75 (1): 40–42. Archived (PDF) from the original on 2019-04-12. Retrieved 2020-01-10. algorithm / binomial coefficient identities / closed form / symbolic computation / linear recurrences