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 \mathbb{Z}$ 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<m$ and all integers $k$, and $c_{k,m}\ne 0$ for some $k\in \mathbb{Z}$.

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{}{}{0ex}{}{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<x$ 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 }$.

$\mathrm{with}\left(\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\right)\&colon;$

$T≔nn!$

$T≔nn!$

$b,s≔\mathrm{BottomSequence}\left(T\&comma;n\&comma;'\mathrm{primitive}'\right)$

$b,s≔\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^{n}n}{\mathrm{\Gamma }\left(-n\right)}& n\le \mathrm{-1}\\ 0& 0\le n\end{array}\right.,\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^n}{\mathrm{\Gamma }\left(-n\right)}& n\le \mathrm{-1}\\ 0& 0\le n\end{array}\right.$

$\mathrm{eval}\left(b\&comma;n=1\right)$

$0$

$\mathrm{eval}\left(T\&comma;n=1\right)$

$1$

$\mathrm{eval}\left(b\&comma;n=-1\right)$

$\mathrm{-1}$

$\mathrm{eval}\left(T\&comma;n=-1\right)$

Error, numeric exception: division by zero

$\mathrm{expand}\left(n\left(\mathrm{eval}\left(T\&comma;n=n+1\right)\right)-{\left(n+1\right)}^{2}T\right)$

$0$

$z≔n\left(\mathrm{eval}\left(b\&comma;n=n+1\right)\right)-{\left(n+1\right)}^{2}b$

$z≔n\left(\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^{n+1}\left(n+1\right)}{\mathrm{\Gamma }\left(-n-1\right)}& n\le \mathrm{-2}\\ 0& 0\le n+1\end{array}\right.\right)-{\left(n+1\right)}^2\left(\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^{n}n}{\mathrm{\Gamma }\left(-n\right)}& n\le \mathrm{-1}\\ 0& 0\le n\end{array}\right.\right)$

$\mathrm{simplify}\left(z\right)\mathbf{assuming}n\le -2$

$0$

$\mathrm{simplify}\left(z\right)\mathbf{assuming}0\le n$

$0$

$\mathrm{eval}\left(z\&comma;n=-1\right)$

$0$

$z≔\mathrm{eval}\left(s\&comma;n=n+1\right)-s-b$

$z≔\left(\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^{n+1}}{\mathrm{\Gamma }\left(-n-1\right)}& n\le \mathrm{-2}\\ 0& 0\le n+1\end{array}\right.\right)-\left(\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^n}{\mathrm{\Gamma }\left(-n\right)}& n\le \mathrm{-1}\\ 0& 0\le n\end{array}\right.\right)-\left(\left\{\begin{array}{cc}-\frac{{\left(\mathrm{-1}\right)}^{n}n}{\mathrm{\Gamma }\left(-n\right)}& n\le \mathrm{-1}\\ 0& 0\le n\end{array}\right.\right)$

$\mathrm{simplify}\left(z\right)\mathbf{assuming}n\le -2$

$0$

$\mathrm{simplify}\left(z\right)\mathbf{assuming}0\le n$

$0$

$\mathrm{eval}\left(z\&comma;n=-1\right)$

$0$

$b,s≔\mathrm{BottomSequence}\left(T\&comma;n\&comma;'\mathrm{primitive}'\right)\mathbf{assuming}0\le n$

$b,s≔n\mathrm{\Gamma }\left(n+1\right),\mathrm{\Gamma }\left(n+1\right)$

$\mathrm{simplify}\left(b-T\right)$

$0$

$\mathrm{simplify}\left(\mathrm{eval}\left(s\&comma;n=n+1\right)-s-b\right)$

$0$

$T≔\frac{\mathrm{\Gamma }\left(-n\right)}{n-k}$

$T≔\frac{\mathrm{\Gamma }\left(-n\right)}{n-k}$

$\mathrm{BottomSequence}\left(T\&comma;n\right)$

$\left\{\begin{array}{cc}0& n\le \mathrm{-1}\\ \frac{{\left(\mathrm{-1}\right)}^n}{\left(-n+k\right)\mathrm{\Gamma }\left(n+1\right)}& 0\le n\end{array}\right.$

$\mathrm{BottomSequence}\left(T\&comma;n\right)\mathbf{assuming}k::\mathrm{nonnegint}$

$\left\{\begin{array}{cc}0& n\le \mathrm{-1}\\ \frac{{\left(\mathrm{-1}\right)}^n}{\left(-n+k\right)\mathrm{\Gamma }\left(n+1\right)}& 0\le n\end{array}\right.$

$\mathrm{BottomSequence}\left(\mathrm{eval}\left(T\&comma;k=2\right)\&comma;n\right)$

$\left\{\begin{array}{cc}0& n\le 1\\ -\frac{1}{2}& n=2\\ 0& 3\le n\end{array}\right.$

$T≔\frac{\mathrm{binomial}\left(2n-3\&comma;n\right)}{4^n}$

$T≔\frac{\left(\genfrac{}{}{0ex}{}{2n-3}{n}\right)}{4^n}$

$b,s≔\mathrm{BottomSequence}\left(T\&comma;n\&comma;'\mathrm{primitive}'\right)$

$b,s≔\left\{\begin{array}{cc}0& n\le \mathrm{-1}\\ \frac{1}{2}& n=0\\ -\frac{1}{8}& n=1\\ \frac{4^{-n}\left(n-2\right)\mathrm{\Gamma }\left(2n-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(2n-1\right)}{{\mathrm{\Gamma }\left(n\right)}^2}& 2\le n\end{array}\right.$

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.

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

For more information on Maple 15 changes, see Updates in Maple 15.