\documentstyle[11pt, amsfonts, reduce, alltt]{article}
\title{{\tt QSUM}\\A Package for the Indefinite\\ and Definite Summation\\
of \textsl{q}-hypergeometric Terms}
\date{}
\author{Harald B\"oing\\
Wolfram Koepf\\
\\
Konrad Zuse Zentrum f\"ur Informationstechnik Berlin \\
Takustr.\ 7 \\
D-14195 Berlin-Dahlem \\
\\
email: {\tt koepf@zib.de}
}
%%\input{amssym.def}
\newcommand{\N} {\Bbb N}
\newcommand{\Z}{\Bbb Z}
\newcommand{\funkdef}[3]{\left\{\!\!\!\begin{array}{cc}
#1 & \!\!\!\mbox{\rm{if} $#2$ } \\
#3 & \!\!\!\mbox{\rm{otherwise}}
\end{array}
\right.}
\newcommand{\funkdefff}[6]{\left\{\begin{array}{ccc}
#1 && \mbox{{if} $#2$ } \\
#3 && \mbox{{if} $#4$ } \\
#5 && \mbox{{if} $#6$ }
\end{array}
\right.}
\newcommand{\qphihyp}[5]{{}_{#1}\phi_{#2}\left.\left[\begin{array}{c}
#3 \\ #4 \end{array}\right|q,#5\right]}
\newcommand{\qpsihyp}[5]{{}_{#1}\psi_{#2}\left.\left[\begin{array}{c}
#3 \\ #4 \end{array}\right|q,#5\right]}
\newcommand{\hyp}[5]{{}_{#1}F_{#2}\left.\left[\begin{array}{c}
#3 \\ #4 \end{array}\right|#5\right]}
\newcommand{\fcn}[2]{{\mathrm #1}(#2)}
\newcommand{\ifcn}[3]{{\mathrm #1}_{#2}(#3)}
\newcommand{\qgosper}{$q$-Gosper\ }
\newcommand{\qgosperalg}{\qgosper algorithm\ }
\newcommand{\qzeilalg}{$q$-Zeilberger algorithm\ }
\newcommand{\qfac}[2]{\left(#1;\,q\right)_{#2}}
\newcommand{\qatom}[1]{\left(#1;\,q\right)_{\infty}}
%\newcommand{\qbinomial}[2]{\left(\begin{array}{c}#1\\#2\end{array}\right)_q}
%\newcommand{\binomial}[2]{\left(\begin{array}{c}#1\\#2\end{array}\right)}
\newcommand{\binomial}[2]{{#1 \choose #2}}
\newcommand{\qbinomial}[2]{{{#1 \choose #2}\!}_q}
\newcommand{\qfactorial}[2]{}
\newcounter{redprompt}
{\setcounter{redprompt}{0}}
\newcommand{\redprompt}{\stepcounter{redprompt}\theredprompt:}
\newenvironment{redoutput}{\small\begin{alltt}}{\end{alltt}\noindent{}}
% ----------------------------------------------------------------------
\begin{document}
%
\maketitle
%
\section{Introduction}
This package is an implementation of the $q$-analogues of Gosper's
and Zeil\-berger's%
%
\footnote{The {\tt ZEILBERG} package (see \cite{Koepf2})
contains the hypergeometric versions. Those algorithms are described in
\cite{Gosper},\cite{hyper_Zeilberger1},\cite{hyper_Zeilberger2}
and \cite{Koepf1}.}
%
algorithm for indefinite, and definite summation of
$q$-hypergeo\-metric terms, respectively.
An expression $a_k$ is called a {\sl $q$-hypergeometric term}, if
$a_{k}/a_{k-1}$ is a rational function with respect to $q^k$. Most
$q$-terms are based on the {\sl $q$-shifted factorial} or
{\sl qpochhammer}. Other typical $q$-hypergeometric terms are ratios
of products of powers, $q$-factorials, $q$-binomial coefficients, and
$q$-shifted factorials that are integer-linear in their arguments.
% ----------------------------------------------------------------------
\section{Elementary \textsl{q}-Functions}
Our package supports the input of the following elementary
$q$-functions:
\begin{itemize}
%
\item {\verb@qpochhammer(a,q,infinity)@}\[
\qfac{a}{\infty}:= \prod_{j=0}^{\infty}{\left(1-a\,q^j\right)}
\]
\item {\verb@qpochhammer(a,q,k)@} \[
\qfac{a}{k}:= \funkdefff{\prod_{j=0}^{k-1}{\left(1-a\,q^j\right)}}%
{k>0}{1}{k=0}{\prod_{j=1}^{k}{\left(1-a\,q^{-j}\right)^{-1}}}{k<0}
\]
\item {\verb@qbrackets(k,q)@}
\[ {}[q,k]:=\frac{q^k-1}{q-1} \]
\item {\verb@qfactorial(k,q)@}
\[ {}[k]_q!:= \frac{\qfac{q}{k}}{(1-q)^k} \]
\item {\verb@qbinomial(n,k,q)@}
\[ \qbinomial{n}{k}:=
\frac{\qfac{q}{n}}{\qfac{q}{k}\cdot\qfac{q}{n-k}} \]
\end{itemize}
Furthermore it is possible to use an abbreviation for the
{\sl generalized $q$-hypergeometric series}
({\sl basic generalized hypergeometric series},
see e.\,g.\ \cite{GasperRahman}, Chapter 1) which is defined as:
\begin{eqnarray*}
\qphihyp{r}{s}{a_1,a_2,\ldots,a_r}{b_1,b_2,\ldots,b_s}{z}:=
\hspace{15em}\\ \hspace{10em}
\sum_{k=0}^{\infty}{\frac{\qfac{a_1,a_2,\ldots,a_r}{k}}
{\qfac{b_1,b_2,\ldots,b_s}{k}}
\,\frac{z^k}{\qfac{q}{k}}\,\left[(-1)^k\,
q^{\binomial{k}{2}}\right]^{1+s-r}}
\end{eqnarray*}
where $\qfac{a_1,a_2,\ldots,a_r}{k}$ is a short form to write the
product $\prod_{j=1}^r{\qfac{a_j}{k}}$. An ${}_r\phi_s$ series
terminates if one of its numerator parameters is of the form
$q^{-n}$ with $n\in\N$. The additional factor
$\left[(-1)^k\,q^{\binomial{k}{2}}\right]^{1+s-r}$ (which does not
occur in the corresponding definition of the {\sl generalized
hypergeometric function}) is due to a {\sl confluence process}.
With this factor one gets the simple formula:
\[
\lim_{a_r\rightarrow\infty}{\qphihyp{r}{s}{a_1,a_2,\ldots,a_r}
{b_1,b_2,\ldots,b_s}{z}} =
{\qphihyp{r-1}{s}{a_1,a_2,\ldots,a_{r-1}}{b_1,b_2,\ldots,b_s}{z}}.
\]
Another variation is the {\sl bilateral basic hypergeometric
series} (see e.\,g.\ \cite{GasperRahman}, Chapter 5) that is defined as
\[
\qpsihyp{r}{s}{a_1,a_2,\ldots,a_r}{b_1,b_2,\ldots,b_s}{z}:=
\sum_{k=-\infty}^{\infty}{\frac{\qfac{a_1,a_2,\ldots,a_r}{k}}
{\qfac{b_1,b_2,\ldots,b_s}{k}}\,z^k\,
\left[(-1)^k\,q^{\binomial{k}{2}}\right]^{s-r}}.
\]
The \textsl{summands} of those generalized $q$-hypergeometric series may
be entered by
\begin{itemize}
\item {\protect\verb-qphihyperterm({a1,a2,...,a3},{b1,b2,...,b3},q,z,k)-}
and
\item {\protect\verb-qpsihyperterm({a1,a2,...,a3},{b1,b2,...,b3},q,z,k)-}
\end{itemize}
respectively.
% ----------------------------------------------------------------------
\section{\textsl{q}-Gosper Algorithm}
\label{qgosper}
The \qgosperalg \cite{Koornwinder} is a {\sl decision procedure}, that
decides by algebraic calculations whether or not a given
$q$-hypergeometric term $a_k$ has a $q$-hypergeometric term
antidifference $g_k$, i.\,e.\ $a_k=g_{k}-g_{k-1}$ with
$g_{k}/g_{k-1}$ rational in $q^k$. The ratio $g_k/a_k$ is also rational
in $q^k$ --- an important fact which makes the
\textsl{rational certification} (see \S~\ref{qzeilberger}) of Zeilberger's
algorithm possible. If the procedure is successful
it returns $g_k$, in which case we call $a_k$
{\sl $q$-Gosper-summable}. Otherwise
{\sl no $q$-hypergeometric antidifference exists}. Therefore
if the \qgosperalg does not return a $q$-hypergeometric antidifference,
it has {\sl proved} that no such solution exists, an information
that may be quite useful and important.
Any antidifference is uniquely determined up to a constant, and is
denoted by
\[
g_k=\sum a_k\,\delta_k
\;.
\]
Finding $g_k$ given $a_k$ is called {\sl indefinite summation}.
The antidifference operator $\Sigma$ is the inverse of the downward
difference operator $\nabla a_k=a_{k}-a_{k-1}$. There is an analogous
summation theory corresponding to the upward difference operator
$\Delta a_k=a_{k+1}-a_k$.
In case, an antidifference $g_k$ of $a_k$ is known, any sum
$\sum_{k=m}^n{a_k}$ can be easily calculated by an evaluation of
$g$ at the boundary points like in the integration case:
\[
\sum_{k=m}^{n}{a_k} = g_{n}-g_{m-1}
\]
% ======================================================================
\section{\textsl{q}-Zeilberger Algorithm}
\label{qzeilberger}
The $q$-Zeilberger algorithm \cite{Koornwinder}
deals with the {\sl definite summation} of
$q$-hyper\-geo\-metric terms $\fcn{f}{n,k}$ wrt.\ $n$ and $k$:
\[
\fcn{s}{n}:= \sum_{k=-\infty}^\infty{\fcn{f}{n,k}}
\]
Zeilberger's idea is to use Gosper's algorithm to find an
inhomogeneous recurrence equation with polynomial coefficients
for $\fcn{f}{n,k}$ of the form
\begin{equation} \label{eq:f_n_k-recursion}
\sum_{j=0}^J{\ifcn{\sigma}{j}{n}\cdot \fcn{f}{n+j,k}} =
\fcn{g}{k}-\fcn{g}{k-1},
\end{equation}
where $\fcn{g}{k}/\fcn{f}{k}$ is rational in $q^k$ and $q^n$.
Assuming finite support of $\fcn{f}{n,k}$ wrt.\ $k$
(i.\,e. $\fcn{f}{n,k}=0$ for any $n$ and all sufficiently large $k$)
we can sum equation (\ref{eq:f_n_k-recursion}) over all $k\in\Z$.
Thus we receive a homogeneous recurrence equation with polynomial
coefficients (called {\sl holonomic equation}) for $\fcn{s}{n}$:
\begin{equation} \label{holonomic_recurrence}
\sum_{j=0}^J{\ifcn{\sigma}{j}{n}\cdot \fcn{s}{n+j}} = 0
\end{equation}
%
At this stage the implementation assumes that the summation
bounds are infinite and the input term has finite support wrt.\ $k$.
If those input requirements are not fulfilled the resulting
recursion is probably not valid. Thus we strongly advise the user to
check those requirements.
Despite this restriction you may still be able to get valuable
information by the program: On request it returns the
left hand side of the recurrence equation (\ref{holonomic_recurrence})
\textsl{and} the antidifference $\fcn{g}{k}$ of equation
(\ref{eq:f_n_k-recursion}).
Once you have the certificate $\fcn{g}{k}$ it is trivial
(at least theoretically) to prove equation (\ref{holonomic_recurrence})
as long as the input requirements are fulfilled. Let's assume
somone gives us equation (\ref{eq:f_n_k-recursion}). If we divide
it by $\fcn{f}{n,k}$ we get a rational identity (in $q^n$ and $q^k$)
---due to the fact that $\fcn{g}{k}/\fcn{f}{n,k}$ is rational in
$q^n$ and $q^k$. Once we confirmed this identity we sum equation
(\ref{eq:f_n_k-recursion}) over $k\in\Z$:
\begin{equation}
\sum_{k\in\Z}\sum_{j=0}^J{\ifcn{\sigma}{j}{n}\cdot \fcn{f}{n+j,k}} =
\sum_{k\in\Z}{\left(\fcn{g}{k}-\fcn{g}{k-1}\right)},
\end{equation}
Again we exploit the
fact that $\fcn{g}{k}$ is a rational multiple of $\fcn{f}{n,k}$ and thus
$\fcn{g}{k}$ has \textsl{finite support} which makes the telescoping sum
on the right hand side vanish. If we exchange the order of summation we
get equation (\ref{holonomic_recurrence}) which finishes the proof.
Note that we may relax the requirements for $\fcn{f}{n,k}$:
An infinite support is possible as long as
$\lim\limits_{k\rightarrow\infty}{\fcn{g}{k}}=0$.
(This is certainly true if
$\lim\limits_{k\rightarrow\infty}{\fcn{p}{k}\,\fcn{f}{k}}=0$ for
all polynomials $\fcn{p}{k}$.)
For a quite general class of $q$-hypergeometric terms
({\sl proper q-hypergeometric terms}) the \qzeilalg
always finds a recurrence equation, not necessarily of lowest
order though. Unlike Zeilberger's original algorithm its
$q$-analogue more often fails to determine the recursion of
lowest possible order, however (see \cite{Paule1}).
If the resulting recurrence equation is of first order
\[
\fcn{a}{n}\,\fcn{s}{n-1}+\fcn{b}{n}\,\fcn{s}{n}=0
\;,
\]
$\fcn{s}{n}$ turns out to be a $q$-hypergeometric term
(as a and b are polynomials in $q^n$),
and a $q$-hypergeometric solution can be easily established using a
suitable initial value.
If the resulting recurrence equation has order larger than one,
this information can be used for identification purposes:
Any other expression satisfying the same recurrence equation, and the same
initial values, represents the same function.
Our implementation is mainly based on \cite{Koornwinder} and on the
hypergeometric analogue described in \cite{Koepf1}.
More examples can be found in \cite{GasperRahman}, \cite{Gasper},
some of which are contained in the test file
{\tt qsum.tst}.
% ======================================================================
\section{\REDUCE{} operator {\tt QGOSPER}}
\label{reduce_qgosper}
The QSUM package must be loaded by:
\begin{redoutput}
\redprompt load qsum;
\end{redoutput}
The {\tt qgosper} operator is an implementation of the $q$-Gosper
algorithm.
\begin{itemize}
\item {\verb@qgosper(a,q,k)@} determines a $q$-hypergeometric
antidifference. (By default it returns a {\sl downward}
antidifference, which may be changed by the switch
{\verb@qgosper_down@}; see also
\S~\ref{switches}.)
If it does not return a \textsl{q}-hypergeometric antidifference,
then such an antidifference does not exist.
\item {\verb@qgosper(a,q,k,m,n)@} determines a closed formula
for the definite sum $\sum\limits_{k=m}^n a_k$ using the
$q$-analogue of Gosper's algorithm.
This is only successful if \textsl{q}-Gosper's algorithm applies.
\end{itemize}
{\bf Examples}: The following two examples can be found in
\cite{GasperRahman} ((II.3) and (2.3.4)).
\begin{redoutput}
\redprompt qgosper(qpochhammer(a,q,k)*q^k/qpochhammer(q,q,k),q,k);
k
(q *a - 1)*qpochhammer(a,q,k)
-------------------------------
(a - 1)*qpochhammer(q,q,k)
\redprompt qgosper(qpochhammer(a,q,k)*qpochhammer(a*q^2,q^2,k)*
qpochhammer(q^(-n),q,k)*q^(n*k)/(qpochhammer(a,q^2,k)*
qpochhammer(a*q^(n+1),q,k)*qpochhammer(q,q,k)),q,k);
k*n k k n 1
( - q *(q *a - 1)*(q - q )*qpochhammer(----,q,k)
n
q
2 2 2*k n
*qpochhammer(a*q ,q ,k)*qpochhammer(a,q,k))/((q *a - 1)*(q - 1)
n 2
*qpochhammer(q *a*q,q,k)*qpochhammer(a,q ,k)*qpochhammer(q,q,k))
\end{redoutput}
Here are some other simple examples:
\begin{redoutput}
\redprompt qgosper(qpochhammer(q^(-n),q,k)*z^k/qpochhammer(q,q,k),q,k);
***** No q-hypergeometric antidifference exists.
\redprompt off qgosper_down;
\redprompt qgosper(q^k*qbrackets(k,q),q,k);
k k
- q *(q + 1 - q )*qbrackets(k,q)
-----------------------------------
k
(q - 1)*(q + 1)*(q - 1)
\redprompt on qgosper_down;
\redprompt qgosper(q^k,q,k,0,n);
n
q *q - 1
----------
q - 1
\end{redoutput}
\vspace{-2ex}%
% ----------------------------------------------------------------------
%
\section{\REDUCE{} operator {\tt QSUMRECURSION}}
\label{reduce_qsumrecursion}
The {\tt qsumrecursion} operator is an implementation of the
$q$-Zeilberger algorithm.
It tries to determine a homogeneous recurrence equation for
$\fcn{summ}{n}$ wrt. $n$ with polynomial coefficients (in $n$), where
%
\[
\fcn{summ}{n}:= \sum_{k=-\infty}^{\infty}{\fcn{f}{n,k}}.
\]
%
If successful the left hand side of the recurrence equation
(\ref{holonomic_recurrence}) is returned.
There are three different ways to pass a summand $\fcn{f}{n,k}$
to {\verb@qsumrecursion@}:
%
\begin{itemize}
\item {\verb@qsumrecursion(f,q,k,n)@}, where {\tt f} is a
$q$-hypergeometric term wrt. {\tt k} and {\tt n},
{\tt k} is the summation variable and {\tt n} the recursion
variable, {\tt q} is a symbol.
\item {\verb@qsumrecursion(upper,lower,q,z,n)@} is a shortcut for \\
{\verb@qsumrecursion(qphihyperterm(upper,lower,q,z,k),q,k,n)@}
\item {\verb@qsumrecursion(f,upper,lower,q,z,n)@} is a similar
shortcut for\\
{\verb@qsumrecursion(f*qphihyperterm(upper,lower,q,z,k),q,k,n)@},
\end{itemize}
%
i.\,e.\ {\tt upper} and {\tt lower} are lists of upper and lower
parameters of the generalized $q$-hypergeometric function.
The third form is handy if you have any additional factors.
For all three instances the following variations are allowed:
\begin{itemize}
\item If for some reason the recursion order is known in
advance you can specify it as an additional ({\sl optional}\,)
argument at the very end of the parameter sequence. There are two
ways. If you just specify a positive integer,
{\tt qsumrecursion} looks only for a recurrence equation of this order.
You can also specify a range by a list of two positive integers,
i.\,e.\ the first one specifying the lowest and the second one the
highest order.
By default {\tt qsumrecursion} will search for recurrences
of order from 1 to 5. (The global variable
{\verb@qsumrecursion_recrange!*@} controls this behavior,
see \S~\ref{switches}.)
\item Usually {\tt qsumrecursion} uses {\tt summ} as a name
for the $\mathrm{summ}$-function defined above. If you want
to use another operator, say e.\,g. {\tt s}, then the
following syntax applies: {\verb@qsumrecursion(f,q,k,s(n))@}
\end{itemize}
As a first example we want to consider the {\sl q-binomial theorem}:
\[
\sum_{k=0}^\infty{\frac{\qfac{a}{k}}{\qfac{q}{k}}z^k} =
\frac{\qfac{a\,z}{\infty}}{\qfac{z}{\infty}},
\]
provided that $|z|,|q|<1$.
It is the $q$-analogue of the binomial theorem in the sense that
\[
\lim_{q\rightarrow{}1^-}\;{\sum_{k=0}^\infty{
\frac{\qfac{q^a}{k}}{\qfac{q}{k}}z^k}} \;\;=\;\;
\sum_{k=0}^\infty{\frac{(a)_k}{k!}z^k} \;\;=\;\; (1-z)^{-a}\;.
\]
For $a:=q^{-n}$ with $n\in\N$ our implementation gets:
\begin{redoutput}
\redprompt qsumrecursion(qpochhammer(q^(-n),q,k)*z^k/
qpochhammer(q,q,k),q,k,n);
n n
- ((q - z)*summ(n - 1) - q *summ(n))
\end{redoutput}
%
Notice that the input requirements are fulfilled. For $n\in\N$ the
summand is zero for all $k>n$ as $\qfac{q^{-n}}{k}=0$ and
the $\qfac{q}{k}$-term in the denominator makes the summand
vanish for all $k<0$.
With the switch \verb@qsumrecursion_certificate@ it is possible
to get the antidifference $g_k$ described above. When switched
on, \verb@qsumrecursion@ returns a list with five entries,
see \S~\ref{switches}. For the
last example we get:
\begin{redoutput}
\redprompt on qsumrecursion_certificate;
\redprompt proof:= qsumrecursion(qpochhammer(q^(-n),q,k)*z^k/
qpochhammer(q,q,k),q,k,n);
n n
proof := { - ((q - z)*summ(n - 1) - q *summ(n)),
k n
- (q - q )*z
----------------,
n
q - 1
k 1
z *qpochhammer(----,q,k)
n
q
--------------------------,
qpochhammer(q,q,k)
k,
downward_antidifference}
\redprompt off qsumrecursion_certificate;
\end{redoutput}
%
\\[-2.5ex]\noindent{}
Let's define the list entries as \verb@{rec,cert,f,k,dir}@. If you
substitute $\fcn{summ}{n+j}$ by $\fcn{f}{n+j,k}$ in \verb@rec@ then
you obtain the left hand side of equation (\ref{eq:f_n_k-recursion}),
where \verb@f@ is the input summand. The function
$\fcn{g}{k}:=\verb@f*cert@$ is the corresponding
antidifference, where \verb@dir@ states which sort of antidifference
was calculated {\tt downward\_antidifference} or
{\tt upward\_antidifference}, see also \S~\ref{switches}.
Those informations enable you to prove the recurrence equation for
the sum or supply you with the necessary informations to determine
an inhomogeneous recurrence equation for a sum with nonnatural bounds.
For our last example we can now calculate both sides of
equation (\ref{eq:f_n_k-recursion}):
\begin{redoutput}
\redprompt lhside:= qsimpcomb(sub(summ(n)=part(proof,3),
summ(n-1)=sub(n=n-1,part(proof,3)),part(proof,1)));
k k n n 1
z *(q *(q - z) + q *(z - 1))*qpochhammer(----,q,k)
n
q
lhside := -----------------------------------------------------
n
(q - 1)*qpochhammer(q,q,k)
\redprompt rhside:= qsimpcomb((part(proof,2)*part(proof,3)-
sub(k=k-1,part(proof,2)*part(proof,3))));
k k n n k 1
- z *((q - q )*z - q *(q - 1))*qpochhammer(----,q,k)
n
q
rhside := ---------------------------------------------------------
n
(q - 1)*qpochhammer(q,q,k)
\redprompt qsimpcomb((rhside-lhside)/part(proof,3));
0
\end{redoutput}
%
\\[-2.5ex]\noindent{}
Thus we have proved the validity of the recurrence equation.
As some other examples we want to consider some generalizations
of orthogonal polynomials from the
Askey--Wilson--scheme \cite{KoekoekSwarttouw}: The $q$-Laguerre
(3.21), $q$-Charlier (3.23) and the continuous $q$-Jacobi (3.10)
polynomials.
\begin{redoutput}
\redprompt operator qlaguerre,qcharlier;
\redprompt qsumrecursion(qpochhammer(q^(alpha+1),q,n)/qpochhammer(q,q,n),
\{q^(-n)\}, \{q^(alpha+1)\}, q, -x*q^(n+alpha+1), qlaguerre(n));
n alpha + n n
((q + 1 - q )*q - q *(q *x + q))*qlaguerre(n - 1)
alpha + n n
+ ((q - q)*qlaguerre(n - 2) + (q - 1)*qlaguerre(n))*q
\redprompt qsumrecursion(\{q^(-n),q^(-x)\},\{0\},q,-q^(n+1)/a,qcharlier(n));
x n n 2*n
- ((q *((q + 1 - q )*a + q )*q - q )*qcharlier(n - 1)
x n n
+ q *((q + a*q)*(q - q)*qcharlier(n - 2) - qcharlier(n)*a*q))
\redprompt on qsum_nullspace;
\redprompt term:= qpochhammer(q^(alpha+1),q,n)/qpochhammer(q,q,n)*
qphihyperterm(\{q^(-n),q^(n+alpha+beta+1),
q^(alpha/2+1/4)*exp(I*theta), q^(alpha/2+1/4)*exp(-I*theta)\},
\{q^(alpha+1), -q^((alpha+beta+1)/2), -q^((alpha+beta+2)/2)\},
q,q,k)$
\redprompt qsumrecursion(term,q,k,n,2);
\end{redoutput}
{\footnotesize
\begin{alltt}
n i*theta alpha beta n
- ((q *e *(q *(q *(q *(q + 1) - q) - q
alpha + beta + n n beta + n
+ q *(q + 1 - q - q )) -
(alpha + beta)/2 alpha n beta + n n
q *(q *(q *(q + 1) - q + q *(q + 1 - q ))
2*alpha + beta + 2*n
- (q + q)))*(sqrt(q) + q) +
(2*alpha + 1)/4 2*i*theta alpha + beta + 2*n 2
q *(e + 1)*(q - q )
alpha + beta + 2*n alpha + beta + 2*n
*(q - 1))*(q - q)*summ(n - 1) -
i*theta (alpha + beta + 2*n)/2 (alpha + beta + 2*n)/2
e *((q *(q + q)
(alpha + beta + 2*n)/2
*(q - q)*(sqrt(q) + q) +
(2*alpha + 2*beta + 4*n + 1)/2
(q + q)
\newpage
alpha + beta + 2*n 2 alpha + beta + n
*(q - q ))*(q - 1)
n alpha alpha + beta + 2*n
*(q - 1)*summ(n) + (q *(sqrt(q)*q + q )
(3*alpha + beta + 2*n)/2
+ q *(sqrt(q) + q))
alpha + beta + 2*n alpha + n beta + n
*(q - 1)*(q - q)*(q - q)
*summ(n - 2)))
\redprompt off qsum_nullspace;
\end{alltt}}
The setting of {\verb@qsum_nullspace@}
(see \cite{Paule1} and \S~\ref{switches})
results in a faster
calculation of the recurrence equation for this example.
% ----------------------------------------------------------------------
\section{Simplification Operators}
\label{simplification}
An essential step in the algorithms introduced above is to decide
whether a term $a_k$ is $q$-hypergeometric, i.\,e.\ if the
ratio $a_{k}/a_{k-1}$ is rational in $q^k$.
The procedure \verb@qsimpcomb@ provides this facility. It tries to
simplify all exponential expressions in the given term and applies
some transformation rules to the known elementary $q$-functions
as \verb@qpochhammer@, \verb@qbrackets@, \verb@qbinomial@
and \verb@qfactorial@. Note that the procedure may fail to
completely simplify some expressions. This is due to the fact that the
procedure was designed to simplify ratios of $q$-hypergeometric
terms in the form $\fcn{f}{k}/\fcn{f}{k-1}$ and not arbitrary
$q$-hypergeometric terms.
E.\,g.\ an expression like
$\qfac{a}{-n}\cdot\qfac{a/q^n}{n}$
is not recognized as 1, despite the transformation formula
\[ \qfac{a}{-n} \;=\; \frac{1}{\qfac{a/q^n}{n}},\]
which is valid for $n\in\N$.
Note that due to necessary simplification of powers, the switch
\verb@precise@ is (locally) turned off in \verb@qsimpcomb@. This
might produce wrong results if the input term contains
e.\,g.\ complex variables.
The following synomyms may be used:
\begin{itemize}
\item \verb@up_qratio(f,k)@ or \verb@qratio(f,k)@ for
\verb@qsimpcomb(sub(k=k+1,f)/f)@ and
\item \verb@down_qratio(f,k)@ for \verb@qsimpcomp(f/sub(k=k-1,f))@.
\end{itemize}
% ----------------------------------------------------------------------
\section{Global Variables and Switches}
\label{switches}
The following switches can be used in connection with
the {\tt QSUM} package:
%
\begin{itemize}
\item \verb@qsum_trace@, default setting is off. If it is
turned on some intermediate results are printed.
\item \verb@qgosper_down@, default setting is on. It determines
whether \verb@qgosper@ returns a downward or an upward
antidifference $g_k$ for the input term $a_k$,
i.\,e.\ $a_k=g_k-g_{k-1}$ or $a_k=g_{k+1}-g_k$ respectively.
\item \verb@qsumrecursion_down@, default setting is on. If it is
switched on a downward recurrence equation will be returned by
\verb@qsumrecursion@. Switching it off leads to an upward
recurrence equation.
\item \verb@qsum_nullspace@, default setting is off. The
antidifference $\fcn{g}{k}$ is always a rational multiple (in $q^k$)
of the input term $\fcn{f}{k}$. \verb@qgosper@ and \verb@qsumrecursion@
determine this certificate, which requires solving a set of
linear equations. If the switch \verb@qsum_nullspace@ is
turned on a modified nullspace-algorithm will be used for
solving those equations. In general this method is slower.
However if the resulting recurrence equation is quite complicated
it might help to switch on \verb@qsum_nullspace@.
See also \cite{Knuth} and \cite{Paule1}.
\item \verb@qgosper_specialsol@, default setting is on. The
antidifference $\fcn{g}{k}$ which is determined by
\verb@qgosper@ might not be unique. If this switch is turned on,
just one special solution is returned. If you want
to see all solutions, you should turn the switch off.
\item \verb@qsumrecursion_exp@, default setting is off. This
switch determines if the coefficients of the
resulting recurrence equation should
be factored. Turning it off might speed up the calculation
(if factoring is complicated). Note that
when turning on \verb@qsum_nullspace@ usually no speedup
occurs by switching \verb@qsumrecursion_exp@ on.
\item \verb@qsumrecursion_certificate@, default off.
As Zeilberger's algorithm
delivers a recurrence equation for a $q$-hypergeometric term
$\mathrm{f}(n,k)$, see equation (\ref{eq:f_n_k-recursion}),
this switch is used to get all necessary informations for
proving this recurrence equation.
If it is set on, instead of simply returning the
resulting recurrence equation (for the sum)---if one
exists---\verb@qsumrecursion@ returns
a list \verb@{rec,cert,f,k,dir}@ with
five items: The first entry contains the
recurrence equation, while the other items enable you to
prove the recurrence a posteriori by rational arithmetic.
If we denote by \verb@r@ the recurrence
\verb@rec@ where we substituted the \verb@summ@-function
by the input term \verb@f@ (with the corresponding shifts
in \verb@n@) then the following equation is valid:
\[ \verb@r = cert*f - sub(k=k-1,cert*f)@ \]
or
\[ \verb@r = sub(k=k+1,cert*f) - cert*f@ \]
if \verb@dir=downward_antidifference@ or
\verb@dir=upward_antidifference@ respectively.
\end{itemize}
The global variable \verb@qsumrecursion_recrange!*@ controls for
which recursion orders the procedure \verb@qsumrecursion@ looks.
It has to be a list with two entries, the first one representing
the lowest and the second one the highest order of a recursion
to search for. By default it is set to \verb@{1,5}@.
% ----------------------------------------------------------------------
\section{Messages}
The following messages may occur:
\begin{itemize}
%
\item If your call to \verb@qgosper@ or \verb@qsumrecursion@
reveals some incorrect syntax, e.\,g.\ wrong number of
arguments or wrong type you may receive the following messages:
\begin{verbatim}***** Wrong number of arguments.\end{verbatim}
or
\begin{verbatim}***** Wrong type of arguments.\end{verbatim}
%
\item If you call \verb@qgosper@ with a summand term that
is free of the summation variable you get
\begin{verbatim}
WARNING: Summand is independent of summation variable.
***** No q-hypergeometric antidifference exists.
\end{verbatim}
%
% \item It is not allowed to specify bounds in \verb@qgosper@ which
% contain the summation variable. Otherwise you get the message:
% \begin{verbatim}
% ***** Summation bounds contain the summation variable.
% \end{verbatim}
%
\item If \verb@qgosper@ finds no antidifference it returns:
\begin{verbatim}
***** No q-hypergeometric antidifference exists.
\end{verbatim}
%
\item If \verb@qsumrecursion@ finds no recursion in the specified
range it returns:
\begin{verbatim}***** Found no recursion. Use higher order.\end{verbatim}
(If you do not pass a range as an argument to \verb@qsumrecursion@
the default range in \verb@qsumrecursion_recrange!*@ will be used.)
%
\item If the input term passed to \verb@qgosper@
(\verb@qsumrecursion@) is not $q$-hyper\-geometric wrt.\ the
summation variable --- say $k$ --- (and the recursion variable)
then you get
\begin{verbatim}
***** Input term is probably not q-hypergeometric.
\end{verbatim}
With all the examples we tested, our procedures decided properly
whether the input term was $q$-hypergeometric or not. However, we
cannot guarantee in general that \verb@qsimpcomb@ {\sl always} returns
an expression that {\sl looks} rational in $q^k$ if it actually is.
%
\item If the global variable \verb@qsumrecursion_recrange!*@ was
assigned an invalid value:
\begin{verbatim}
Global variable qsumrecursion_recrange!* must be a list
of two positive integers: {lo,hi} with lo<=hi.
***** Invalid value of qsumrecursion_recrange!*
\end{verbatim}
%
\end{itemize}
% ----------------------------------------------------------------------
\begin{thebibliography}{99}
\bibitem{AskeyWilson}
% check
Askey R.\ and Wilson, J.:
{\sl Some Basic Hypergeometric Orthogonal Polynomials that Generalize Jacobi
Polynomials}. Memoirs Amer.\ Math.\ Soc.\ 319, Providence, RI, 1985.
\bibitem{Gasper}
Gasper, G.:
{\sl Lecture Notes for an Introductory Minicourse on $q$-Series}.
1995. To obtain from
ftp://unvie6.un.or.at/siam/opsf\_new/\linebreak 00index\_by\_author.html.
\bibitem{GasperRahman}
Gasper, G.\ and Rahman, M.:
{\sl Basic Hypergeometric Series},
Encyclopedia of Mathematics and its Applications,
{\bf 35}, (G.-C.\ Rota, ed.), Cambridge University Press,
London and New York, 1990.
\bibitem{Gosper}
Gosper Jr., R.\ W.:
Decision procedure for indefinite hypergeometric
summation. Proc.\ Natl.\ Acad.\ Sci.\ USA {\bf 75}, 1978, 40--42.
\bibitem{Knuth}
Knuth, D.\ E.:
{\sl The Art of Computer Programming, Seminumerical Algorithms}.
2nd ed., 1981, Addison-Wesley Publishing Company.
\bibitem{Koepf1}
Koepf, W.:
Algorithms for $m$-fold hypergeometric summation.
Journal of Symbolic Computation {\bf 20}, 1995, 399--417.
%(Zbl.\ Math.\ 851.68049, summary).
\bibitem{Koepf2}
Koepf, W.:
REDUCE package for indefinite and definite summation.
% Konrad-Zuse-Zentrum Berlin (ZIB), Technical Report TR 94-9, 1994.
SIGSAM Bulletin {\bf 29}, 1995, 14--30.
\bibitem{Koornwinder}
Koornwinder, T.\ H.:
On Zeilberger's algorithm and its $q$-analogue: a rigorous description.
J.\ of Comput.\ and Appl.\ Math.\ {\bf 48}, 1993, 91--111.
\bibitem{KoekoekSwarttouw}
Koekoek, R.\ und Swarttouw, R.F.:
{\sl The Askey-scheme of Hypergeometric Orthogonal
Polynomials and its $q$-analogue}. Report 94--05, Tech\-nische Universiteit
Delft, Faculty of Technical Mathematics and Informatics, Delft, 1994.
\bibitem{Paule1}
Paule, P.\ und Riese, A.:
A Mathematica \textsl{q}-analogue of Zeilberger's\linebreak[4]
algorithm based on an
algebraically motivated approach to \textsl{q}-hyper\-geometric telescoping.
Fields Proceedings of the Workshop `Special Functions, \textsl{q}-Series
and Related Topics', organized by the Fields Institute for Research in
Mathematical Sciences at Univerisity College,
12-23 June 1995, Toronto, Ontario,179--210.
\bibitem{hyper_Zeilberger1}
Zeilberger, D.:
A fast algorithm for proving terminating hypergeometric identities.
Discrete Math.\ {\bf 80}, 1990, 207--211.
\bibitem{hyper_Zeilberger2}
Zeilberger, D.:
The method of creative telescoping.
J.\ Symbolic Computation {\bf 11}, 1991, 195--204.
\end{thebibliography}
\end{document}