\documentclass[12pt,a4paper,reqno]{amsart}%{article}

%\RequirePackage{theorem}



\hfuzz=10pt

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

\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}

\def\U{{\cal{U}}}
\def\E{{\cal{E}}}
\def\T{{\cal{T}}}
\def\P{{\cal{P}}}
\def\a{{\bold{a}}}
\def\p{{\bold{p}}}
\def\mcirc{{\bigcirc}}
\def\dilog{\operatorname{dilog}}
\def\C{{\cal C}}
\def\P{{\cal P}}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}  
\newcommand{\gausss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{1/q}}
\def\bl{\operatorname{L}}






\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

%\section{packages}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{theorem}
%\usepackage{xspace}

\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\Prob{\mathbb{P}}

\newcommand{\Res}[1]{\mathop{\textrm{Res}}\nolimits\left\ldlm#1\right\rdlm}
                                                   % Residue
\newcommand{\ffact}[2]{#1^{\underline{#2}}}
\newcommand{\img}{\text{i}}
\newcommand{\bigOh}{\mathop{\mathcal{O}}\nolimits}  
\newcommand{\Pm}{\operatorname{pm}}
\def\bb#1{[\![#1]\!]}




%\section{preamble}
\title[A $q$--analogue of a formula of Hernandez]
{A $q$--analogue of a formula of Hernandez obtained
by inverting a result of Dilcher}

\author{Helmut Prodinger}
\thanks{This research was conducted while the author was
a host of the projet Algo at INRIA, Rocquencourt. The funding
came from the Austrian--French ``Amad\'ee'' cooperation.}


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









\begin{document}
\begin{abstract}
We prove a $q$--analogue of the formula
\begin{equation*}
\sum_{1\le k\le n} \binom nk(-1)^{k-1}\sum_{1\le i_1\le i_2\le\dots \le
i_m=k}\frac1{i_1i_2\dots i_m}= \sum_{1\le k\le n}\frac{1}{k^m} 
\end{equation*}
by inverting a formula due to Dilcher.
\end{abstract}


\maketitle

\section{The identities}

Hern\'andez in \cite{Hernandez99} proved the following identity:


\begin{equation}\label{Hernandez}
\sum_{1\le k\le n} \binom nk(-1)^{k-1}\sum_{1\le i_1\le i_2\le\dots \le
i_m=k}\frac1{i_1i_2\dots i_m}= \sum_{1\le k\le n}\frac{1}{k^m} .
\end{equation}
However this identity does not really require a proof, since we will
show that it is just an inverted form of an identity of Dilcher
\cite{Dilcher95};
\begin{equation}\label{dilcher}
\sum_{1\le k\le n} \binom nk(-1)^{k-1}\frac1{k^m}
=\sum_{1\le i_1\le i_2\le\dots \le
i_m\le n}\frac1{i_1i_2\dots i_m}.
\end{equation}






Define for $k\ge1$
$$
a_k:=-\sum_{1\le i_1\le i_2\le\dots \le
i_m=k}\frac1{i_1i_2\dots i_m}
\qquad\text{and}\qquad
b_k:=\frac1{k^m},
$$
and $a_0=b_0=0$, then the identities are

\begin{align}\label{ab_pair}\begin{split}
\sum_{0\le k\le n}\binom nk(-1)^ka_k&=\sum_{0\le k\le n}b_k,\\
\sum_{0\le k\le n}\binom nk(-1)^kb_k&=\sum_{0\le k\le n}a_k.
\end{split}\end{align}
They are {\sl inverse relations,} as can be seen by introducing ordinary
generating functions $A(z)=\sum a_nz^n$ and
$B(z)=\sum b_nz^n$. Then they are

\begin{align*}
\frac1{1-z}A\Big(\frac z{z-1}\Big)&=\frac1{1-z}B(z),\\
\frac1{1-z}B\Big(\frac z{z-1}\Big)&=\frac1{1-z}A( z).
\end{align*}
However

$$
w=\frac z{z-1} \longleftrightarrow z=\frac w{w-1},
$$
and the proof is finished. An alternative argument that will be useful
in the sequel when we do the $q$--analogue, is as follows.
We assume $a_0=b_0=0$ and 
take differences in (\ref{ab_pair}) of the lines indexed with $n$ resp.
$n-1$; then we have to prove that

\begin{equation*}
b_n=\sum_{1\le k\le n}\binom {n-1}{k-1}(-1)^ka_k\quad\Longleftrightarrow 
\quad
a_n=\sum_{1\le k\le n}\binom {n-1}{k-1}(-1)^kb_k.
\end{equation*}


Now in this form this is a traditional inverse relation; see e.~g. \cite{Riordan68}.
An explicit argument will follow in the next section for the $q$--instance.




We note that
Dilcher's sum appears also in disguised form in \cite{FlSe95}. 


\section{A $q$--analogue}

Dilcher's formula (\ref{dilcher}) was only a corollary of his elegant
 $q$--version;






$$
\sum_{1\le k\le n} \gauss
nk(-1)^{k-1}\frac{q^{\binom{k+1}{2}+(m-1)k}}{(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}}. $$
Here, $\gauss nk$ denotes the Gaussian polynomial
\begin{equation*}
\gauss nk
=\frac{(q;q)_n}{(q;q)_k(q;q)_{n-k}}
\end{equation*}


with
\begin{equation*}
(x;q)_n:=(1-x)(1-xq)\dots(1-xq^{n-1}).
\end{equation*}

Apart from Dilcher's paper \cite{Dilcher95}, the article
\cite{AnCrSi97} is also of some relevance in this context.












Therefore it is a natural 
question to find a 
$q$--analogue of Hern\'andez' formula, or, what amount to the same,
to find the appropriate inverse relations for the $q$--analogues.

We state them in the following lemma.



\begin{lemma} Assume that $a_0=b_0=0$, then
\begin{align}\label{qab_pair}\begin{split}
\sum_{1\le k\le n}b_k&=\sum_{1\le k\le n}\gauss nk(-1)^kq^{\binom k2}a_k, \\
\sum_{1\le k\le n}q^{-k}a_k&=\sum_{1\le k\le n}\gauss nk(-1)^kq^{-kn+\binom k2}b_k.
\end{split}\end{align}
\end{lemma}

\begin{proof} First note that it is much easier to prove this than to find
it (it took me a few hours, but I am not too experienced).

After  a first version of this note was circulated, O.~Warnaar kindly informed
me that this lemma would follow from results in \cite{GeSt83}. Nevertheless, 
it is perhaps instructive to provide a direct and independent proof. 

Taking again differences in (\ref{qab_pair}), we have to prove that 

\begin{equation}\label{q_equivalence}
b_n=\sum_{1\le k\le n}\gauss {n-1}{k-1}(-1)^kq^{\binom k2}
a_k\quad\Longleftrightarrow 
\quad
a_n=\sum_{1\le k\le n}\gauss {n-1}{k-1}(-1)^kq^{-(n-1)k+\binom k2}b_k.
\end{equation}




Now

\begin{align*}
\sum_{1\le k\le n}&\gauss {n-1}{k-1}(-1)^kq^{-(n-1)k+\binom k2}b_k\\
&=\sum_{1\le k\le n}\gauss {n-1}{k-1}(-1)^kq^{-(n-1)k+\binom k2}
\sum_{1\le l\le k}\gauss {k-1}{l-1}(-1)^lq^{\binom l2}a_l\\
&=\sum_{1\le l\le n}(-1)^lq^{\binom l2}a_l\sum_{l\le k\le n}
\gauss {n-1}{k-1}\gauss {k-1}{l-1}(-1)^kq^{-(n-1)k+\binom k2}=a_n,
\end{align*}
since for $l<n$ the inner sum is


\begin{align*}
\sum_{l\le k\le n}
&\gauss {n-1}{k-1}\gauss {k-1}{l-1}(-1)^kq^{-(n-1)k+\binom k2}\\
&=(-1)^lq^{-(n-1)l+\binom l2}\gauss{n-1}{l-1}
\sum_{0\le m\le n-l}(-1)^m\big(q^{-(n-l-1)}\big)^mq^{\binom m2}
\gauss{n-l}{m}\\
&=(-1)^lq^{-(n-1)l+\binom l2}\gauss{n-1}{l-1}
\big(q^{-(n-l-1)};q\big)_{n-l}=0;
\end{align*}
here we have used
 the following version of the 
$q$--binomial theorem (see e.~g. \cite{Andrews76}):
\begin{align*}
\sum_{0\le m\le n}(-1)^mz^mq^{\binom m2}\gauss{n}{m}=
(z;q)_n.
\end{align*}


The other direction is very similar. (For our application
``Dilcher'' $\Rightarrow $ ``Hern\'andez'' we would need only one implication.)
\end{proof}

We would like to remark that an alternative formulation can be given
in terms of  matrices of {\sl connection coefficients.}



This can be done in terms of the original formul{\ae} 
(\ref{qab_pair}), but looks much nicer when referring to 
(\ref{q_equivalence}):











Define matrices

\begin{align*}
T:=\left[\gauss {n-1}{k-1}(-1)^kq^{\binom {k}2}\right]_{n,k},
\qquad
U:=\left[\gauss {n-1}{k-1}(-1)^kq^{-(n-1)k+\binom {k}2}\right]_{n,k},
\end{align*}
then
\begin{equation*}
TU=I.
\end{equation*}





\begin{theorem}{\rm [$q$--analogue of Hern\'andez' formula]}
\begin{align*}
\sum_{1\le k \le n}\gauss nk (-1)^{k-1}q^{-kn+\binom k2}
\sum_{1\le i_1\le
i_2\le\dots \le i_m=k}\frac{q^{i_1}}{1-q^{i_1}}\dots \frac{
q^{i_m}}{1-q^{i_m}}=
\sum_{1\le k \le n}\frac{q^{k(m-1)}}{(1-q^k)^m}.
\end{align*}






\end{theorem}

{\bf Acknowledgment.} The presentation has gained much by
the comments of an insightful referee.

\bibliographystyle{plain}
\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{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{GeSt83}
I.~Gessel and D.~Stanton.
\newblock Applications of $q$--{L}agrange inversion to basic hypergeometric
  series.
\newblock {\em Transactions of the American Mathematical Society},
  227:173--201, 1983.

\bibitem{Hernandez99}
V.~Hern\'andez.
\newblock Solution {IV} of problem 10490 (a reciprocal summation identity).
\newblock {\em American Mathematical Monthly}, 106:589--590, 1999.

\bibitem{Riordan68}
J.~Riordan.
\newblock {\em Combinatorial Identities}.
\newblock John Wiley, 1968.

\end{thebibliography}

%\bibliography{C:/texfiles/pro_bib}

\end{document}
