SumTools[Hypergeometric] - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Summation and Difference Equations : SumTools : Hypergeometric Subpackage : SumTools/Hypergeometric/Zeilberger

SumTools[Hypergeometric]

 Zeilberger
 perform Zeilberger's algorithm
 ZeilbergerRecurrence
 construct the Zeilberger's recurrence
 Verify
 verify the result from Zeilberger's algorithm

 Calling Sequence Zeilberger(T, n, k, En) Zeilberger(T, n, k, En, 'gosper') ZeilbergerRecurrence(T, n, k, f, l..u) Verify(T, 'Zpair', n, k, En)

Parameters

 T - hypergeometric term of n and k n - name k - name En - name; denote the shift operator with respect to n f - name of the recurrence function l..u - range for k 'Zpair' - list of two elements specifying a Z-pair for T

Description

 • 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

$L={a}_{v}\left(n\right){\mathrm{En}}^{v}+\mathrm{...}+{a}_{1}\left(n\right)\mathrm{En}+{a}_{0}\left(n\right)$

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

$LT\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right).$

 • 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:

$LT\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right).$

Examples

 > with(SumTools[Hypergeometric]):
 > T := (-1)^k*binomial(2*n-2*k,n-k)*binomial(2*k,k);
 ${T}{≔}{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{2}{}{k}}{{n}{-}{k}}\right){}\left(\genfrac{}{}{0}{}{{2}{}{k}}{{k}}\right)$ (1)
 > Zpair := Zeilberger(T,n,k,En):
 > L := Zpair[1];
 ${L}{≔}\left({-}{n}{-}{2}\right){}{{\mathrm{En}}}^{{2}}{+}{16}{}{n}{+}{16}$ (2)
 > G := Zpair[2];
 ${G}{≔}\frac{{4}{}\left({-}{2}{}{n}{+}{2}{}{k}{-}{1}\right){}{k}{}{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{2}{}{k}}{{n}{-}{k}}\right){}\left(\genfrac{}{}{0}{}{{2}{}{k}}{{k}}\right)}{\left({-}{n}{-}{1}{+}{k}\right){}\left({-}{n}{-}{2}{+}{k}\right)}$ (3)
 > Verify(T,'Zpair',n,k,En);
 ${\mathrm{true}}$ (4)

Maple returns an error if no Z-pair is found in the specified order range (by default $\mathrm{order}\left(L\right)\le 6$).

 > T := (2*n+3)/(n^2-1)*(n+8*k+1)!;
 ${T}{≔}\frac{\left({2}{}{n}{+}{3}\right){}\left({n}{+}{8}{}{k}{+}{1}\right){!}}{{{n}}^{{2}}{-}{1}}$ (5)
 > Zeilberger(T,n,k,En);

Try Zeilberger's algorithm with order of L restricted to the range from $7$ to $9$.

 > _MINORDER := 7: _MAXORDER := 9:
 > Zpair := Zeilberger(T,n,k,En):
 > L := Zpair[1];
 ${L}{≔}\left({-}{2}{}{{n}}^{{3}}{-}{35}{}{{n}}^{{2}}{-}{174}{}{n}{-}{189}\right){}{{\mathrm{En}}}^{{8}}{+}{2}{}{{n}}^{{3}}{+}{19}{}{{n}}^{{2}}{-}{2}{}{n}{-}{19}$ (6)
 > Verify(T,'Zpair',n,k,En);
 ${\mathrm{true}}$ (7)
 > _MINORDER := 0:
 > T := (-1)^k*binomial(n+1,k+1)/binomial((a*k+1)/a,k);
 ${T}{≔}\frac{{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{n}{+}{1}}{{k}{+}{1}}\right)}{\left(\genfrac{}{}{0}{}{\frac{{a}{}{k}{+}{1}}{{a}}}{{k}}\right)}$ (8)
 > ZeilbergerRecurrence(T,n,k,f,0..n);
 ${-}{f}{}\left({n}\right){+}{f}{}\left({n}{+}{1}\right){=}\frac{{1}}{{a}{}{n}{+}{a}{+}{1}}$ (9)

References

 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.