Stavros Garoufalidis and Xinyu Sun
Abstract: We introduce a new algorithm to find recursions of proper hypergeometric multisums. Our algorithm treats one summation variable at a time, and provides rational certificates along the way. We also provide an algorithm to construct a polynomial divisible by the denominator of any rational solution $x(n)$ to $$ \frac{a_m(n)}{b_m(n)}x(n+m)+\cdots+\frac{a_0(n)}{b_0(n)}x(n)= \frac{c(n)}{d(n)},$$ where $a_i(n), b_i(n), c(n), d(n)$ are polynomials. The algorithm improves Abramov's universal denominator. In the case of single sums our algorithm differs from Zeilberger's Gosper summation and appears to be more efficient.
Key words: WZ-algorithm, Creative Telescoping, Gosper's algorithm, Zeilberger's algorithm, hypergeometric, multisum, recursion Abramov's algorithm, universal denominator.
Notes: 12 pages, 0 figures.
Computer files with examples and a Maple program, iSum created by Xinyu Sun.