Zeilberger's Algorithm

An Algorithm which finds a Polynomial recurrence for terminating Hypergeometric Identities of the form

$$\sum_k {n\choose k} {\prod_{i=1}^A (a_in+a_i'k+a_i'')!\over ... ...a_i')!\over\prod_{i=1}^{\bar B}(\bar b_in+\bar b_i')}\bar x^n,$$

where ${n\choose k}$ is a Binomial Coefficient, $a_i$, $a_i'$, $\bar a_i$, $b_i$, $b_i'$, $\bar b_i$ are constant integers and $a_i''$, $\bar a_i'$, $b_i''$, $\bar b_i'$, $C$, $x$, and $z$ are complex numbers (Zeilberger 1990). The method was called Creative Telescoping by van der Poorten (1979), and led to the development of the amazing machinery of Wilf-Zeilberger Pairs.

See also Binomial Series, Gosper's Algorithm, Hypergeometric Identity, Sister Celine's Method, Wilf-Zeilberger Pair

References

Krattenthaler, C. ``HYP and HYPQ: The Mathematica Package HYP.'' http://radon.mat.univie.ac.at/People/kratt/hyp_hypq/hyp.html.

Paule, P. and Riese, A. ``A Mathematica $q$-Analogue of Zeilberger's Algorithm Based on an Algebraically Motivated Approach to $q$-Hypergeometric Telescoping.'' In Special Functions, $q$-Series and Related Topics, Fields Institute Communications 14, 179-210, 1997.

Paule, P. and Schorn, M. ``A Mathematica Version of Zeilberger's Algorithm for Proving Binomial Coefficient Identities.'' J. Symb. Comput. 20, 673-698, 1995.

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. ``Zeilberger's Algorithm.'' Ch. 6 in A=B. Wellesley, MA: A. K. Peters, pp. 101-119, 1996.

Riese, A. ``A Generalization of Gosper's Algorithm to Bibasic Hypergeometric Summation.'' Electronic J. Combinatorics 1, R19 1-16, 1996. http://www.combinatorics.org/Volume_1/volume1.html#R19.

van der Poorten, A. ``A Proof that Euler Missed... Apéry's Proof of the Irrationality of $\zeta(3)$.'' Math. Intel. 1, 196-203, 1979.

Wegschaider, K. Computer Generated Proofs of Binomial Multi-Sum Identities. Diploma Thesis, RISC. Linz, Austria: J. Kepler University, May 1997.

Zeilberger, D. ``Doron Zeilberger's Maple Packages and Programs: EKHAD.'' http://www.math.temple.edu/~zeilberg/programs.html.

Zeilberger, D. ``A Fast Algorithm for Proving Terminating Hypergeometric Series Identities.'' Discrete Math. 80, 207-211, 1990.

Zeilberger, D. ``A Holonomic Systems Approach to Special Function Identities.'' J. Comput. Appl. Math. 32, 321-368, 1990.

Zeilberger, D. ``The Method of Creative Telescoping.'' J. Symb. Comput. 11, 195-204, 1991.