BottomSequence - Maple Help

SumTools[Hypergeometric]

 BottomSequence
 bottom sequence of a hypergeometric term

 Calling Sequence BottomSequence(T, x, opt)

Parameters

 T - hypergeometric term in x x - name opt - (optional) equation of the form primitive=true or primitive=false

Description

 • Consider $T$ as an analytic function in $x$ satisfying a linear difference equation $p\left(x\right)T\left(x+1\right)+q\left(x\right)T\left(x\right)=0$, where $p\left(x\right)$ and $q\left(x\right)$ are polynomials in $x$. For $h\in ℤ$ and any integer $k$, let ${c}_{k,h}$ be the $h$-th coefficient of the Laurent series expansion for $T$ at $x=k$. An integer $m$ is called depth of $T$ if ${c}_{k,h}=0$ for all $h and all integers $k$, and ${c}_{k,m}\ne 0$ for some $k\in ℤ$.
 • The bottom sequence of $T$ is the doubly infinite sequence ${b}_{x}$ defined as ${b}_{x}={c}_{x,m}$ for all integers $x$, where $m$ is the depth of $T$. The command BottomSequence(T, x) returns the bottom sequence of $T$ in form of an expression representing a function of (integer values of) $x$. Typically, this is a piecewise expression.
 • The bottom sequence ${b}_{x}$ is defined at all integers $x$ and satisfies the same difference equation $p\left(x\right){b}_{x+1}+q\left(x\right){b}_{x}=0$ as $T$.
 • If $T$ is Gosper-summable and $S=vT$ is its indefinite sum found by Gosper's algorithm, then the depth of $S$ is also $m$. If the optional argument primitive=true (or just primitive) is specified, the command returns a pair $v,u$, where $v$ is the bottom sequence of $T$ and $u$ is the bottom sequence of $S$ or FAIL if $T$ is not Gosper-summable.
 • Note that this command rewrites expressions of the form $\left(\genfrac{}{}{0}{}{n}{k}\right)$ in terms of GAMMA functions $\frac{\mathrm{\Gamma }\left(n+1\right)}{\mathrm{\Gamma }\left(k+1\right)\mathrm{\Gamma }\left(n-k+1\right)}$.
 • If assumptions of the form ${x}_{0} and/or $x<{x}_{1}$ are made, the depth and the bottom of $T$ are computed with respect to the given interval instead of $-\mathrm{\infty }..\mathrm{\infty }$.

Examples

 > $\mathrm{with}\left(\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\right):$
 > $T≔nn!$
 ${T}{≔}{n}{}{n}{!}$ (1)
 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)$
 ${b}{,}{s}{≔}\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}}{}{n}}{{\mathrm{\Gamma }}{}\left({-}{n}\right)}& {n}{\le }{-1}\\ {0}& {0}{\le }{n}\end{array}\right\{,}\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}}}{{\mathrm{\Gamma }}{}\left({-}{n}\right)}& {n}{\le }{-1}\\ {0}& {0}{\le }{n}\end{array}\right\$ (2)

Note that $b$ is not equivalent to $T$:

 > $\mathrm{eval}\left(b,n=1\right)$
 ${0}$ (3)
 > $\mathrm{eval}\left(T,n=1\right)$
 ${1}$ (4)
 > $\mathrm{eval}\left(b,n=-1\right)$
 ${-1}$ (5)
 > $\mathrm{eval}\left(T,n=-1\right)$

However, $b$ satisfies the same difference equation as $T$:

 > $\mathrm{expand}\left(n\left(\mathrm{eval}\left(T,n=n+1\right)\right)-{\left(n+1\right)}^{2}T\right)$
 ${0}$ (6)
 > $z≔n\left(\mathrm{eval}\left(b,n=n+1\right)\right)-{\left(n+1\right)}^{2}b$
 ${z}{≔}{n}{}\left(\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}{+}{1}}{}\left({n}{+}{1}\right)}{{\mathrm{\Gamma }}{}\left({-}{1}{-}{n}\right)}& {n}{\le }{-2}\\ {0}& {0}{\le }{n}{+}{1}\end{array}\right\\right){-}{\left({n}{+}{1}\right)}^{{2}}{}\left(\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}}{}{n}}{{\mathrm{\Gamma }}{}\left({-}{n}\right)}& {n}{\le }{-1}\\ {0}& {0}{\le }{n}\end{array}\right\\right)$ (7)
 > $\mathrm{simplify}\left(z\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n\le -2$
 ${0}$ (8)
 > $\mathrm{simplify}\left(z\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\le n$
 ${0}$ (9)
 > $\mathrm{eval}\left(z,n=-1\right)$
 ${0}$ (10)

$s$ is an indefinite sum of $b$:

 > $z≔\mathrm{eval}\left(s,n=n+1\right)-s-b$
 ${z}{≔}\left(\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}{+}{1}}}{{\mathrm{\Gamma }}{}\left({-}{1}{-}{n}\right)}& {n}{\le }{-2}\\ {0}& {0}{\le }{n}{+}{1}\end{array}\right\\right){-}\left(\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}}}{{\mathrm{\Gamma }}{}\left({-}{n}\right)}& {n}{\le }{-1}\\ {0}& {0}{\le }{n}\end{array}\right\\right){-}\left(\left\{\begin{array}{cc}{-}\frac{{\left({-1}\right)}^{{n}}{}{n}}{{\mathrm{\Gamma }}{}\left({-}{n}\right)}& {n}{\le }{-1}\\ {0}& {0}{\le }{n}\end{array}\right\\right)$ (11)
 > $\mathrm{simplify}\left(z\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n\le -2$
 ${0}$ (12)
 > $\mathrm{simplify}\left(z\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\le n$
 ${0}$ (13)
 > $\mathrm{eval}\left(z,n=-1\right)$
 ${0}$ (14)

Now assume that $0\le n$:

 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\le n$
 ${b}{,}{s}{≔}{n}{}{\mathrm{\Gamma }}{}\left({n}{+}{1}\right){,}{\mathrm{\Gamma }}{}\left({n}{+}{1}\right)$ (15)

With that assumption, $b$ and $T$ are equivalent, and $s$ is an indefinite sum of both:

 > $\mathrm{simplify}\left(b-T\right)$
 ${0}$ (16)
 > $\mathrm{simplify}\left(\mathrm{eval}\left(s,n=n+1\right)-s-b\right)$
 ${0}$ (17)

Example of a hypergeometric term with parameters:

 > $T≔\frac{\mathrm{\Gamma }\left(-n\right)}{n-k}$
 ${T}{≔}\frac{{\mathrm{\Gamma }}{}\left({-}{n}\right)}{{n}{-}{k}}$ (18)
 > $\mathrm{BottomSequence}\left(T,n\right)$
 $\left\{\begin{array}{cc}{0}& {n}{\le }{-1}\\ \frac{{\left({-1}\right)}^{{n}}}{\left({-}{n}{+}{k}\right){}{\mathrm{\Gamma }}{}\left({n}{+}{1}\right)}& {0}{\le }{n}\end{array}\right\$ (19)

Note that $k$ is considered non-integer.

 > $\mathrm{BottomSequence}\left(T,n\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{assuming}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}k::'\mathrm{nonnegint}'$
 $\left\{\begin{array}{cc}{0}& {n}{\le }{-1}\\ \frac{{\left({-1}\right)}^{{n}}}{\left({-}{n}{+}{k}\right){}{\mathrm{\Gamma }}{}\left({n}{+}{1}\right)}& {0}{\le }{n}\end{array}\right\$ (20)
 > $\mathrm{BottomSequence}\left(\mathrm{eval}\left(T,k=2\right),n\right)$
 $\left\{\begin{array}{cc}{0}& {n}{\le }{1}\\ {-}\frac{{1}}{{2}}& {n}{=}{2}\\ {0}& {3}{\le }{n}\end{array}\right\$ (21)
 > $T≔\frac{\mathrm{binomial}\left(2n-3,n\right)}{{4}^{n}}$
 ${T}{≔}\frac{\left(\genfrac{}{}{0}{}{{2}{}{n}{-}{3}}{{n}}\right)}{{{4}}^{{n}}}$ (22)
 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)$
 ${b}{,}{s}{≔}\left\{\begin{array}{cc}{0}& {n}{\le }{-1}\\ \frac{{1}}{{2}}& {n}{=}{0}\\ {-}\frac{{1}}{{8}}& {n}{=}{1}\\ \frac{{{4}}^{{-}{n}}{}\left({n}{-}{2}\right){}{\mathrm{\Gamma }}{}\left({2}{}{n}{-}{1}\right)}{{2}{}{{\mathrm{\Gamma }}{}\left({n}\right)}^{{2}}{}{n}}& {2}{\le }{n}\end{array}\right\{,}\left\{\begin{array}{cc}{0}& {n}{\le }{0}\\ \frac{{1}}{{2}}& {n}{=}{1}\\ \frac{{{4}}^{{-}{n}}{}\left({n}{+}{1}\right){}{\mathrm{\Gamma }}{}\left({2}{}{n}{-}{1}\right)}{{{\mathrm{\Gamma }}{}\left({n}\right)}^{{2}}}& {2}{\le }{n}\end{array}\right\$ (23)

References

 S.A. Abramov, M. Petkovsek. "Analytic solutions of linear difference equations, formal series, and bottom summation." Proc. of CASC'07, (2007): 1-10.
 S.A. Abramov, M. Petkovsek. "Gosper's Algorithm, Accurate Summation, and the Discrete Newton-Leibniz Formula." Proceedings of ISSAC'05, (2005): 5-12.

Compatibility

 • The SumTools[Hypergeometric][BottomSequence] command was introduced in Maple 15.