\documentclass[12pt]{article}
%\usepackage{amsmath, epsfig, cite, amssymb, amsfonts,latexsym}
\usepackage{amssymb,amsfonts,amsmath, psfrag,eepic}


\setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\newcommand{\qed}{{\hfill\rule{4pt}{7pt}}}

\def\MX{\mathbb{X}}
\def\MY{\mathbb{Y}}
\def\MZ{\mathbb{Z}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{ex}{Example}[section]
\newtheorem{defi}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}

\def\pf{\noindent {\it Proof.} }
\def\makefootline{\baselineskip=24pt
    \iftitle \global\titlefalse
\footline={\hss\pagfont\folio\hss} \else\footline={\hfil}
    \fi    \line{\the\footline}}

\newcommand{\newsection}[1]{\section{#1} \setcounter{equation}{0}}

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thesection}{\arabic{section}.}
\renewcommand{\thethm}{\arabic{section}.\arabic{thm}}

\makeatletter \@addtoreset{equation}{section} \makeatother

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
  {\footbf 12} (2005), \#R38\hfil\footrm\thepage}}
\makeatother \pagestyle{plain}

\begin{document}

\begin{center}
{\Large  $q$-Identities related to overpartitions and divisor
functions}
\end{center}


 \vspace{0.3cm}
 \begin{center}
   {\bf Amy M. Fu}\\
   Center for Combinatorics, LPMC\\
   Nankai University, Tianjin 300071, P.R. China\\
   Email: fmu@eyou.com
  \end{center}
 \begin{center}
  {\bf Alain Lascoux}\\
  Nankai University, Tianjin 300071, P.R. China\\
  Email: Alain.Lascoux@univ-mlv.fr\\
  CNRS, IGM Universit\'e  de
  Marne-la-Vall\'ee\\
  77454 Marne-la-Vall\'ee Cedex, France\\
  \end{center}

  \vspace{1cm}

\noindent{\bf Abstract.} We generalize and prove two conjectures
of Corteel and Lovejoy related to overpartitions and divisor
functions.\\


\noindent{\small 
Submitted: Apr 29, 2004; Accepted: Jun 16, 2005; Published: Aug 5, 2005\\
\small MR Subject Classifications: 11B65, 41A05}


\section{Introduction}

In this paper, for any pair positive integers $m, n$, we prove the
following two identities:
\begin{multline}\label{EQ1}
\sum_{i=1}^n{n \brack
i}\frac{(-1)^{i-1}(x+1)\cdots(x+q^{i-1})}{(1-q^i)^m}q^{mi}
\\=\sum_{i=1}^{n}\frac{(-1)^{i-1}(x^i-(-1)^i)}{1-q^i}q^i
 \sum_{i\leq i_2\leq \cdots\leq i_m\leq
n}\frac{q^{\sum_{j=2}^mi_j}}{\prod_{j=2}^m(1-q^{i_j})},
\end{multline}

\begin{equation}\label{EQ2}
\frac{(z;q)_{n+1}}{(q;q)_n}\sum_{i=0}^n {n \brack
i}\frac{(-1)^{i-1}(x+1)\cdots(x+q^{i-1})}{1-zq^i}q^i
=\sum_{i=0}^n(-1)^{i-1}\frac{(z;q)_i}{(q;q)_i}x^iq^i,
\end{equation}
using the classical notations $(z;q)_i=(1-z)\cdots(1-zq^{i-1})$,
and $\displaystyle{{n \brack
i}}=\frac{(q;q)_n}{(q;q)_i(q;q)_{n-i}}$.

In the next section, we shall show that (\ref{EQ1}) and
(\ref{EQ2}) can be obtained from the Newton interpolation in
points $\{-1,-q,-q^2,\ldots\,\}$, using the complete symmetric
function in the variables $\{q/(1-q), q^2/(1-q^2), \ldots\,\}$.

Given $\MX=\{x_1, x_2, \ldots\}$, Newton gave the following
interpolation formula, for any function $f(x)$:
\begin{eqnarray*}
f(x)=f(x_1)+f\partial_1(x-x_1)+f\partial_1\partial_2(x-x_1)(x-x_2)+\cdots,
\end{eqnarray*}
where $\partial_i$, acting on its left, is defined by
$$
f(x_1,\ldots,x_i,x_{i+1},\ldots)\partial_i=\frac{f(\ldots,x_i,x_{i+1},\ldots)-f(\ldots,x_{i+1},x_i,\ldots)}{x_i-x_{i+1}}.
$$

Taking $f(x)=x^n$, we have,
\begin{equation}\label{Com}
x_1^n \partial_1\cdots \partial_i=h_{n-i}(x_1,x_2,\ldots,x_{i+1}),
\end{equation}
where $h_k$ is the complete symmetric function of degree $k$
defined by
$$
h_{k}(x_1,x_2,\ldots, x_n)=\sum_{1 \leq i_1 \leq i_2 \leq \cdots
\leq i_k \leq n}x_{i_1}x_{i_2}\cdots x_{i_k}.
$$
Recall the following properties of $h_k$:
\begin{itemize}
\item[1.] Given an alphabet $\MX$, the generating function of
$h_k$ is
\begin{equation}\label{Gene}
\sum_{k=0}^{\infty}h_{k}(\MX)t^k=\frac{1}{\prod_{x \in
\MX}(1-xt)}.
\end{equation}

In particular, Take $\MX=\{z,zq,zq^2,\ldots\}$,
$\MX_n=\{z,zq,zq^2,\ldots,zq^{n-1}\}$. We have
$$
\sum_{k=0}^{\infty}h_{k}(z,zq,zq^2,\ldots)t^k=\frac{1}{\prod_{i=0}^\infty(1-tzq^i)},
$$
and
$$
\sum_{k=0}^\infty
h_{k}(z,zq,zq^2,\ldots,zq^{n-1})t^k=\frac{1}{\prod_{i=0}^{n-1}(1-tzq^i)}.
$$

In consequence of  the $q$-binomial theorem
$$
\sum_{i=0}^\infty \frac{(a;q)_i}{(q;q)_i} t^i
=\frac{(at;q)_\infty}{(t;q)_\infty},
$$
it follows that
\begin{equation}\label{Add}
h_{k}(z,zq,zq^2,\ldots)=\frac{z^k}{(q;q)_k}.
\end{equation}

Putting $a=q^n$ in the $q$-binomial theorem gives
$$
\sum_{i=0}^\infty {n+i-1 \brack i} t^i =\frac{1}{(t;q)_n}.
$$
Thus we have
\begin{equation}\label{add2}
h_{k}(z,zq,zq^2,\ldots,zq^{n-1})={n+k-1 \brack k}z^k.
\end{equation}

 \item[2.] More generally, given two alphabets $\MX$ and $\MY$,  the generating functions of $h_k(\MX+\MY)$
and $h_k(\MX-\MY)$ are
\begin{eqnarray}
\sum_{k=0}^{\infty}h_k(\MX+\MY)t^k &=& \frac{1}{\prod_{x \in
\MX}(1-xt)\prod_{y \in \MY}(1-yt)}, \nonumber\\
\sum_{k=0}^{\infty}h_k(\MX-\MY)t^k &=& \frac{\prod_{y \in
\MY}(1-yt)}{\prod_{x \in \MX}(1-xt)}\label{gened}.
\end{eqnarray}

As a consequence, one has
\begin{equation}\label{expan}
h_n(\MX + \MY)=\sum_{k=0}^n h_k(\MX)h_{n-k}(\MY).
\end{equation}


 \item[3.] Given $\{x_1,x_2,\ldots,x_n\}$, and a positive integer $m$, we
 have
\begin{equation}\label{Pas}
\sum_{i=1}^n x_i h_{m-1}(x_i, x_{i+1},\ldots,
x_{n})=h_m(x_1,x_2,\ldots,x_n).
\end{equation}
\end{itemize}

Taking  $\MX=\{-1,-q,-q^2, \ldots\,\}$, it is easy to check from
(\ref{Com}) and (\ref{add2}):
$$
x_1^n\partial_1\cdots\partial_i=h_{n-i}(-1,-q,\ldots,-q^{i})=(-1)^{n-i}{n
\brack i}.
$$

\section{Proofs of (\ref{EQ1}) and (\ref{EQ2})}

 The Gauss polynomials $\displaystyle{{n \brack k}}$ satisfy the following recursion
 (cf.\cite{Andrews1}):
\begin{equation}\label{Pascal2}
\sum_{j=0}^n{m+j \brack m}q^j={n+m+1 \brack m+1}.
\end{equation}

In this paper, we need the following more general relations.

\begin{lem} \label{LEM}
Let $k$, $m$ and $n$ be nonnegative integers. Then we have the
following formulas:
\begin{equation}\label{Pascal1}
\sum_{i=k}^n{i \brack k}\frac{q^i}{1-q^i}\sum_{i \leq i_2 \leq
\cdots \leq i_m \leq n}\frac{q^{\sum_{j=2}^m
i_j}}{\prod_{j=2}^m(1-q^{i_j})}={n \brack k}
\frac{q^{km}}{(1-q^k)^m},
\end{equation}
and
\begin{equation}\label{Pasz}
\sum_{i=0}^n\frac{(z;q)_i}{(q;q)_i}q^i=\frac{(zq;q)_n}{(q;q)_n}.
\end{equation}
\end{lem}


\pf

Taking $\MX=\{1,q,\ldots, q^l\}$ and
$\MY=\{q^{l+1},q^{l+2},\ldots\}$, we obtain from (\ref{Add}),
(\ref{add2}) and (\ref{expan}):
\begin{equation}\label{Aqq1}
\frac{1}{(q;q)_n}=h_n(\MX+\MY)=\sum_{i=0}^n
h_i(\MY)h_{n-i}(\MX)=\sum_{i=0}^n\frac{1}{(q;q)_i}{n-i+l \brack
l}q^{(l+1)i}.
\end{equation}

Letting $f(m)$ be the left side of (\ref{Pascal1}), we have
\begin{eqnarray*}
\sum_{m=1}^{\infty}f(m)z^m&=&\sum_{m=1}^{\infty}\sum_{i=k}^n{i
\brack k}\frac{q^i}{1-q^i}h_{m-1}\left(\frac{q^i}{1-q^i},
\frac{q^{i+1}}{1-q^{i+1}},\ldots, \frac{q^n}{1-q^n}\right)z^m\\
&\overset{(\ref{Gene})}{=}&z\sum_{i=k}^n{i \brack
k}\frac{q^i}{1-q^i}\frac{1}{(1-q^iz/(1-q^i))\cdots(1-q^nz/(1-q^n))}\\
&=&z\sum_{i=k}^n{i \brack
k}\frac{q^i}{1-q^i}\sum_{l=0}^{\infty}(q^i;q)_{n-i+1}{n-i+l \brack l}(q^i(1+z))^l\\
&=&z{n \brack
k}\sum_{i=k}^n\frac{(q;q)_{n-k}}{(q;q)_{i-k}}\sum_{l=0}^{\infty}{n-i+l
\brack l}q^{(l+1)i}\sum_{m=0}^l\binom{l}{m}z^m\\
%\end{eqnarray*}
%\begin{eqnarray*}
%\phantom{\sum_{m=1}^{\infty}f(m)z^m}
&=&z{n \brack
k}\sum_{l=0}^{\infty}\sum_{m=0}^l\binom{l}{m}z^m\sum_{i=k}^n\frac{(q;q)_{n-k}}{(q;q)_{i-k}}{n-i+l
\brack l}q^{(l+1)i}\\
&\overset{(\ref{Aqq1})}{=}&{n \brack
k}\sum_{l=0}^{\infty}\sum_{m=0}^l\binom{l}{m}z^{m+1}q^{(l+1)k}\\
&=&{n \brack k}\frac{q^{k}z}{1-q^k(1+z)}\\
&=&\sum_{m=1}^{\infty}{n \brack k} \frac{q^{km}}{(1-q^k)^m}z^m.
\end{eqnarray*}

Taking $\MX=\{1\}$, $\MY=\{q,q^2,\ldots\,\}$ and $\MZ=\{zq, zq^2,
\ldots\,\}$, from (\ref{gened}), (\ref{expan}) and the $q$-binomial
theorem, we get the proof of (\ref{Pasz}):
\begin{multline*}
\frac{(zq;q)_n}{(q;q)_n}=h_{n}((\MX+\MY)-\MZ)\\=h_{n}(\MX+(\MY-\MZ))
=\sum_{i=0}^n
h_{i}(\MY-\MZ)h_{n-i}(\MX)=\sum_{i=0}^n\frac{(z;q)_i}{(q;q)_i}q^i.
\end{multline*}



\qed


Taking
\begin{eqnarray*}
f(x)&=&\sum_{i=1}^{n}\frac{(-1)^{i-1}(x^i-(-1)^i)}{1-q^i}q^i
\sum_{i\leq i_2\leq\cdots\leq i_m\leq
n}\frac{q^{\sum_{j=2}^mi_j}}{\prod_{j=2}^m(1-q^{i_j})},
\end{eqnarray*}
and
$$
\MX=\{-1,-q,-q^2,\ldots\,\},
$$
we have,
\begin{eqnarray*}
f(x)&=&f(x_1)+\sum_{k=1}^n f(x_1)\partial_1\cdots\partial_k
\, (x+1)\cdots(x+q^{k-1})\\
&=&\sum_{k=1}^n\sum_{i=k}^n(-1)^{k-1}{i \brack
k}\frac{q^i}{1-q^i}\sum_{i\leq i_2\leq\cdots\leq i_m\leq
n}\frac{q^{\sum_{j=2}^mi_j}}{\prod_{j=2}^m(1-q^{i_j})}(x+1)\cdots(x+q^{k-1})\\
&=&\sum_{k=1}^n(-1)^{k-1}(x+1)\cdots(x+q^{k-1})\sum_{i=k}^n{i
\brack k}\frac{q^i}{1-q^i}\sum_{i\leq i_2\leq\cdots\leq i_m\leq
n}\frac{q^{\sum_{j=2}^mi_j}}{\prod_{j=2}^m(1-q^{i_j})}\\
&=&\sum_{k=1}^n{n \brack
k}\frac{(-1)^{k-1}(x+1)\cdots(x+q^{k-1})}{(1-q^k)^m}q^{mk},
\end{eqnarray*}
as stated in (\ref{EQ1}). \qed


Taking
\begin{eqnarray*}
f(x)=\sum_{i=0}^{n}(-1)^{i-1}\frac{(z;q)_i}{(q;q)_i}x^{i}q^i,
\quad  \text{and} \quad  \MX=\{-1,-q,-q^2, \ldots\,\},
\end{eqnarray*}
we have,
\begin{eqnarray*}
f(x)&=&\sum_{k=0}^nf(x_1)\partial_1\cdots\partial_k \, (x+1)\cdots(x+q^{k-1})\\
&=&\sum_{k=0}^n (x+1)\cdots(x+q^{k-1}) \sum_{i=k}^n(-1)^{k-1}{i
\brack k}\frac{(z;q)_i}{(q;q)_i}q^i\\
&=&\sum_{k=0}^n(-1)^{k-1}(x+1)\cdots(x+q^{k-1})q^k\frac{(z;q)_k}{(q;q)_k}
\sum_{i=k}^n\frac{(zq^k;q)_{i-k}}{(q;q)_{i-k}}q^{i-k}\\
&=&\sum_{k=0}^n(-1)^{k-1}(x+1)\cdots(x+q^{k-1})q^k\frac{(z;q)_k}{(q;q)_k}\frac{(zq^{k+1};q)_{n-k}}{(q;q)_{n-k}}\\
&=&\frac{(z;q)_{n+1}}{(q;q)_n}\sum_{k=0}^n{n \brack
k}\frac{(-1)^{k-1}(x+1)\cdots(x+q^{k-1})}{1-zq^k}q^k,
\end{eqnarray*}
which implies (\ref{EQ2}). \qed

\section{Special Cases}

In their study of overpartitions \cite[Theorem 4.4]{CorLove},
Corteel and Lovejoy obtained a combinatorial interpretation of the
identity:
\begin{eqnarray*}
\sum_{i=1}^{\infty}(-1)^{i-1}\frac{(-1;q)_i}{(q;q)_i}\frac{q^i}{1-q^i}
=\sum_{i=1}^{\infty}\frac{2q^{2i-1}}{1-q^{2i-1}}=\sum_{i=1}^{\infty}\frac{2q^i}{1-q^{2i}},
\end{eqnarray*}
and formulated, as conjectures, the following finite forms
(private communication):
\begin{multline}\label{Conje1}
\sum_{i=1}^{2n-1}{2n-1 \brack
i}\frac{(-1)^{i-1}(-1;q)_i}{(1-q^i)^m}q^{mi}\\
=\sum_{i=1}^n\frac{2q^{2i-1}}{1-q^{2i-1}}\sum_{2i-1\leq
i_2\leq\cdots\leq i_m\leq
2n-1}\frac{q^{\sum_{j=2}^mi_j}}{\prod_{j=2}^m(1-q^{i_j})},
\end{multline}
and
\begin{equation}\label{Conje2}
\sum_{i=1}^{2n}{2n \brack
i}\frac{(-1)^{i-1}(-1;q)_i}{1-q^{i+2}}q^i=\sum_{i=1}^{n}\frac{2q^{2i-1}(1-q)}{(1+q^2)(1-q^{2i-1})(1-q^{2i+1})}.
\end{equation}

In fact, (\ref{Conje1}) is the special case of (\ref{EQ1}) when
$x=1$.  Taking $x=1$, $z=q^2$, (\ref{EQ2}) can be deduced to
(\ref{Conje2}).


The case $x=0$, $m=1$ of (\ref{EQ1}) is due to Van Hamme
\cite{Hamme} (see also \cite{Andrews}, \cite{FuLa},
\cite{Uchimura}):
\begin{eqnarray*}
\sum_{i=1}^n{n \brack
i}\frac{(-1)^{i-1}q^{\binom{i+1}{2}}}{1-q^i}=\sum_{i=1}^n\frac{q^i}{1-q^i}.
\end{eqnarray*}

Taking $x=0$, and (\ref{Pas}), we get the formula of Dilcher
\cite{Dilcher}:
\begin{eqnarray*}
\sum_{i=1}^n{n \brack i}(-1)^{i-1}\frac{q^{{i \choose
2}+mi}}{(1-q^i)^m}= \sum_{1\leq i_1\leq i_2\leq \cdots \leq i_m
\leq n}\frac{q^{i_1}}{1-q^{i_1}}\cdots\frac{q^{i_m}}{1-q^{i_m}}.
\end{eqnarray*}

When $x=0$ and $z=q^m$ in (\ref{EQ2}), we get Uchimura's identity
\cite{Uchimura2}:
\begin{eqnarray*}
\sum_{i=1}^n{n \brack
i}\frac{(-1)^{i-1}q^{\binom{i+2}{2}}}{1-q^{i+m}}=\sum_{i=1}^n
\frac{q^i}{1-q^i}\left/ {i+m \brack i}.\right.
\end{eqnarray*}

Note added in proof: Two different approaches to prove (\ref{EQ1})
and (\ref{EQ2}) were recently given by Prodinger \cite{Prodinger}
and Zeng \cite{Zeng}.

\vskip 5mm \noindent{\bf Acknowledgments.}

This work was done under the auspices of the 973 Project on
 Mathematical Mechanization of the Ministry of Science and Technology, and the
National Science Foundation of China. The second author is
partially supported by the EC's IHRP Program, within the Research
Training Network ``Algebraic Combinatorics in Europe'', grant
HPRN-CT-2001-00272.

\begin{thebibliography}{9}
\bibitem{Andrews1} G. E. Andrews, The Theory of Partitions,
Cambridge University Press, (1984).
\bibitem{Andrews} G. E. Andrews, K. Uchimura, Identities in
combinatorics IV: differential and harmonic numbers, Utilitas
Math., 28(1985) 265--269.
\bibitem{CorLove} S. Corteel and J. Lovejoy, Overpartitions,
Trans.  Amer. Math. Soc,  356(2004) 1623--1635.
\bibitem{Dilcher} K. Dilcher, Some $q$-series identities related
to divisor functions, Discrete Math., 145(1995) 83--93.
\bibitem{FuLa} A. M. Fu and A. Lascoux, $q$-identities from
Lagrange and Newton interpolation, Adv. Appl. Math., 31(2003)
527--531.
\bibitem{Hamme} L. Van Hamme, Advanced problem 6407, Amer. Math.
Monthly, 40(1982) 703--704.
\bibitem{Prodinger} H. Prodinger, $q$-identities of Fu and Lascoux
proved by the $q$-Rice
formula,  Quaestiones Math., 27(2004) 391--395.
\bibitem{Uchimura} K. Uchimura, An identity for the divisor
generating function arising from sorting theory, J. Combin.
Theory, Series A, 31(1981) 131--135.
\bibitem{Uchimura2} K. Uchimura, A generalization of identities
for the divisor generating function, Utilitas Math., 25(1984)
377--379.
\bibitem{Zeng}J. Zeng, On some $q$-identities related to divisor
functions, Adv. Appl. Math., 34(2005) 313--315.

  \end{thebibliography}

\end{document}
