The Simplified Zeilberger Algorithm

implemented in a Mathematica package by 
Andrew Sills, Rutgers University
version of January 24, 2006.

Introduction

Zeilberger's algorithm (also known as the creative telescoping algorithm) finds a recurrence of the form
∑\(TraditionalForm\`\_\(i = 0\)\%L\)(Subscript[e, i])(n) F(n+i,k) = G(n,k+1) - G(n,k)            (*)
where F is a hypergeometric term in n and k with finite support and G is a rational function multiple of F.

The original Zeilberger algorithm is discussed in
	[1] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207-211.
	[2] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195-204.
	[3] M. Petkovsek, H.S. Wilf and D. Zeilberger, A=B, A.K. Peters, 1996.

A simplified version of the algorithm (implemented in the Mathematica package NewZeil.m) is implied by the theoretical results in
	[4] M. Mohammed and D. Zeilberger, Sharp upper bounds for the orders of the recurrences output by the Zeilberger and q-Zeilberger algorithms, J. Symbolic Comput. 39(2005), 201-207.

Examples

First, load the package:

<< NewZeil.m

Consider the following examples.  The output is of the form { Recurrence, Certificate }, where "Recurrence" is recurrence found by the algorithm from the left hand side of (*) above and "Certificate" is the rational certificate function (which equals G/F from (*) above).

The input format of the main function, Zeil, is
Zeil[ H, z, POL, sum_var, discrete_var, {params}], where
	H is the 'pure hypergeometric part', i.e. ratios of Pochhammer symbols, binomial coefficients, and factorials;
	z is the hypergeometric argument;
	sum_var is a symbol to represent the summation index (usually denoted by k in the WZ literature);
	discrete_var is a symbol to represent the discrete parameter (usually denoted by n in the WZ literature);
	shift_op is is a symbol to represent the shift operator (usually deonted by N in the WZ literature); and
	{params} is an optional list of additional parameters.
Consider the following examples.

Zeil[ Binomial[n, k],  1, 1, k, n]

Zeil[ Binomial[n, k], z, 1, k, n]

Zeil[ Binomial[n, k]^2,  1, 1, k, n]

Zeil[ Binomial[n, k]^3, 1, 1, k, n]

Zeil[ Pochhammer[a, k] Pochhammer[n, k],  1, 1, k, 
      n, {a}]

Zeil[ 1/k!^3  Pochhammer[n, k], 1, n^3 + k, k, n]

Zeil[Binomial[x, k] Binomial[a, n - k], 1, 1, k, n, {x, a}]

If the global variable 'Verbose' is set to 'True', the results of intermediate calculatations are displayed using the notation of [4], allowing the user to follow the details of the simplified Zeilberger algorithm.

Verbose = True

Zeil[ Pochhammer[a, k] Pochhammer[n, k],  1, 1, k, 
      n, {a}]