WZMethod - Maple Help

# Online Help

###### All Products    Maple    MapleSim

SumTools[Hypergeometric]

 WZMethod
 perform Wilf-Zeilberger's algorithm

 Calling Sequence WZMethod(f,r,n,k,cert)

Parameters

 f - function of n and k r - function of n n - variable k - variable cert - (optional) name; assigned the computed WZ certificate

Description

 • The WZMethod(f,r,n,k,cert) command certifies identities of the form ${\sum }_{k}f\left(n,k\right)=r\left(n\right)$.
 • Let $F\left(n,k\right)=\frac{f\left(n,k\right)}{r\left(n\right)}$ if $r\left(n\right)\ne 0$ and $F\left(n,k\right)=f\left(n,k\right)$, otherwise. If the method succeeds in certifying the given identity, the output is a list of two elements $\left[F,G\right]$ representing the WZ-pair $F,G$ such that $F\left(n+1,k\right)-F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$. Otherwise, it returns the error message "WZ method fails".
 • If the method is successful and if the fifth optional argument cert is given, cert is assigned the WZ certificate $R\left(n,k\right)=\frac{G\left(n,k\right)}{F\left(n,k\right)}$.
 • It is assumed that for each integer $0\le n$, $\underset{k\to \mathrm{\infty }}{lim}G\left(n,k\right)=0$ and $\underset{k\to -\mathrm{\infty }}{lim}G\left(n,k\right)=0$.

Examples

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

Proof of Gauss's 2F1 identity:

 > $f≔\frac{\left(n+k\right)!\left(b+k\right)!\left(c-n-1\right)!\left(c-b-1\right)!}{\left(c+k\right)!\left(n-1\right)!\left(c-n-b-1\right)!\left(k+1\right)!\left(b-1\right)!}$
 ${f}{≔}\frac{\left({n}{+}{k}\right){!}{}\left({b}{+}{k}\right){!}{}\left({c}{-}{n}{-}{1}\right){!}{}\left({c}{-}{b}{-}{1}\right){!}}{\left({c}{+}{k}\right){!}{}\left({n}{-}{1}\right){!}{}\left({c}{-}{n}{-}{b}{-}{1}\right){!}{}\left({k}{+}{1}\right){!}{}\left({b}{-}{1}\right){!}}$ (1)
 > $r≔1$
 ${r}{≔}{1}$ (2)
 > $\mathrm{WZpair}≔\mathrm{WZMethod}\left(f,r,n,k,'\mathrm{cert}'\right):$
 > $F≔\mathrm{WZpair}\left[1\right]$
 ${F}{≔}\frac{\left({n}{+}{k}\right){!}{}\left({b}{+}{k}\right){!}{}\left({c}{-}{n}{-}{1}\right){!}{}\left({c}{-}{b}{-}{1}\right){!}}{\left({c}{+}{k}\right){!}{}\left({n}{-}{1}\right){!}{}\left({c}{-}{n}{-}{b}{-}{1}\right){!}{}\left({k}{+}{1}\right){!}{}\left({b}{-}{1}\right){!}}$ (3)
 > $G≔\mathrm{WZpair}\left[2\right]$
 ${G}{≔}{-}\frac{\left(\left({c}{-}{n}{-}{2}{-}{b}\right){!}{}{n}{!}{}\left({n}{+}{k}\right){!}{}\left({c}{-}{n}{-}{1}\right){!}{-}\left({c}{-}{n}{-}{2}\right){!}{}\left({n}{+}{1}{+}{k}\right){!}{}\left({n}{-}{1}\right){!}{}\left({c}{-}{n}{-}{b}{-}{1}\right){!}\right){}\left({b}{+}{k}\right){!}{}\left({c}{-}{b}{-}{1}\right){!}{}\left({c}{+}{k}\right){}\left({k}{+}{1}\right)}{\left({c}{-}{n}{-}{b}{-}{1}\right){!}{}\left({n}{-}{1}\right){!}{}\left({b}{-}{1}\right){!}{}\left({k}{+}{1}\right){!}{}\left({c}{-}{n}{-}{2}{-}{b}\right){!}{}{n}{!}{}\left({c}{+}{k}\right){!}{}\left({k}{}{b}{+}{n}{}{b}{-}{k}{}{c}{+}{k}{}{n}{+}{b}{-}{c}{+}{k}{+}{n}{+}{1}\right)}$ (4)
 > $\mathrm{cert}$
 ${-}\frac{\left({k}{+}{1}\right){}\left({c}{+}{k}\right)}{\left({c}{-}{n}{-}{1}\right){}{n}}$ (5)

Proof of Dixon's identity:

 > $F≔{\left(-1\right)}^{k}\mathrm{binomial}\left(n+b,n+k\right)\mathrm{binomial}\left(n+c,c+k\right)\mathrm{binomial}\left(b+c,b+k\right)$
 ${F}{≔}{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{n}{+}{b}}{{n}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{n}{+}{c}}{{c}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{b}{+}{c}}{{b}{+}{k}}\right)$ (6)
 > $r≔\frac{\left(n+b+c\right)!}{n!b!c!}$
 ${r}{≔}\frac{\left({n}{+}{b}{+}{c}\right){!}}{{n}{!}{}{b}{!}{}{c}{!}}$ (7)
 > $\mathrm{WZpair}≔\mathrm{WZMethod}\left(F,r,n,k,'\mathrm{certificate}'\right):$
 > $F≔\mathrm{WZpair}\left[1\right]$
 ${F}{≔}\frac{{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{n}{+}{b}}{{n}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{n}{+}{c}}{{c}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{b}{+}{c}}{{b}{+}{k}}\right){}{n}{!}{}{b}{!}{}{c}{!}}{\left({n}{+}{b}{+}{c}\right){!}}$ (8)
 > $G≔\mathrm{WZpair}\left[2\right]$
 ${G}{≔}{-}\frac{\left(\left(\genfrac{}{}{0}{}{{n}{+}{1}{+}{b}}{{n}{+}{1}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{n}{+}{1}{+}{c}}{{c}{+}{k}}\right){}\left({n}{+}{1}\right){!}{}\left({n}{+}{b}{+}{c}\right){!}{-}\left({n}{+}{1}{+}{b}{+}{c}\right){!}{}\left(\genfrac{}{}{0}{}{{n}{+}{b}}{{n}{+}{k}}\right){}\left(\genfrac{}{}{0}{}{{n}{+}{c}}{{c}{+}{k}}\right){}{n}{!}\right){}{c}{!}{}{b}{!}{}\left(\genfrac{}{}{0}{}{{b}{+}{c}}{{b}{+}{k}}\right){}{\left({-1}\right)}^{{k}}{}\left({b}{+}{k}\right){}\left({n}{+}{1}{+}{k}\right){}\left({c}{+}{k}\right)}{{2}{}\left({n}{+}{b}{+}{c}\right){!}{}\left({n}{+}{1}{+}{b}{+}{c}\right){!}{}\left({b}{}{c}{}{n}{+}{b}{}{{k}}^{{2}}{+}{c}{}{{k}}^{{2}}{+}{{k}}^{{2}}{}{n}{+}{b}{}{c}{+}{{k}}^{{2}}\right)}$ (9)
 > $\mathrm{certificate}$
 $\frac{\left({b}{+}{k}\right){}\left({c}{+}{k}\right)}{{2}{}\left({n}{+}{1}{+}{b}{+}{c}\right){}\left({-}{n}{+}{k}{-}{1}\right)}$ (10)

References

 Wilf, H., and Zeilberger, D. "Rational function certify combinatorial identities." J. Amer. Math. Soc. Vol. 3. (1990): 147-158.

 See Also