\chapter[QSUM: {\slshape q}-hypergeometric sums]%
{QSUM : Package for {\slshape q}-hypergeometric sums}
\label{QSUM}
\typeout{{QSUM : Package for summation of
                $q$-hypergeometric terms}}


\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{}}

{\footnotesize
\begin{center}
Harald B\"oing \\
Wolfram Koepf \\
Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D-14195 Berlin-Dahlem \\
e-mail: koepf@zib.de
\end{center}
}
\ttindex{QSUM}
%\markboth{CHAPTER \ref{QSUM}. QSUM: SUMMATION OF Q-HYPERGEOMETRIC TERMS}{}
%\thispagestyle{myheadings}


This package is an implementation of the $q$-analogues of Gosper's
and Zeilberger's
%
\footnote{The {\tt ZEILBERG} package (Chap. \ref{ZEILBERG} 
p. \pageref{ZEILBERG}, see also \cite{Koepf:95})
contains the hypergeometric versions.}
%
algorithm for indefinite and definite summation of
$q$-hypergeometric 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. \\
The package is loaded with {\tt load\_package qsum}.

\section{Elementary {\slshape q}-Functions}
The package supports the input of the following elementary 
{\slshape q}-functions:
\begin{itemize}

\item {\verb@qpochhammer(a,q,infinity)@}
	\ttindex{QPOCHHAMMER}
	\[ \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)@}
	\ttindex{QBRACKETS}
	\[  {}[q,k]:=\frac{q^k-1}{q-1}  \]
\item {\verb@qfactorial(k,q)@}
	\ttindex{QFACTORIAL}
	\[   {}[k]_q!:= \frac{\qfac{q}{k}}{(1-q)^k}  \]
\item {\verb@qbinomial(n,k,q)@}
	\ttindex{QBINOMIAL}
	\[  \qbinomial{n}{k}:=
		\frac{\qfac{q}{n}}{\qfac{q}{k}\cdot\qfac{q}{n-k}} \]
\item {\protect\verb@qphihyperterm({a1,a2,...,ar},{b1,b2,...,bs},q,z,k)@}
	\ttindex{QPHIHYPERTERM}
	\[ \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}} \]

\item {\protect\verb@qpsihyperterm({a1,a2,...,ar},{b1,b2,...,bs},q,z,k)@}
	\ttindex{QPSIHYPERTERM}
        \[\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}} \]
\end{itemize}
where $\qfac{a_1,a_2,\ldots,a_r}{k}$ stands for the
product $\prod_{j=1}^r{\qfac{a_j}{k}}$.

\section{The {\ttfamily QGOSPER} operator}

The {\tt qgosper} operator is an implementation of the $q$-Gosper
algorithm \cite{Koornwinder:93}.
\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@}.)
		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 Example:}
\begin{verbatim}
1: 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)

\end{verbatim}



\section{The {\ttfamily QSUMRECURSION} operator}
\label{QSUMRECURSION}

The \f{QSUMRECURSION\ttindex{QSUMRECURSION}} operator is an implementation 
of the $q$-Zeilberger algorithm \cite{Koornwinder:93}.
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}}.
\]

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 it is possible to pass the order, if known 
in advance, as additional argument at the end of the parameter sequence.
You can also specifiy a range by a list of two positive integers, the first
one specifying the lowest and the second one the highest order. By default
\f{QSUMRECURSION} will search for recurrences of order from 1 to 5. Usually
it uses {\tt summ} as name for the summ-function. If you want to change this 
behaviour then use the following syntax: \f{QSUMRECURSION(f,q,k,s(n))}.

\begin{verbatim}
2: 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{verbatim}

\section{Global Variables and Switches}

There are several switches defined in the \f{QSUM} package. Please take a
look in the accompanying documentation file {\tt qsum.tex} in 
\$REDUCEPATH/packages/. \\

The most important switches are:

\begin{itemize}

\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$,
	.\,e.\ $a_k=g_k-g_{k-1}$ or $a_k=g_{k+1}-g_k$ respectively.
\item \verb@qsumrecursion_certificate@, default off. 
	As Zeilberger's algorithm 
	delivers a recurrence equation for a $q$-hypergeometric term
	$\mathrm{f}(n,k)$ 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}

There is one global variable:

\begin{itemize}
\item \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}@.
\end{itemize}
