The extended Zeilberger algorithm with parameters

DOI10.1016/J.JSC.2011.12.024MaRDI QIDQ413409zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Qing-Hu Hou, Yan-Ping Mu

Publication date 7 May 2012

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

Gosper's algorithmhypergeometric seriesorthogonal polynomialssymbolic summationZeilberger's algorithm

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Hypergeometric functions (33C99) Basic hypergeometric functions in one variable, ({}_rphi_s) (33D15) Basic orthogonal polynomials and functions (Askey-Wilson polynomials, etc.) (33D45) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30)

Abstract: For a hypergeometric series $su{m}_{k}f(k,a,b,\mathrm{...},c)$ with parameters $a,b,>\mathrm{...},c$, Paule has found a variation of Zeilberger's algorithm to establish recurrence relations involving shifts on the parameters. We consider a more general problem concerning several similar hypergeometric terms $f_1(k,a,b,\mathrm{...},c)$, $f_2(k,a,b,\mathrm{...},c)$, $\mathrm{...}$, $f_m(k,a,b,\mathrm{...},c)$. We present an algorithm to derive a linear relation among the sums $su{m}_k{f}_i(k,a,b,\mathrm{...},c)$ $(1leqileqm)$. Furthermore, when the summand $f_i$ contains the parameter $x$, we can require that the coefficients be $x$-free. Such relations with $x$-free coefficients can be used to determine whether a polynomial sequence satisfies the three term recurrence and structure relations for orthogonal polynomials. The $q$-analogue of this approach is called the extended $q$-Zeilberger's algorithm, which can be employed to derive recurrence relations on the Askey-Wilson polynomials and the $q$-Racah polynomials.

Review text

Zeilberger's algorithm is a classic method in symbolic summation: for a sum with proper hypergeometric summands \(f(n,k)\), it derives a linear recurrence relation with polynomial coefficients. Stated differently, it solves the following telescoping problem: find rational functions \(a_0(n),\dots,a_m(n)\) and a hypergeometric term \(g(n,k)\) such that NEWLINE\[NEWLINEa_0(n)f(n,k) + a_1(n)f(n+1,k) + \dots + a_m(n)f(n+m,k) = g(n,k+1) - g(n,k).NEWLINE\]NEWLINE The hypergeometric nature of~\(f\) implies that all terms appearing on the left-hand side are pairwise similar (i.e., their quotient is a rational function in \(n\) and~\(k\)).NEWLINENEWLINEIn the present paper, the authors extend Zeilberger's algorithm to solve the more general telescoping problem NEWLINE\[NEWLINEa_0(n)f_0(n,k) + a_1(n)f_1(n,k) + \dots + a_m(n)f_m(n,k) = g(n,k+1) - g(n,k)NEWLINE\]NEWLINE where \(f_0,\dots,f_m\) are arbitrary, but pairwise similar hypergeometric terms. Previously, algorithms had been developed to solve such kinds of telescoping problems, but in more general contexts, e.g., in difference fields, or for multivariate holonomic functions. The algorithm can be easily adapted to the situation where the ground field contains some parameters, which one wants to prevent from appearing in the coefficients \(a_0,\dots,a_m\). The same ideas apply to basic (i.e., \(q\)-) hypergeometric terms. The paper concludes with an extensive list of examples: it is demonstrated how the algorithm can be applied to find linear relations among (basic) orthogonal polynomials and to derive multivariate recurrence equations for (basic) hypergeometric sums.

Recommendations

• Algorithms for m-fold hypergeometric summation
• Applicability of the \(q\)-analogue of Zeilberger's algorithm
• An extension of Zeilberger's fast algorithm to general holonomic functions
• scientific article; zbMATH DE number 1504574
• On homogeneous Zeilberger recurrences

Cites work

• Algorithms for \(q\)-hypergeometric summation in computer algebra
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• An extension of Zeilberger's fast algorithm to general holonomic functions
• Decision procedure for indefinite hypergeometric summation
• Extended Zeilberger's algorithm for identities on Bernoulli and Euler polynomials
• scientific article; zbMATH DE number 194092 (Why is no real title available?)
• scientific article; zbMATH DE number 1330281 (Why is no real title available?)
• scientific article; zbMATH DE number 1023404 (Why is no real title available?)
• Pfaff's method. I: The Mills-Robbins-Rumsey determinant.
• Pfaff's method. III: Comparison with the WZ method
• Representations of orthogonal polynomials
• Solving parameterized linear difference equations in terms of indefinite nested sums and products
• Summation in Finite Terms
• The method of creative telescoping

Cited in

(28)

• Quasi-orthogonality of some hypergeometric and q-hypergeometric polynomials
• Algorithms for m-fold hypergeometric summation
• Multibasic and mixed hypergeometric Gosper-type algorithms
• An extension of Zeilberger's fast algorithm to general holonomic functions
• Polynomial reduction and supercongruences
• Numerical computations of separability probabilities
• Applicability of the \(q\)-analogue of Zeilberger's algorithm
• On homogeneous Zeilberger recurrences
• Recurrences for Callan's generalization of Narayana polynomials
• SIMPLIFYING SUMS IN ΠΣ*-EXTENSIONS
• Recurrence relations for the connection coefficients of classical orthogonal polynomials
• scientific article; zbMATH DE number 6917125 (Why is no real title available?)
• Contiguous relations and creative telescoping
• Gosper summability of rational multiples of hypergeometric terms
• Inner bounds for the extreme zeros of _3F₂ hypergeometric polynomials
• Deconstructing the Zeilberger algorithm^†
• Formal residue and computer-assisted proofs of combinatorial identities
• Linear recurrence relations for sums of products of two terms
• On two-term hypergeometric recursions with free lower parameters
• Parameterized telescoping proves algebraic independence of sums
• The interlacing properties of generalized Narayana polynomials
• Reduction for congruences of partial sums of P-recursive sequences
• Creative telescoping for hypergeometric double sums
• Some supercongruences of hypergeometric sums and the WZ method
• Construction of WZ pairs by the extended Zeilberger algorithm
• Finding congruences with the WZ method
• Analytic properties of Speyer's g-polynomial of uniform matroids
• A definite summation of hypergeometric terms of special kind

Describes a project that uses

Uses Software

• qZeil

This page was built for publication: The extended Zeilberger algorithm with parameters

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