 SumTools[Hypergeometric] - Maple Programming Help

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

SumTools[Hypergeometric]

 MinimalZpair
 compute the minimal Z-pair
 MinimalTelescoper
 compute the minimal telescoper

 Calling Sequence MinimalZpair(T, n, k, En) MinimalTelescoper(T, 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

Description

 • For a specified hypergeometric term $T\left(n,k\right)$ of n and k, MinimalZpair(T, n, k, En) constructs for $T\left(n,k\right)$ the minimal Z-pair $\left[L,G\right]$; MinimalTelescoper(T, n, k, En) constructs for $T\left(n,k\right)$ the minimal telescoper $L$.
 • L and G satisfy the following properties:
 1. $L$ is a linear recurrence operator in En with polynomial coefficients in n.
 2. $G$ is a hypergeometric term of n and k.
 3. $LT=\left(\mathrm{Ek}-1\right)G$, where $\mathrm{Ek}$ denotes the shift operator with respect to k.
 4. The order of L w.r.t. En is minimal.
 • The execution steps of MinimalZpair can be described as follows.
 1. Determine the applicability of Zeilberger's algorithm to $T\left(n,k\right)$.
 2. If it is proven in Step 1 that a Z-pair for $T\left(n,k\right)$ does not exist, return the conclusive error message Zeilberger's algorithm is not applicable''. Otherwise,
 a. If $T\left(n,k\right)$ is a rational function in n and k, apply the direct algorithm to compute the minimal Z-pair for $T\left(n,k\right)$.
 b. If $T\left(n,k\right)$ is a nonrational term, first compute a lower bound u for the order of the telescopers for $T\left(n,k\right)$. Then compute the minimal Z-pair using Zeilberger's algorithm with u as the starting value for the guessed orders.
 • For case 2b, since the term T2 in the additive decomposition $\mathrm{T1},\mathrm{T2}$ of T is simpler'' than T in some sense, we first apply Zeilberger's algorithm to T2 to obtain the minimal Z-pair $\left[L,G\right]$ for T2. It is easy to show that $\left[L,\mathrm{LT1}+G\right]$ is the minimal Z-pair for the input term T.

Examples

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

Case 1: Zeilberger's algorithm is not applicable to the input term T.

 > $T≔\frac{{\left(-1\right)}^{k}\cdot 1\mathrm{binomial}\left(n+1,k\right)\mathrm{binomial}\left(2n-2k-1,n-1\right)}{nk+1}$
 ${T}{≔}\frac{{\left({-1}\right)}^{{k}}{}\left(\genfrac{}{}{0}{}{{n}{+}{1}}{{k}}\right){}\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{2}{}{k}{-}{1}}{{n}{-}{1}}\right)}{{n}{}{k}{+}{1}}$ (1)
 > $\mathrm{MinimalZpair}\left(T,n,k,\mathrm{En}\right)$

Case 2a: Rational Function

 > $T≔\frac{1}{{\left(3n+20k+2\right)}^{3}}$
 ${T}{≔}\frac{{1}}{{\left({3}{}{n}{+}{20}{}{k}{+}{2}\right)}^{{3}}}$ (2)
 > $\mathrm{MinimalZpair}\left(T,n,k,\mathrm{En}\right)$
 $\left[{{\mathrm{En}}}^{{20}}{-}{1}{,}\frac{{1}}{{\left({3}{}{n}{+}{20}{}{k}{+}{42}\right)}^{{3}}}{+}\frac{{1}}{{\left({3}{}{n}{+}{20}{}{k}{+}{22}\right)}^{{3}}}{+}\frac{{1}}{{\left({3}{}{n}{+}{20}{}{k}{+}{2}\right)}^{{3}}}\right]$ (3)

Case 2b: Hypergeometric

 > $T≔\frac{1}{\left(n\left(k+1\right)-1\right)\left(n-2k-4\right)\left(2n+k+4\right)!}-\frac{1}{\left(nk-1\right)\left(n-2k-2\right)\left(2n+k+3\right)!}+\frac{1}{\left(n-2k-2\right)\left(2n+k+3\right)!}$
 ${T}{≔}\frac{{1}}{\left({n}{}\left({k}{+}{1}\right){-}{1}\right){}\left({n}{-}{2}{}{k}{-}{4}\right){}\left({2}{}{n}{+}{k}{+}{4}\right){!}}{-}\frac{{1}}{\left({n}{}{k}{-}{1}\right){}\left({n}{-}{2}{}{k}{-}{2}\right){}\left({2}{}{n}{+}{k}{+}{3}\right){!}}{+}\frac{{1}}{\left({n}{-}{2}{}{k}{-}{2}\right){}\left({2}{}{n}{+}{k}{+}{3}\right){!}}$ (4)
 > $\mathrm{Zpair}≔\mathrm{MinimalZpair}\left(T,n,k,\mathrm{En}\right):$
 > ${\mathrm{Zpair}}_{1}$
 $\left({-}{1953125}{}{{n}}^{{9}}{-}{44140625}{}{{n}}^{{8}}{-}{438125000}{}{{n}}^{{7}}{-}{2505718750}{}{{n}}^{{6}}{-}{9095640625}{}{{n}}^{{5}}{-}{21719685625}{}{{n}}^{{4}}{-}{34096450250}{}{{n}}^{{3}}{-}{33905768600}{}{{n}}^{{2}}{-}{19362572120}{}{n}{-}{4833216960}\right){}{{\mathrm{En}}}^{{3}}{+}\left({1953125}{}{{n}}^{{9}}{+}{42187500}{}{{n}}^{{8}}{+}{400625000}{}{{n}}^{{7}}{+}{2194468750}{}{{n}}^{{6}}{+}{7637609375}{}{{n}}^{{5}}{+}{17505613750}{}{{n}}^{{4}}{+}{26405971500}{}{{n}}^{{3}}{+}{25257742600}{}{{n}}^{{2}}{+}{13888257120}{}{n}{+}{3340995840}\right){}{{\mathrm{En}}}^{{2}}{+}\left({20000}{}{{n}}^{{4}}{+}{152000}{}{{n}}^{{3}}{+}{422400}{}{{n}}^{{2}}{+}{508160}{}{n}{+}{223232}\right){}{\mathrm{En}}{-}{20000}{}{{n}}^{{4}}{-}{232000}{}{{n}}^{{3}}{-}{998400}{}{{n}}^{{2}}{-}{1888960}{}{n}{-}{1325792}$ (5)
 > $T≔\frac{1}{{n}^{2}+9nk-4n-22{k}^{2}+21k-5}$
 ${T}{≔}\frac{{1}}{{-}{22}{}{{k}}^{{2}}{+}{9}{}{n}{}{k}{+}{{n}}^{{2}}{+}{21}{}{k}{-}{4}{}{n}{-}{5}}$ (6)
 > $\mathrm{MinimalTelescoper}\left(T,n,k,\mathrm{En}\right)$
 ${-}{13}{}{n}{-}{1}{+}\left({-}{14}{-}{13}{}{n}\right){}{\mathrm{En}}{+}\left({144}{+}{13}{}{n}\right){}{{\mathrm{En}}}^{{11}}{+}\left({157}{+}{13}{}{n}\right){}{{\mathrm{En}}}^{{12}}$ (7)

References

 Abramov, S.A.; Geddes, K.O.; and Le, H.Q. "Computer Algebra Library for the Construction of the Minimal Telescopers." Proceedings ICMS'2002, pp. 319- 329. World Scientific, 2002.