

\documentclass[12pt,reqno,a4paper]{amsart}%{article}
%\usepackage{a4ams}
\usepackage{amsfonts,amsmath,amssymb}

\allowdisplaybreaks

\topmargin 0 pt
\textheight 46\baselineskip
\advance\textheight by \topskip
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 2pt minus 1pt}
\setlength{\textwidth}{155mm}

\setlength{\oddsidemargin}{5.6mm}
\setlength{\evensidemargin}{5.6mm}

\def\C{\mathcal{C}}
\def\N{\mathbb{N}}

\newcommand{\stwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newtheorem{theorem}{Theorem}

\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}%[section]


\newtheorem{prop}{Proposition}
%\numberwithin{equation}{section}

\def\Prob{\mathbb{P}}
\def\prob{\mathbb{P}}
\def\expect{\mathbb{E}}
\def\shuffle{\sqcup\kern-0.07cm\sqcup}

\newcommand{\Res}{\operatornamewithlimits{Res}}

\def\eps{\varepsilon}
\def\al{\alpha}
\def\1{\bar{1}}

\def\qf#1#2{(#1;q)_{#2}}
\def\qff#1#2#3{(#1;#2)_{#3}}

\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}  


\title[Some applications of the $q$--Rice formula]
{Some applications of the $\boldsymbol{q}$--Rice formula}


\author{Helmut Prodinger}

\address{ Helmut Prodinger\newline
The John Knopfmacher
Centre for Applicable Analysis and Number Theory\newline
School of Mathematics\newline
University of the Witwatersrand, P.~O. Wits\newline 
2050 Johannesburg, South Africa\newline email:
{\tt helmut@gauss.cam.wits.ac.za},\newline
homepage: {\tt http://www.wits.ac.za/helmut/index.htm}
}



\date{\today}

\begin{document}
\begin{abstract}
We evaluate alternating sums involving $q$--binomial coefficients
using a contour integration technique. In this way we rederive 
very easily some results due to Van Hamme, Uchimura (simplified!), Dilcher,
Andrews, Crippa, and Simon.
\end{abstract}

\maketitle
{\sl
\rightline{Dedicated to my friend Wojtek Szpankowski}
\rightline{on the occasion of his 50th birthday}
}

\section{Introduction}


Rice's method has been a tremendous success in Computer Science, see
\cite{FlSe95} and
\cite{Szpankowski01}; the latter book
devotes a whole chapter to it. 
It is based on the integral representation
\begin{equation*}
\sum_{k=1}^n\binom nk (-1)^kf(k)=
\frac{(-1)^n}{2\pi i}\int_{\C}\frac{n!}{z(z-1)\dots (z-n) }f(z)\,dz,
\end{equation*}
where $\C$ (positively oriented) encloses the poles $1,2,\dots,n$
and no others. Extending the curve of integration and taking the
extra negative residues into account, we get identities, provided the
integrals goes to zero, which it does for a large class of functions
$f(z)$. 
The proof is by Cauchy's integral formula, and the survey \cite{FlSe95}
contains all the technicalities and many examples. 

One simple  example is


\begin{align}\label{simple}\begin{split}
\sum_{k=1}^n\binom nk (-1)^{k-1}\frac1k&=
\frac{(-1)^{n-1}}{2\pi i}\int_{\C}\frac{n!}{z^2(z-1)\dots (z-n) }\,dz\\
&=(-1)^n\Res_{z=0}\frac{n!}{z^2(z-1)\dots (z-n) }\\
&=(-1)^n[z^1]\frac{n!}{(z-1)\dots (z-n) }\\
&=[z^1]\frac{1}{(1-z)(1-\frac z2)\dots (1-\frac zn) }\\
&=[z^1]{(1+z)(1+\tfrac z2)\dots (1+\tfrac zn) }=H_n.
\end{split}
\end{align}


Here we want to consider a $q$--version of this formula and 
show how useful it is. Assume that $q$ is a parameter with $|q|<1$, 
then we define the $q$--binomial coefficients (Gaussian polynomials)
as usually by
\begin{equation*}
\gauss nk:=\frac{\qf q n}{\qf qk\qf q{n-k}},
\end{equation*}
with $\qf zn:=(1-z)(1-zq)\dots(1-zq^{n-1})$, see e.~g.
\cite{Andrews76}.

The formula is now this:


\begin{equation}\label{kurwa}
\sum_{k=1}^n(-1)^{k-1}q^{\binom k2}\gauss nkf(q^{-k})
=
\frac{1}{2\pi i}\int_{\C}\frac{\qf qn}{\qf z{n+1} }f(z)\,dz,
\end{equation}
where $\C$ encircles the poles $q^{-1},\dots,q^{-n}$ and no others.
This follows immediately from
\begin{align*}
\Res_{z=q^{-k}}\frac{\qf qn}{\qf z{n+1} }=(-1)^{k-1}q^{\binom k2}\gauss nk.
\end{align*}
(P.~Borwein used a similar formula in \cite{Borwein88}.)

In this paper we are only interested in deriving {\em identities\/},
leaving applications to asymptotic expansions to future research. 

For that we use
\begin{equation*}
\sum_{k=1}^n(-1)^{k-1}q^{\binom k2}\gauss nkf(q^{-k})
=(-1)^{n+1}\Res_{z}\left\{
f(z){\frac{\qf qn}{\qf z{n+1} }}
\right\},
\end{equation*}
where the sum is extended to all poles $z$ of $f(z)
{\qf qn}/\qf z{n+1}$ not in $\{q^{-1},\dots,q^{-n}\}$
and the function $f(z)$ is a rational function.
This formula, being exact, is the basis of the identities
discussed in the present paper. 



The proof is verbatim as in \cite{FlSe95}: 
A rational function is of {\it polynomial growth\/}, 
i.\,e. $f(z)=O(|z|^s)$ for some $s$.
If $n>s+1$, then
the integral in (\ref{kurwa}),
 taken over a circle of radius $R$
(avoiding poles of the integrand), tends to
zero for $R\to\infty$.

All our applications (next section) are of that type. 

The gentle reader is invited to provide more examples, 
also for larger classes of functions than just rational
functions. 












\section{Applications}

The first one it the formula of Van Hamme \cite{Van_Hamme82}, see
also \cite{AnCrSi97}:
\begin{equation*}
S:=\sum_{k=1}^n\frac{(-1)^{k-1}q^{\binom {k+1}2}}{1-q^k}
\gauss nk=\sum_{k=1}^n\frac{q^k}{1-q^k}.
\end{equation*}
For that one, $f(z)=\frac{1}{z-1}$, and we must now do this computation:
\begin{align*}
S&=-\Res_{z=1}\frac{\qf qn}{\qf z{n+1} }\frac{1}{z-1}\\
&=[(z-1)^1]\frac{\qf qn}{(1-zq)\dots(1-zq^n) }\\
&=[w^1]\frac{\qf qn}{(1-q-wq)\dots(1-q^n-wq^n) }\\
&=[w^1]\frac{1}{(1-\frac{wq}{1-q})\dots (1-\frac{wq^n}{1-q^n})}\\
&=\frac{q}{1-q}+\dots+\frac{q^n}{1-q^n}.
\end{align*}

The limit (after multiplication by $1-q$) for $q\to 1$ is just
(\ref{simple}).

The next one is Uchimura's \cite{Uchimura84} generalization for
$m\in \N$ (actually it works for all real $m$ different from $0,-1,\dots, -n $):

\begin{equation*}
S:=\sum_{k=1}^n\frac{(-1)^{k-1}q^{\binom {k+1}2}}{1-q^{k+m}}
\gauss nk=\sum_{k=1}^n\frac{q^k}{1-q^k}\bigg/\gauss{k+m}{k}.
\end{equation*}
Here, $f(z)=\frac{1}{z-q^m}$, and

\begin{align*}
S&=-\Res_{z=1}\frac{\qf qn}{\qf z{n+1} }\frac{1}{z-q^m}
-\Res_{z=q^m}\frac{\qf qn}{\qf z{n+1} }\frac{1}{z-q^m}
\\
&=\frac{1}{1-q^m}-\frac{\qf qn\qf q{m-1}}{\qf q{m+n}},
\end{align*}
which is better (closed form!) than Uchimura's formula. To prove the
equivalence we use induction on $n$. For $n=0$, everything 
evaluates to zero, and the inductive step goes like this:
\begin{align*}
\sum_{k=1}^{n+1}\frac{q^k}{1-q^k}\bigg/\gauss{k+m}{k}
&=\frac{1}{1-q^m}-\frac{\qf qn\qf q{m-1}}{\qf q{m+n}}+
\frac{q^{n+1}}{1-q^{n+1}}\bigg/\gauss{n+1+m}{n+1}\\
&=\frac{1}{1-q^m}-\frac{\qf qn\qf q{m-1}}{\qf q{m+n}}+
\frac{q^{n+1}\qf qn\qf q{m}}{\qf q{n+1+m}}\\
&=\frac{1}{1-q^m}-\frac{\qf qn\qf q{m-1}}{\qf q{m+n+1}}
\Big[1-q^{n+1+m}-q^{n+1}(1-q^m)\Big]\\
&=\frac{1}{1-q^m}-\frac{\qf q{n+1}\qf q{m-1}}{\qf q{m+n+1}},\\
\end{align*}
as desired.

The limit of this formula for $q\to 1$ is
\begin{equation*}
\sum_{k=1}^n\frac{(-1)^{k-1}}{k+m}\binom{n}{k}=
\frac1m-\frac{n!(m-1)!}{(m+n)!}.
\end{equation*}







Since the case $m=0$ is well understood, let us now consider the case
$m=-M$, $M\in\{1,\dots,n\}$:

We consider the sum
\begin{equation*}
S:=\sum_{\genfrac{}{}{0pt}{}{k=1}{k\ne M}}^n
\gauss nk \frac{(-1)^{k-1}q^{\binom {k+1}2}}{1-q^{k-M}}.
\end{equation*}
The negative residue at $z=1$ is $\frac1{1-q^{m}}$ as before;
now we compute the negative residue at $z=q^{-M}$:

\begin{align*}
&-\Res_{z=q^{-M}}\frac{\qf qn}{\qf z{n+1}}\frac1{z-q^{-M}}\\
&=q^{-M}[(z-q^{-M})^1]\frac{\qf qn}{(1-z)\dots(1-zq^{M-1})
(1-zq^{M+1})\dots(1-zq^n)}\\
&=q^{-M}\qf qn[w^1]\frac{1}
{(1-q^{-M})\dots(1-q^{-1})\big(1-\frac{w}{1-q^{-M}}\big)
\dots\big(1-\frac{wq^{M-1}}{1-q^{-1}}\big)}\\
&\qquad\qquad\qquad\times\frac1{
(1-q)\dots(1-q^{n-M })
\big(1-\frac{wq^{M+1}}{1-q}\big)
\dots\big(1-\frac{wq^{n}}{1-q^{n-M}}\big)}
\\
&=q^{-M}\frac{\qf qn}{\qf{q^{-M}}{M}\qf q{n-M}}
\bigg[
\frac{1}{1-q^{-M}}+\dots+\frac{q^{M-1}}{1-q^{-1}}+
\frac{q^{M+1}}{1-q}+\dots+\frac{q^n}{1-q^{n-M}}
\bigg].
\end{align*}
Consequently, the sum is evaluated:
\begin{equation*}
S=\frac1{1-q^{-M}}+(-1)^Mq^{\binom{M+1}2}\gauss nM
\sum_{\genfrac{}{}{0pt}{}{i=0}{i\ne M}}^n
\frac{q^{i-M}}{1-q^{i-M}};
\end{equation*}
it looks nicer in this form:
\begin{equation*}
\sum_{\genfrac{}{}{0pt}{}{k=0}{k\ne M}}^n
\gauss nk \frac{(-1)^{k-1}q^{\binom {k+1}2}}{1-q^{k-M}}
=(-1)^Mq^{\binom{M+1}2}\gauss nM
\sum_{\genfrac{}{}{0pt}{}{i=0}{i\ne M}}^n
\frac{q^{i-M}}{1-q^{i-M}}.
\end{equation*}



The limit for $q\to1$ is
\begin{equation*}
\sum_{\genfrac{}{}{0pt}{}{k=0}{k\ne M}}^n
\binom nk \frac{(-1)^{k-1}}{{k-M}}=
(-1)^M\binom nM\Big(H_{n-M}-H_M\Big).
\end{equation*}





Higher powers of $(1-q^{k+m})$, like
\begin{equation*}
\sum_{k=1}^n\frac{(-1)^{k-1}q^{\binom {k+1}2}}{(1-q^{k+m})^d}\gauss nk
\end{equation*}
can also be handled (compare \cite{FlSe95} and \cite{Kirschenhofer96}
for the classical case); it involves Bell polynomials and is quite messy
but not difficult. 
























The next one is Dilcher's sum \cite{Dilcher95}:

$$
\sum_{1\le k\le n} \gauss
nk(-1)^{k-1}\frac{q^{\binom{k}{2}+mk}}{(1-q^k)^m} =\sum_{1\le i_1\le
i_2\le\dots \le i_m\le n}\frac{q^{i_1}}{1-q^{i_1}}\dots \frac{
q^{i_m}}{1-q^{i_m}}. $$

This time,
\begin{equation*}
f(z)=\frac1{(z-1)^m},
\end{equation*}
and we must compute


\begin{align*}
&-[(z-1)^{-1}]\frac1{(z-1)^m}							
\frac{(1-q)\dots(1-q^n)}{(1-z)(1-zq)\dots(1-zq^n)}\\
&=[(z-1)^{m}]\frac{(1-q)\dots(1-q^n)}{(1-zq)\dots(1-zq^n)}\\
&=[w^{m}]\frac{1}{(1-\frac{wq}{1-q})\dots(1-\frac{wq^n}{1-q^n})}\\
&=\sum_{1\le i_1\le
i_2\le\dots \le i_m\le n}\frac{q^{i_1}}{1-q^{i_1}}\dots \frac{
q^{i_m}}{1-q^{i_m}}.
\end{align*}
As Dilcher noted, the limit for $q\to1$ is

$$
\sum_{1\le k\le n} \binom
nk(-1)^{k-1}\frac{1}{k^m} =\sum_{1\le i_1\le
i_2\le\dots \le i_m\le n}\frac{1}{{i_1}\dots {i_m}}. $$

(Dilcher's formula can be inverted, which is then a $q$--version of
a formula of Hern\'andez, see \cite{Prodinger00}.)



In \cite{AnCrSi97} (Theorem 2.1) the authors are concerned with the sum
\begin{equation*}
S(m):=\sum_{k\ge1}\frac{(-1)^{k-1}q^{\binom{k+1}{2}}}{\qf qk(1-q^k)^m},
\end{equation*}
as they want to reduce it to certain simpler functions.

We introduce the finite forms

\begin{equation*}
S_n(m):=\sum_{k=1}^n
\frac{(-1)^{k-1}q^{\binom{k+1}{2}}}{(1-q^k)^m}\gauss nk,
\end{equation*}
so that $\lim_{n\to\infty}S_n(m)=S(m)$, and apply the now familiar
technique. Observe the similarity to Dilcher's sum!
We have
\begin{equation*}
f(z)=\frac{z^{m-1}}{(z-1)^m},
\end{equation*}
and compute



\begin{align*}
S_n(m)&=-[(z-1)^{-1}]\frac{z^{m-1}}{(z-1)^m}							
\frac{(1-q)\dots(1-q^n)}{(1-z)(1-zq)\dots(1-zq^n)}\\
&=[(z-1)^{m}]z^{m-1}\frac{(1-q)\dots(1-q^n)}{(1-zq)\dots(1-zq^n)}\\
&=[w^{m}](1+w)^{m-1}\frac{1}{(1-\frac{wq}{1-q})\dots(1-\frac{wq^n}{1-q^n})}\\
&=\sum_{h=0}^{m-1}
\binom{m-1}{h}
[w^{h+1}]\frac{1}{(1-\frac{wq}{1-q})\dots(1-\frac{wq^n}{1-q^n})}\\
&=\sum_{h=0}^{m-1}
\binom{m-1}{h}\sum_{1\le i_1\le
i_2\le\dots \le i_{h+1}\le n}\frac{q^{i_1}}{1-q^{i_1}}\dots \frac{
q^{i_{h+1}}}{1-q^{i_{h+1}}}.
\end{align*}
Everything is now fully explicit. 




















 
\bibliographystyle{plain}

%\bibliography{C:/texfiles2000/pro_bib}
\begin{thebibliography}{1}

\bibitem{Andrews76}
G.~Andrews.
\newblock {\em The Theory of Partitions}, volume~2 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Addison--Wesley, 1976.

\bibitem{AnCrSi97}
G.~Andrews, D.~Crippa, and K.~Simon.
\newblock $q$--series arising from the study of random graphs.
\newblock {\em SIAM Journal on Discrete Mathematics}, 10:41--56, 1997.

\bibitem{Borwein88}
P.~Borwein.
\newblock Pad\'e approximations for the $q$--elementary functions.
\newblock {\em Constructive Approximation}, 4:391--402, 1988.

\bibitem{Dilcher95}
K.~Dilcher.
\newblock Some $q$--series identities related to divisor functions.
\newblock {\em Discrete Mathematics}, 145:83--93, 1995.

\bibitem{FlSe95}
P.~Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: Finite differences and {R}ice's
  integrals.
\newblock {\em Theoretical Computer Science}, 144:101--124, 1995.

\bibitem{Van_Hamme82}
L.~Van Hamme.
\newblock Advanced problem 6407.
\newblock {\em American Mathematical Monthly}, 40:703--704, 1982.

\bibitem{Kirschenhofer96}
P.~Kirschenhofer.
\newblock A note on alternating sums.
\newblock {\em Electronic Journal of Combinatorics}, 3(2):R7, 10 pages, 1996.

\bibitem{Prodinger00}
H.~Prodinger.
\newblock A $q$--analogue of a formula of {H}ern\'andez obtained by inverting a
  result of {D}ilcher.
\newblock {\em Australasian Journal of Combinatorics}, 21:271--274, 2000.

\bibitem{Uchimura84}
K.~Uchimura.
\newblock A generalization of identities for the divisor generating function.
\newblock {\em Utilitas Mathematica}, 25:377--379, 1984.

\bibitem{Szpankowski01}
W.~Szpankowski.
\newblock Average Case Analysis of Algorithms on Sequences.
\newblock {\em John Wiley}, 2001.



\end{thebibliography}




\end{document}




