SumTools[Hypergeometric] - Maple Help

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

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\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}ℤ$ 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\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}ℤ$.
 • 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 $\mathrm{binomial}\left(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}[\mathrm{Hypergeometric}]\right):$
 > $T≔nn!$
 ${T}{:=}{n}{}{n}{!}$ (1)
 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)$
 ${b}{,}{s}{:=}{{}\begin{array}{cc}{-}\frac{{n}{}{\left({-}{1}\right)}^{{n}}}{{\mathrm{Γ}}{}\left({-}{n}\right)}& {n}{\le }{-}{1}\\ {0}& {0}{\le }{n}\end{array}{,}{{}\begin{array}{cc}{-}\frac{{\left({-}{1}\right)}^{{n}}}{{\mathrm{Γ}}{}\left({-}{n}\right)}& {n}{\le }{-}{1}\\ {0}& {0}{\le }{n}\end{array}$ (2)

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

 > $\genfrac{}{}{0}{}{b}{\phantom{n=1}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{b}}{n=1}$
 ${0}$ (3)
 > $\genfrac{}{}{0}{}{T}{\phantom{n=1}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{T}}{n=1}$
 ${1}$ (4)
 > $\genfrac{}{}{0}{}{b}{\phantom{n=-1}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{b}}{n=-1}$
 ${-}{1}$ (5)
 > $\genfrac{}{}{0}{}{T}{\phantom{n=-1}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{T}}{n=-1}$

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

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

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

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

Now assume that $0\le n$:

 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}assuming\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}0\le n$
 ${b}{,}{s}{:=}{n}{}{\mathrm{Γ}}{}\left({n}{+}{1}\right){,}{\mathrm{Γ}}{}\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(\genfrac{}{}{0}{}{s}{\phantom{n=n+1}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{s}}{n=n+1}-s-b\right)$
 ${0}$ (17)

Example of a hypergeometric term with parameters:

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

Note that $k$ is considered non-integer.

 > $\mathrm{BottomSequence}\left(T,n\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}assuming\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}k::\mathrm{nonnegint}$
 Warning, the assumptions about variable(s) k are ignored
 ${{}\begin{array}{cc}{0}& {n}{\le }{-}{1}\\ \frac{{\left({-}{1}\right)}^{{n}}}{\left({-}{n}{+}{k}\right){}{\mathrm{Γ}}{}\left({n}{+}{1}\right)}& {0}{\le }{n}\end{array}$ (20)
 > $\mathrm{BottomSequence}\left(\genfrac{}{}{0}{}{T}{\phantom{k=2}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{T}}{k=2},n\right)$
 ${{}\begin{array}{cc}{0}& {n}{\le }{1}\\ {-}\frac{{1}}{{2}}& {n}{=}{2}\\ {0}& {3}{\le }{n}\end{array}$ (21)
 > $T≔\frac{\mathrm{binomial}\left(2n-3,n\right)}{{4}^{n}}$
 ${T}{:=}\frac{{\mathrm{binomial}}{}\left({2}{}{n}{-}{3}{,}{n}\right)}{{{4}}^{{n}}}$ (22)
 > $b,s≔\mathrm{BottomSequence}\left(T,n,'\mathrm{primitive}'\right)$
 ${b}{,}{s}{:=}{{}\begin{array}{cc}{0}& {n}{\le }{-}{1}\\ \frac{{1}}{{2}}& {n}{=}{0}\\ {-}\frac{{1}}{{8}}& {n}{=}{1}\\ \frac{{1}}{{2}}{}\frac{{{4}}^{{-}{n}}{}\left({n}{-}{2}\right){}{\mathrm{Γ}}{}\left({2}{}{n}{-}{1}\right)}{{{\mathrm{Γ}}{}\left({n}\right)}^{{2}}{}{n}}& {2}{\le }{n}\end{array}{,}{{}\begin{array}{cc}{0}& {n}{\le }{0}\\ \frac{{1}}{{2}}& {n}{=}{1}\\ \frac{{{4}}^{{-}{n}}{}\left({n}{+}{1}\right){}{\mathrm{Γ}}{}\left({2}{}{n}{-}{1}\right)}{{{\mathrm{Γ}}{}\left({n}\right)}^{{2}}}& {2}{\le }{n}\end{array}$ (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.