For a specified hypergeometric term $T\left(n\,k\right)$ of n and k, the Zeilberger(T, n, k, En) command constructs for $T\left(n\,k\right)$ a Z-pair $L,G$ that consists of a linear difference operator with coefficients that are polynomials of n over the complex number field

and a function $G\left(n\,k\right)$ such that

En is the shift operator with respect to n, defined by $\mathrm{En}\left(T\left(n\,k\right)\right)=T\left(n+1\,k\right)$.

The algorithm uses an item-by-item examination of the order v of L. It starts with the value of 0 for v and increases v until it is successful in finding a Z-pair $L,G$ provided that such a pair exists. Note that a maximum value of the order of the difference operator L in the Z-pair $L,G$ must be specified. This can be controlled by assigning a value to the global variable _MAXORDER (the default value of _MAXORDER is $6$). Additionally, by assigning values to the global variables _MINORDER and _MAXORDER, the algorithm is restricted to finding a Z-pair $L,G$ for $T\left(n\,k\right)$ such that the order of L is between _MINORDER and _MAXORDER.

The algorithm has two implementations. The default implementation is based on the universal denominators, and another one uses a variant of Gosper's algorithm. With the 'gosper' option, Gosper-based implementation is used.

The output from the Zeilberger command is a list of two elements $\left[L\,G\right]$ representing the computed Z-pair $L,G$.

The ZeilbergerRecurrence(T, n, k, f, l..u) command constructs the Zeilberger's recurrence. The function first computes the Z-pair $L,G$ for T and sums both sides of the relation $LT\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$ over k in the specified range $l..u$. This yields in general an inhomogeneous recurrence equation.

The possible ranges of $l..u$ include $rn+s..un+v$, $rn+s..\mathrm{\infty }$, $-\mathrm{\infty }..un+v$, and -infinity..infinity where r, s, u, and v are integers.

The Verify(T, 'Zpair', n, k, En) command verifies the correctness of the result ('Zpair') returned from Zeilberger, that is, it tries to verify that:

$\mathrm{with}\left(\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\right)\:$

$T≔{\left(-1\right)}^k\mathrm{binomial}\left(2n-2k\,n-k\right)\mathrm{binomial}\left(2k\,k\right)$

$T≔{\left(\mathrm{-1}\right)}^k\left(\genfrac{}{}{0ex}{}{2n-2k}{n-k}\right)\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$

$\mathrm{Zpair}≔\mathrm{Zeilberger}\left(T\,n\,k\,\mathrm{En}\right)\:$

$L≔\mathrm{Zpair}\left[1\right]$

$L≔\left(-n-2\right){\mathrm{En}}^2+16n+16$

$G≔\mathrm{Zpair}\left[2\right]$

$G≔\frac{4\left(-2n+2k-1\right)k{\left(\mathrm{-1}\right)}^k\left(\genfrac{}{}{0ex}{}{2n-2k}{n-k}\right)\left(\genfrac{}{}{0ex}{}{2k}{k}\right)}{\left(-n-1+k\right)\left(-n-2+k\right)}$

$\mathrm{Verify}\left(T\,'\mathrm{Zpair}'\,n\,k\,\mathrm{En}\right)$

$\mathrm{true}$

$T≔\frac{2n+3}{n^2-1}\left(n+8k+1\right)!$

$T≔\frac{\left(2n+3\right)\left(n+8k+1\right)!}{n^2-1}$

$\mathrm{Zeilberger}\left(T\,n\,k\,\mathrm{En}\right)$

Error, (in SumTools:-Hypergeometric:-Zeilberger) No recurrence of order 6 was found

$\mathrm{\_MINORDER}≔7\:$$\mathrm{\_MAXORDER}≔9\:$

$\mathrm{Zpair}≔\mathrm{Zeilberger}\left(T\,n\,k\,\mathrm{En}\right)\:$

$L≔\mathrm{Zpair}\left[1\right]$

$L≔\left(-2n^3-35n^2-174n-189\right){\mathrm{En}}^8+2n^3+19n^2-2n-19$

$\mathrm{Verify}\left(T\,'\mathrm{Zpair}'\,n\,k\,\mathrm{En}\right)$

$\mathrm{true}$

$\mathrm{\_MINORDER}≔0\:$

$T≔\frac{{\left(-1\right)}^k\mathrm{binomial}\left(n+1\,k+1\right)}{\mathrm{binomial}\left(\frac{ak+1}{a}\,k\right)}$

$T≔\frac{{\left(\mathrm{-1}\right)}^k\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)}{\left(\genfrac{}{}{0ex}{}{\frac{ak+1}{a}}{k}\right)}$

$\mathrm{ZeilbergerRecurrence}\left(T\,n\,k\,f\,0..n\right)$

$-f\left(n\right)+f\left(n+1\right)=\frac{1}{na+a+1}$

Petkovsek, M.; Wilf, H.; and Zeilberger, D. A=B. Wellesley, Massachusetts: A K Peters, Ltd., 1996.

Zeilberger, D. "The Method of Creative Telescoping." Journal of Symbolic Computing. Vol. 11. (1991): 195-204.