The extended Zeilberger algorithm with parameters (Q413409)

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 \[ a_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). \] 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\)). In the present paper, the authors extend Zeilberger's algorithm to solve the more general telescoping problem \[ a_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) \] 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.