SumTools[IndefiniteSum] - Maple Programming Help

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

SumTools[IndefiniteSum]

 Hypergeometric
 compute closed forms of indefinite sums of hypergeometric terms

 Calling Sequence Hypergeometric(f, k, opt)

Parameters

 f - hypergeometric term in k k - name opt - (optional) equation of the form failpoints=true or failpoints=false

Description

 • The Hypergeometric(f, k) command computes a closed form of the indefinite sum of $f$ with respect to $k$.
 • The following algorithms are used to handle indefinite sums of hypergeometric terms (see the References section):
 – Gosper's algorithm,
 – Koepf's extension to Gosper's algorithm, and
 – the algorithm to compute additive decompositions of hypergeometric terms developed by Abramov and Petkovsek.
 • If the option failpoints=true (or just failpoints for short) is specified, then the command returns a pair $s,\left[p,q\right]$, where $s$ is the closed form of the indefinite sum of $f$ w.r.t. $k$, as above, and $p,q$ are lists of points where $f$ does not exist or the computed sum $s$ is undefined or improper, respectively (see SumTools[IndefiniteSum][Indefinite] for more detailed help).
 • The command returns $\mathrm{FAIL}$ if it is not able to compute a closed form.

Examples

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

Gosper's algorithm:

 > $f≔\frac{\left(4n-1\right){\mathrm{binomial}\left(2n,n\right)}^{2}}{{\left(2n-1\right)}^{2}{4}^{2n}}$
 ${f}{≔}\frac{\left({4}{}{n}{-}{1}\right){}{\left(\genfrac{}{}{0}{}{{2}{}{n}}{{n}}\right)}^{{2}}}{{\left({2}{}{n}{-}{1}\right)}^{{2}}{}{{4}}^{{2}{}{n}}}$ (1)
 > $\mathrm{Hypergeometric}\left(f,n\right)$
 ${-}\frac{{4}{}{\left(\genfrac{}{}{0}{}{{2}{}{n}}{{n}}\right)}^{{2}}{}{{n}}^{{2}}}{{\left({2}{}{n}{-}{1}\right)}^{{2}}{}{{4}}^{{2}{}{n}}}$ (2)

The points where the telescoping equation fails:

 > $f≔\frac{\mathrm{binomial}\left(2n-3,n\right)}{{4}^{n}}$
 ${f}{≔}\frac{\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{3}}{{n}}\right)}{{{4}}^{{n}}}$ (3)
 > $s,\mathrm{fp}≔\mathrm{Hypergeometric}\left(f,n,'\mathrm{failpoints}'\right)$
 ${s}{,}{\mathrm{fp}}{≔}\frac{{2}{}{n}{}\left({n}{+}{1}\right){}\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{3}}{{n}}\right)}{\left({n}{-}{2}\right){}{{4}}^{{n}}}{,}\left[\left[\right]{,}\left[{2}\right]\right]$ (4)
 > $\mathrm{eval}\left(s,n=2\right)$

Koepf's extension to Gosper's algorithm:

 > $f≔{\mathrm{binomial}\left(m,j\right)}^{2}{\mathrm{binomial}\left(m,k\right)}^{2}\mathrm{binomial}\left(2m+\frac{n}{3}-j-k,2m\right)$
 ${f}{≔}{\left(\genfrac{}{}{0}{}{{m}}{{j}}\right)}^{{2}}{}{\left(\genfrac{}{}{0}{}{{m}}{{k}}\right)}^{{2}}{}\left(\genfrac{}{}{0}{}{{2}{}{m}{+}\frac{{n}}{{3}}{-}{j}{-}{k}}{{2}{}{m}}\right)$ (5)
 > $\mathrm{Hypergeometric}\left(f,n\right)$
 $\frac{\left(\frac{{n}}{{3}}{-}{j}{-}{k}\right){}{\left(\genfrac{}{}{0}{}{{m}}{{j}}\right)}^{{2}}{}{\left(\genfrac{}{}{0}{}{{m}}{{k}}\right)}^{{2}}{}\left(\genfrac{}{}{0}{}{{2}{}{m}{+}\frac{{n}}{{3}}{-}{j}{-}{k}}{{2}{}{m}}\right)}{{2}{}{m}{+}{1}}{+}\frac{\left(\frac{{n}}{{3}}{-}{j}{-}{k}{+}\frac{{1}}{{3}}\right){}{\left(\genfrac{}{}{0}{}{{m}}{{j}}\right)}^{{2}}{}{\left(\genfrac{}{}{0}{}{{m}}{{k}}\right)}^{{2}}{}\left(\genfrac{}{}{0}{}{{2}{}{m}{+}\frac{{n}}{{3}}{+}\frac{{1}}{{3}}{-}{j}{-}{k}}{{2}{}{m}}\right)}{{2}{}{m}{+}{1}}{+}\frac{\left(\frac{{n}}{{3}}{+}\frac{{2}}{{3}}{-}{j}{-}{k}\right){}{\left(\genfrac{}{}{0}{}{{m}}{{j}}\right)}^{{2}}{}{\left(\genfrac{}{}{0}{}{{m}}{{k}}\right)}^{{2}}{}\left(\genfrac{}{}{0}{}{{2}{}{m}{+}\frac{{n}}{{3}}{+}\frac{{2}}{{3}}{-}{j}{-}{k}}{{2}{}{m}}\right)}{{2}{}{m}{+}{1}}$ (6)

Abramov and Petkovsek's algorithm (note that the specified summand is not hypergeometrically summable):

 > $f≔\frac{\left({n}^{2}-2n-1\right){2}^{n}}{\left(n+1\right){n}^{2}\left(n+3\right)!}$
 ${f}{≔}\frac{\left({{n}}^{{2}}{-}{2}{}{n}{-}{1}\right){}{{2}}^{{n}}}{\left({n}{+}{1}\right){}{{n}}^{{2}}{}\left({n}{+}{3}\right){!}}$ (7)
 > $\mathrm{Hypergeometric}\left(f,n\right)$
 $\frac{\left({n}{+}{3}\right){}\left({\prod }_{{\mathrm{_i}}{=}{1}}^{{n}{-}{1}}{}\frac{{2}}{{\mathrm{_i}}{+}{4}}\right)}{{12}{}{n}}{+}\left({\sum }_{{n}}{}\frac{\left({{n}}^{{2}}{+}{2}{}{n}{-}{1}\right){}\left({\prod }_{{\mathrm{_i}}{=}{1}}^{{n}{-}{1}}{}\frac{{2}}{{\mathrm{_i}}{+}{4}}\right)}{{12}{}{{n}}^{{2}}}\right)$ (8)
 > $\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\left[\mathrm{Gosper}\right]\left(f,n\right)$

References

 • Abramov, S.A., and Petkovsek, M. "Rational Normal Forms and Minimal Decompositions of Hypergeometric Terms." Journal of Symbolic Computing. Vol. 33. (2002): 521-543.
 • Gosper, R.W., Jr. "Decision Procedure for Indefinite Hypergeometric Summation." Proceedings of the National Academy of Sciences USA. Vol. 75. (1978): 40-42.
 • Koepf, W. Hypergeometric Summation: An Algorithmic Approach to Summation and Special Function Identities. Braunschweig, Germany: Vieweg, 1998.
 • Abramov, S.A. and Petkovsek, M. "Gosper's Algorithm, Accurate Summation, and the discrete Newton-Leibniz formula." Proceedings ISSAC'05. (2005): 5-12.