SumTools[Hypergeometric] - Maple Programming Help

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

SumTools[Hypergeometric]

 SumDecomposition
 construct the minimal additive decomposition of a hypergeometric term

 Calling Sequence SumDecomposition(T, n, k, newT, opts)

Parameters

 T - hypergeometric term of $n$ n - name k - (optional) name; the index variable to use in the output newT - (optional) name; will be assigned an equivalent expression for $T$ opts - (optional) equation(s) of the form keyword=value; possible keywords are minimize or maxiterations

Options

 • The following optional arguments can be used if $T$ is a rational function of $n$.
 • minimize=v, where v is either a numeric value between $0$ and $1$ or one of "numerator", "sum denominator", "combined", "left", "right".
 – If v="sum denominator", then the degree $g$ of the denominator of ${T}_{1}$ will be minimized.
 – If v="numerator", then the degree $e$ of the numerator of ${T}_{2}$ will be minimized.
 – If v="combined", then then the sum of the degrees $g+e$ will be  minimized.
 – If v is  a numeric constant between $0$ and $1$, then the weighted sum of the degrees $vg+\left(1-v\right)e$ will be minimized.
 Note that small values of v may lead to time-consuming search; the option maxiterations (see below) can be used to restrict it.
 – If v="left", then the remainder of the result will be aligned such that $\mathrm{gcd}\left(\mathrm{denom}\left({T}_{1}\right),\genfrac{}{}{0}{}{\mathrm{denom}\left({T}_{2}\right)}{\phantom{n=n+k}}|\genfrac{}{}{0}{}{\phantom{\mathrm{denom}\left({T}_{2}\right)}}{n=n+k}\right)=1$ for all integers $k<0$.
 – If v="right", then the remainder of the result will be aligned such that $\mathrm{gcd}\left(\mathrm{denom}\left({T}_{1}\right),\genfrac{}{}{0}{}{\mathrm{denom}\left({T}_{2}\right)}{\phantom{n=n+k}}|\genfrac{}{}{0}{}{\phantom{\mathrm{denom}\left({T}_{2}\right)}}{n=n+k}\right)=1$ for all integers $0\le k$.
 • maxiterations=integer
 This option can be used to restrict the number of iterations performed by the command when the option minimize=v is used with a small positive numeric value v. The default value is $10000$.

Description

 • The SumDecomposition(T, n, k) command constructs two hypergeometric terms ${T}_{1}$ and ${T}_{2}$ such that $T\left(n\right)={T}_{1}\left(n+1\right)-{T}_{1}\left(n\right)+{T}_{2}\left(n\right)$ and the certificate $\frac{E\left({T}_{2}\right)}{{T}_{2}}=\frac{{T}_{2}\left(n+1\right)}{{T}_{2}\left(n\right)}$ has a rational normal form $\left(z,r,s,u,v\right)$ with $v$ of minimal degree.
 • The output from SumDecomposition is a list of two elements $\left[{T}_{1},{T}_{2}\right]$. Both are represented in the form

${T}_{i}\left(n\right)=\frac{T\left({n}_{0}\right){z}^{n}F\left(n\right)\left({\prod }_{k={n}_{0}}^{n-1}\frac{r\left(k\right)}{s\left(k\right)}\right)}{{z}^{{n}_{0}}F\left({n}_{0}\right)}$

 for some integer $0\le {n}_{0}$. The form shown above is called a multiplicative decomposition of the hypergeometric term $T\left(n\right)$.
 • If the third optional argument k is not specified, the first unused name in the sequence $k,\mathrm{k0},\mathrm{k1},\mathrm{k2},\mathrm{...}$ is used.
 • If the fourth optional argument newT is specified, it will be assigned an expression in terms of inert Products of the same form as for ${T}_{i}$ above that is equivalent to $T$.
 • If $T$ is a rational function of $n$, then ${T}_{1}$ and ${T}_{2}$ will be rational functions as well, and the denominator of ${T}_{2}$ is of smallest possible degree. In that case, ${T}_{1}$ and ${T}_{2}$ are not unique, however, and you can use the minimize=v option to impose some additional conditions on ${T}_{1}$ and ${T}_{2}$ (see below).
 • Note: If you set infolevel[SumDecomposition] to $3$, Maple prints diagnostics.

Examples

 > $\mathrm{with}\left(\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\right):$
 > $T≔\frac{\left({n}^{2}-2n-1\right){2}^{n}}{\left(n+1\right){n}^{2}\left(n+3\right)!}$
 ${T}{≔}\frac{\left({{n}}^{{2}}{-}{2}{}{n}{-}{1}\right){}{{2}}^{{n}}}{\left({n}{+}{1}\right){}{{n}}^{{2}}{}\left({n}{+}{3}\right){!}}$ (1)

Set the infolevel to 3.

 > $\mathrm{infolevel}\left[\mathrm{SumDecomposition}\right]≔3:$
 > $\mathrm{SumDecomposition}\left(T,n,k,'\mathrm{newT}'\right)$
 SumDecomposition:   "calling dterm" SumDecomposition:   "construct the RCF_1 for the certificate of T" SumDecomposition:   "construct a regular description of T" SumDecomposition:   "calling dcert" SumDecomposition:   "using factorization method" SumDecomposition:   "construct a regular description of T1" SumDecomposition:   "construct a regular description of T2" SumDecomposition:   "T2 is not summable" SumDecomposition:   "An attempt to control the degree of the numerator" SumDecomposition:   "construct a triple that regularly describes T2"
 $\left[\frac{\left({n}{+}{3}\right){}\left({\prod }_{{k}{=}{1}}^{{n}{-}{1}}{}\frac{{2}}{{k}{+}{4}}\right)}{{12}{}{n}}{,}\frac{\left({{n}}^{{2}}{+}{2}{}{n}{-}{1}\right){}\left({\prod }_{{k}{=}{1}}^{{n}{-}{1}}{}\frac{{2}}{{k}{+}{4}}\right)}{{12}{}{{n}}^{{2}}}\right]$ (2)
 > $\mathrm{newT}$
 $\frac{\left({{n}}^{{2}}{-}{2}{}{n}{-}{1}\right){}\left({\prod }_{{k}{=}{1}}^{{n}{-}{1}}{}\frac{{2}}{{k}{+}{4}}\right)}{{12}{}{{n}}^{{2}}{}\left({n}{+}{1}\right)}$ (3)
 > $\mathrm{convert}\left(\mathrm{value}\left(\mathrm{newT}\right),'\mathrm{factorial}'\right)$
 $\frac{\left({{n}}^{{2}}{-}{2}{}{n}{-}{1}\right){}{{2}}^{{n}}}{\left({n}{+}{1}\right){}{{n}}^{{2}}{}\left({n}{+}{3}\right){!}}$ (4)
 > $T≔{n}^{3}{2}^{n}$
 ${T}{≔}{{n}}^{{3}}{}{{2}}^{{n}}$ (5)
 > $\mathrm{infolevel}\left[\mathrm{SumDecomposition}\right]≔0:$
 > $\mathrm{SumDecomposition}\left(T,n,k\right)$
 $\left[\frac{\left({2}{}{{n}}^{{3}}{-}{12}{}{{n}}^{{2}}{+}{36}{}{n}{-}{52}\right){}{{2}}^{{n}}}{{2}}{,}{0}\right]$ (6)

The above result shows that the input hypergeometric term T is summable.

 > $T≔-\frac{2\left(925+190n+19{n}^{2}+606{n}^{3}+72{n}^{5}+435{n}^{4}+3{n}^{6}\right)}{\left(n+5\right)\left({n}^{2}+12n+37\right)\left({n}^{3}+2\right)\left(n-1\right)n}$
 ${T}{≔}{-}\frac{{2}{}\left({3}{}{{n}}^{{6}}{+}{72}{}{{n}}^{{5}}{+}{435}{}{{n}}^{{4}}{+}{606}{}{{n}}^{{3}}{+}{19}{}{{n}}^{{2}}{+}{190}{}{n}{+}{925}\right)}{\left({n}{+}{5}\right){}\left({{n}}^{{2}}{+}{12}{}{n}{+}{37}\right){}\left({{n}}^{{3}}{+}{2}\right){}\left({n}{-}{1}\right){}{n}}$ (7)
 > $\mathrm{SumDecomposition}\left(T,n\right)$
 $\left[\frac{{10}}{{n}{-}{1}}{+}\frac{{5}}{{n}}{+}\frac{{5}}{{n}{+}{1}}{+}\frac{{5}}{{n}{+}{2}}{+}\frac{{5}}{{n}{+}{3}}{+}\frac{{5}}{{n}{+}{4}}{,}\frac{{5}}{{n}{-}{1}}{+}\frac{{-}{4}{}{n}{-}{22}}{{{n}}^{{2}}{+}{12}{}{n}{+}{37}}{+}\frac{{-}{{n}}^{{2}}{-}{2}{}{n}{-}{4}}{{{n}}^{{3}}{+}{2}}\right]$ (8)
 > $\mathrm{SumDecomposition}\left(T,n,'\mathrm{minimize}'="numerator"\right)$
 $\left[\frac{{5}}{{n}{-}{1}}{+}\frac{{5}}{{n}}{+}\frac{{5}}{{n}{+}{1}}{+}\frac{{5}}{{n}{+}{2}}{+}\frac{{5}}{{n}{+}{3}}{+}\frac{{5}}{{n}{+}{4}}{+}\frac{{-}{4}{}{n}{+}{2}}{{\left({n}{-}{6}\right)}^{{2}}{+}{12}{}{n}{-}{35}}{+}\frac{{-}{4}{}{n}{-}{2}}{{\left({n}{-}{5}\right)}^{{2}}{+}{12}{}{n}{-}{23}}{+}\frac{{-}{4}{}{n}{-}{6}}{{\left({n}{-}{4}\right)}^{{2}}{+}{12}{}{n}{-}{11}}{+}\frac{{-}{4}{}{n}{-}{10}}{{\left({n}{-}{3}\right)}^{{2}}{+}{12}{}{n}{+}{1}}{+}\frac{{-}{4}{}{n}{-}{14}}{{\left({n}{-}{2}\right)}^{{2}}{+}{12}{}{n}{+}{13}}{+}\frac{{-}{4}{}{n}{-}{18}}{{\left({n}{-}{1}\right)}^{{2}}{+}{12}{}{n}{+}{25}}{,}\frac{{5}}{{n}}{+}\frac{{-}{4}{}{n}{+}{2}}{{\left({n}{-}{6}\right)}^{{2}}{+}{12}{}{n}{-}{35}}{+}\frac{{-}{{n}}^{{2}}{-}{2}{}{n}{-}{4}}{{{n}}^{{3}}{+}{2}}\right]$ (9)
 > $\mathrm{SumDecomposition}\left(T,n,'\mathrm{minimize}'=\frac{1}{5}\right)$
 $\left[\frac{{5}}{{n}{-}{1}}{+}\frac{{5}}{{n}{+}{4}}{+}\frac{{-}{4}{}{n}{-}{18}}{{\left({n}{-}{1}\right)}^{{2}}{+}{12}{}{n}{+}{25}}{,}\frac{{-}{4}{}{n}{-}{18}}{{\left({n}{-}{1}\right)}^{{2}}{+}{12}{}{n}{+}{25}}{+}\frac{{5}}{{n}{+}{4}}{+}\frac{{-}{{n}}^{{2}}{-}{2}{}{n}{-}{4}}{{{n}}^{{3}}{+}{2}}\right]$ (10)
 > $\mathrm{SumDecomposition}\left(T,n,'\mathrm{minimize}'="sum denominator"\right)$
 $\left[\frac{{5}}{{n}{-}{1}}{,}\frac{{5}}{{n}{+}{5}}{+}\frac{{-}{4}{}{n}{-}{22}}{{{n}}^{{2}}{+}{12}{}{n}{+}{37}}{+}\frac{{-}{{n}}^{{2}}{-}{2}{}{n}{-}{4}}{{{n}}^{{3}}{+}{2}}\right]$ (11)
 > $T≔\frac{1}{n-1}-\frac{3\left({n}^{2}+1\right)}{{n}^{3}}+\frac{n}{{\left(n+1\right)}^{2}}$
 ${T}{≔}\frac{{1}}{{n}{-}{1}}{-}\frac{{3}{}\left({{n}}^{{2}}{+}{1}\right)}{{{n}}^{{3}}}{+}\frac{{n}}{{\left({n}{+}{1}\right)}^{{2}}}$ (12)
 > $\mathrm{SumDecomposition}\left(T,n\right)$
 $\left[\frac{{n}{-}{1}}{{{n}}^{{2}}}{-}\frac{{1}}{{n}{-}{1}}{,}{-}\frac{{{n}}^{{2}}{+}{n}{+}{3}}{{{n}}^{{3}}}\right]$ (13)
 > $\mathrm{SumDecomposition}\left(T,n,'\mathrm{minimize}'="left"\right)$
 $\left[\frac{{-}{2}{}{\left({n}{-}{1}\right)}^{{2}}{-}{n}{-}{2}}{{\left({n}{-}{1}\right)}^{{3}}}{+}\frac{{n}{-}{1}}{{{n}}^{{2}}}{,}{-}\frac{{{n}}^{{2}}{-}{n}{+}{3}}{{\left({n}{-}{1}\right)}^{{3}}}\right]$ (14)
 > $\mathrm{SumDecomposition}\left(T,n,'\mathrm{minimize}'="right"\right)$
 $\left[{-}\frac{{-}{2}{}{{n}}^{{2}}{-}{3}}{{{n}}^{{3}}}{-}\frac{{1}}{{n}{-}{1}}{,}{-}\frac{{{n}}^{{2}}{+}{3}{}{n}{+}{5}}{{\left({n}{+}{1}\right)}^{{3}}}\right]$ (15)

References

 Abramov, S.A. "Indefinite Sums of Rational Functions." Proceedings ISSAC'95, pp. 303-308. 1995.
 Abramov, S.A., and Petkovsek, M. "Minimal Decomposition of Indefinite Hypergeometric Sums." Proceedings ISSAC'2001, pp. 7-14. 2001.
 Abramov, S.A., and Petkovsek, M. "Rational Normal Forms and Minimal Decompositions of Hypergeometric Terms." Journal of Symbolic Computation. Vol. 33 No. 5. (2002): 521-543.
 Polyakov, S.P. "Symbolic Additive Decomposition of Rational Functions." Programming and Computer Software, Vol. 31 No. 2. (2005): 60-64.
 Polyakov, S.P. "Indefinite Summation of Rational Functions with Additional Minimization of the Summable Part." Programming and Computer Software 34 No. 2, (2008): 95-100.