\documentclass{dmtcs}
\usepackage{amssymb,amsmath,amsthm,latexsym}


%\parindent0pt
\renewcommand{\theequation}{\mbox{\arabic{section}.\arabic{equation}}}

\newtheorem{theorem}{Theorem}[section]

\theoremstyle{remark}
\newtheorem*{remark}{Remark}


%\renewcommand{\baselinestretch}{2}


\begin{document}
%\newbox\email
%\setbox\email\hbox{\small{\it e-mail}: {\tt Johann.Cigler@univie.ac.at}}




\author{Peter Paule\addressmark{1}\thanks{Partially supported by SFB
grant F1305   of the Austrian FWF.}{\ }
  \and Helmut Prodinger\addressmark{2}\thanks{The research was started when this
author visited the RISC in 2002. Partially supported by NRF
grant 2053748.}{\ }}
\title[Fountains, histograms, and ${q}$--identities]
{Fountains, histograms, and $\boldsymbol{q}$--identities}


\address{\addressmark{1}Research Institute for Symbolic Computation,
Johannes Kepler University Linz,
A-4040 Linz, Austria\\
\hbox{\small{\it e-mail}: {\tt Peter.Paule@risc.uni-linz.ac.at}} \\
\hbox{\small{\it Url}: {\tt http://www.risc.uni-linz.ac.at/research/combinat/}}

\addressmark{2}
The John Knopfmacher Centre for Applicable Analysis and Number Theory,
 School of Mathematics,
University of the Witwatersrand, P.~O. Wits,
2050 Johannesburg, South Africa\\
\hbox{\small{\it e-mail}: {\tt helmut@maths.wits.ac.za}} \\
\hbox{\small{\it Url}: {\tt http://www.wits.ac.za/helmut/}}
}

%\address{Institut f\"ur Mathematik, Universit\"at Wien,
%A-1090 Wien, Strudlhofgasse 4, Austria.\newline
%\unhbox\email}












\received{---}
\revised{---}
\accepted{---}


\keywords{$q$--identities, fountains, histograms, Schur polynomials}










\maketitle
\begin{abstract}
We solve the recursion $S_n=S_{n-1}-q^nS_{n-p}$, both, explicitly, and
in the limit for $n\to\infty$, proving in this way a formula due to
Merlini and Sprugnoli. It is also discussed how computer algebra
could be applied. 
\end{abstract}






\allowdisplaybreaks

\hfuzz=10pt


\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\newtheorem{ncor}{Corollary}

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

\def\aK{a^{\textrm{[FB1]}}}
\def\kK{\kappa^{\textrm{[FB1]}}}
\def\ak{a^{\textrm{[FB2]}}}
\def\kk{\kappa^{\textrm{[FB2]}}}
\def\kt{\tilde{\kappa}^{\textrm{[FB2]}}}
\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\la{\lambda}
\def\mcirc{{\bigcirc}}
\def\dilog{\operatorname{dilog}}
\def\C{{\cal C}}
\def\P{{\cal P}}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0
pt}{}{#1}{#2}}  
\newcommand{\gausss}[2]{\genfrac{[}{]}{
0pt}{}{#1}{#2}_{1/q}}
\def\bl{\operatorname{L}}
\newcommand{\qf}[1]{(q)_{#1}}  
\newcommand{\qff}[2]{(#1)_{#2}}  






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

%\section{packages}
%\usepackage{theorem}
%\usepackage{xspace}

\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip

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





\def\Prob{\mathbb{P}}

\newcommand{\Res}[1]{\mathop{\textrm{Re
s}}\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]\!]}
\def\a{\alpha}
\def\b{\beta}


%\section{preamble}


\section{Fountains and histograms}

Merlini and Sprugnoli \cite{MeSp02} discuss \emph{fountains}
and \emph{histograms}; for the reader's convenience, we review a
few key issues here.

A \emph{fountain with $n$ coins} is an arrangement of $n$ coins
in rows such that each coin in a higher row touches exactly two
coins in the next lower row.

A \emph{$p$-histogram} is a sequence of columns in which the 
height of the $(j+1)$st column is at most $k+p$, if $k$ is the height
of column $j$; the first column has height $r$, with $1\le r\le p$.

It can be shown that the enumeration of coins in a fountain is equivalent 
with the enumeration of \hbox{$1$-histograms.} The paper
\cite{MeSp02} addresses the enumeration of $p$-histograms with respect to
area (=number of cells). 
Let $f_n^{[p]}$ be the number $p$-histograms with area $n$ and 
$F^{[p]}(q)$ the corresponding generating function
$F^{[p]}(q)=\sum_nf_n^{[p]}q^n$. The authors of 
\cite{MeSp02} use two different approaches: one produces the answer in the form
\begin{equation*}
F^{[p]}(q)=\lim_{m\to\infty}\frac{D_m}{E_m},
\end{equation*}
with some polynomials $D_m$, $E_m$ defined in the next section, and the 
other gives it as
\begin{equation*}
F^{[p]}(q)=
\sum_{k\ge0}\frac{(-1)^kq^{p\binom{k+1}{2}}}{(1-q)\dots(1-q^k)}\bigg/
\sum_{k\ge0}\frac{(-1)^kq^{k+p\binom{k}{2}}}{(1-q)\dots(1-q^k)}.
\end{equation*}

According to \cite{Merlini02}, it would be nice to have a direct argument that
these two answers coincide. This is the subject of the present note.




\section{Generalized Schur polynomials}

The polynomials mentioned in the introduction are for fixed $p\ge1$
 defined  as follows:
\begin{align*}
E_n&=E_{n-1}-q^nE_{n-p},\quad n\ge p,\qquad E_0=\cdots =E_{p-1}=1,\\
D_n&=D_{n-1}-q^nD_{n-p},\quad n\ge p, \qquad D_i=1-\sum_{j=1}^iq^j,
\ i=0,\dots,p-1.
\end{align*}
They can be compared with the classical Schur polynomials
\cite{Schur17}, which occur
for $p=2$ and $q=-1$.
Then Merlini and Sprugnoli want a direct proof of the formul{\ae}
\begin{align*}
E_\infty&:=\lim_{n\to\infty}E_n=\sum_{k\ge0}\frac{(-1)^kq^{p\binom{k+1}{2}}}
{(1-q)\dots(1-q^k)},\\
D_\infty&:=\lim_{n\to\infty}D_n=\sum_{k\ge0}\frac{(-1)^kq^{k+p\binom{k}{2}}}
{(1-q)\dots(1-q^k)}.
\end{align*}

We will not only achieve that but actually derive \emph{explicit}
expressions for these polynomials!

It should be mentioned that Cigler \cite{Cigler03} developed independently
a combinatorial method to deal with  recursions as ours, but also more
general ones.
\medskip

Let us study the generic recursion
\begin{equation*}
S_n=S_{n-1}+tq^{n-p}S_{n-p},
\end{equation*}
with unspecified initial values $S_0,\dots,S_{p-1}$.
For $p=2$, these polynomials were studied by Andrews (and others)
in the context of \emph{Schur polynomials}, see \cite{Andrews02}.

We will use standard notation from $q$--calculus, see \cite{AnAsRo99}:
\begin{equation*}
\qff xn=(1-x)(1-xq)\dots(1-xq^{n-1}), \qquad \gauss nk=\frac{\qf n}{\qf k\qf{n-k}}.
\end{equation*}
It will be convenient to define $\gauss nk=0$ for $n<0$ or $k>n$.

Now we will proceed as in \cite{AnAsRo99} and consider noncommutative
variables $x$, $\eta$, such that $x\eta=q\eta x$; all other variables
commute.
\begin{lemma}
\begin{equation*}
\big(x+x^p\eta\big)^n=\sum_{k=0}^n\gauss nk q^{p\binom n2-pnk+p\binom{k+1}2}
x^{k+p(n-k)}\eta^{n-k}.
\end{equation*}
\end{lemma}
\textbf{Proof.} We write 
\begin{equation*}
\big(x+x^p\eta\big)^n=\sum_{k=0}^na_{n,k}x^{k+p(n-k)}\eta^{n-k},
\end{equation*}
and $\big(x+x^p\eta\big)^{n+1}=\big(x+x^p\eta\big)^n\big(x+x^p\eta\big)$
resp. as
$\big(x+x^p\eta\big)^{n+1}=\big(x+x^p\eta\big)\big(x+x^p\eta\big)^n$, 
compare coefficients, and get the recursions
\begin{align*}
a_{n+1,k}&=a_{n,k-1}+a_{n,k}q^{k+p(n-k)},\\*
a_{n+1,k}&=a_{n,k-1}q^{n+1-k}+a_{n,k}q^{p(n-k)}.
\end{align*}
 From this we derive, taking differences,
\begin{equation*}
a_{n,k}=\frac{1-q^{n+1-k}}{1-q^k}q^{-p(n-k)}a_{n,k-1}.
\end{equation*}
The result follows from iteration by noting that
$a_{n,0}=q^{p\binom n2}$. \qed

Of course we also have
\begin{equation*}
\big(x+tx^p\eta\big)^n=\sum_{k=0}^n\gauss nk q^{p\binom n2-pnk+p\binom{k+1}2}
x^{k+p(n-k)}t^{n-k}\eta^{n-k}.
\end{equation*}



Now we derive the generating function for 
\begin{equation*}
F(x)=\sum_{n\ge0}S_nx^n;
\end{equation*}
the following procedure is inspired by \cite{Andrews02}. Note
that we can alternatively view $\eta$ as an operator, defined
by $\eta f(x)=f(qx)$. Cigler worked also much with this technique
\cite{Cigler81, Cigler03}. 
We find
\begin{equation*}
\sum_{n\ge p}S_nx^n=\sum_{n\ge p}S_{n-1}x^n+
\sum_{n\ge p}tq^{n-p}S_{n-p}x^n=
x\sum_{n\ge p-1}S_{n}x^n+
tx^p\sum_{n\ge 0}\eta S_{n} x^n
\end{equation*}
or
\begin{equation*}
F(x)-\sum_{n< p}S_nx^n=
xF(x)-x\sum_{n< p-1}S_nx^n+tx^p\eta F(x),
\end{equation*}
and
\begin{equation*}
F(x)=\frac1{1-x-tx^p\eta}\bigg(\sum_{i< p}S_ix^i-\sum_{i< p-1}S_ix^{i+1}\bigg).
\end{equation*}

Now we can apply our lemma and write
\begin{align*}
F(x)&=\sum_{n\ge0 }\big(x+tx^p\eta\big)^n
\bigg(\sum_{i< p}S_ix^i-\sum_{i< p-1}S_ix^{i+1}\bigg)\\
&=\sum_{n\ge0 }\sum_{k=0}^n\gauss nk q^{p\binom n2-pnk+p\binom{k+1}2}
x^{k+p(n-k)}t^{n-k}\eta^{n-k}
\bigg(\sum_{i< p}S_ix^i-\sum_{i< p-1}S_ix^{i+1}\bigg)\\
&=\sum_{n\ge0 }\sum_{k=0}^n\gauss nk q^{p\binom n2-pnk+p\binom{k+1}2}
x^{k+p(n-k)}
t^{n-k}\bigg(\sum_{i< p}S_iq^{i(n-k)}x^{i}-\sum_{i< p-1}S_iq^{(i+1)(n-k)}x^{i+1}\bigg)\\
&=\sum_{n\ge0 }\sum_{k=0}^n\gauss nk q^{p\binom k2}
x^{n-k+pk}
t^{k}\bigg(\sum_{i< p}S_iq^{ik}x^{i}-\sum_{i< p-1}S_iq^{(i+1)k}x^{i+1}\bigg)\\
&=\sum_{k,n\ge0}\gauss {n+k}k q^{p\binom k2}
x^{n+pk}
t^{k}\bigg(\sum_{i< p}S_iq^{ik}x^{i}-\sum_{i< p-1}S_iq^{(i+1)k}x^{i+1}\bigg)\\
&=\sum_{k\ge0} q^{p\binom k2}
x^{pk}
t^{k}\frac 1{\qff x{k+1}}\bigg(\sum_{i< p}S_iq^{ik}x^{i}
-\sum_{i< p-1}S_iq^{(i+1)k}x^{i+1}\bigg).
\end{align*}

 From this we find an explicit formula for $S_n$ (the quantity
$S_{-1}$ has to be interpreted as 0):

\begin{align*}
S_n=\sum_{0\le i< p}(S_i-S_{i-1})	\sum_{k\ge0}\gauss{n-(p-1)k-i}{k}q^{p\binom k2+ik}t^k.
\end{align*}

Now we specialize this to our instance. Here, $t=-q^p$, and thus
%
\begin{align*}
S_n=\sum_{0\le i< p}(S_i-S_{i-1})	
\sum_{k\ge0}\gauss{n-(p-1)k-i}{k}q^{p\binom {k+1}2+ik}(-1)^k.
\end{align*}
%
Therefore
\begin{align*}
E_n=\sum_{k\ge0}\gauss{n-(p-1)k}{k}q^{p\binom {k+1}2}(-1)^k.
\end{align*}
 From this, the limit of $E_n$ is immediate.
For $D_n$ we eventually get  the following form
\begin{align*}
D_n=\sum_{k\ge0}\gauss{n-(p-1)(k-1)}{k}q^{k+p\binom {k}2}(-1)^k,
\end{align*}
from which the formula for $D_\infty$ is immediate.
To prove it,  we need a simple lemma whose proof is just a routine 
calculation.
\begin{lemma}
\begin{equation*}
\gauss{m-i}{k}q^{i(k+1)}=g(i)-g(i-1)\qquad\text{where}\qquad
g(i)=-\gauss{m-i}{k+1}q^{(i+1)(k+1)}.\qed
\end{equation*}
\end{lemma}

Now we can plug into the general formula above and compute
\begin{align*}
D_n&=E_n-\sum_{i=1}^{p-1}\sum_{k\ge0}\gauss{n-(p-1)k-i}{k}q^{p\binom {k+1}2+i(k+1)}(-1)^k\\
&=E_n-\sum_{k\ge0}(-1)^kq^{p\binom {k+1}2}\sum_{i=1}^{p-1}
\gauss{n-(p-1)k-i}{k}q^{i(k+1)}\\
&=E_n-\sum_{k\ge0}(-1)^kq^{p\binom {k+1}2}
\bigg\{q^{k+1}\gauss{n-(p-1)k}{k+1}-q^{p(k+1)}\gauss{n-(p-1)(k+1)}{k+1}\bigg\}\\
&=1-\sum_{k\ge0}(-1)^kq^{p\binom {k+1}2}
q^{k+1}\gauss{n-(p-1)k}{k+1},
\end{align*}
which is the announced formula after a simple change of variable. Note that
in the penultimate step the telescoping property of the lemma has been used.
















\section{Computer algebra proofs}

The polynomial families $(E_n)$ and $(D_n)$ give rise to the following
study with respect to possible computer proofs. Let us take as input our
sum representations of $E_n$ and $D_n$:
\begin{align}\begin{split}\label{sumrep}
E_n&=\sum_{k\ge0}\gauss{n-(p-1)k}{k}q^{p\binom {k+1}2}(-1)^k,\\
D_n&=\sum_{k\ge0}\gauss{n-(p-1)(k-1)}{k}q^{k+p\binom {k}2}(-1)^k.
\end{split}
\end{align}
%
Then, if $p$ is chosen as a specific positive integer, Riese's package
\textsf{qZeil} \cite{PauleRiese} returns the recurrences $S_n=S_{n-1}-q^nS_{n-p}$
($n\ge p$) together with a certificate function $\mathsf{Cert}$ for independent
verification. Despite the fact that for general ``generic'' integer parameter $p$
there is no algorithm available, a general pattern can be easily guessed from running
the algorithm for $p=1$, $p=2$, and $p=3$, say. 

For example, let $F(n,k)$ be the $k$th summand in our sum representation 
\eqref{sumrep} of $E_n$, then the recurrence for $E_n$ can be refined to the following
statement.
\begin{theorem}
For $n\ge p$ and $\delta_kf(n,k)=f(n,k)-f(n,k-1)$, we have
\begin{equation}\label{zwei}
F(n,k)-F(n-1,k)+q^nF(n-p,k)=\delta_k\mathsf{Cert}(n,k)F(n,k),
\end{equation}
where
\begin{equation*}
\mathsf{Cert}(n,k)=q^n\frac{\qff{q^{n-p(k+1)+1}}{p}}
{\qff{q^{n-(p-1)(k+1)}}{p}}.
\end{equation*}
\end{theorem} 

\textbf{Proof.} After dividing both sides of \eqref{zwei} by $F(n,k)$
the proof reduces to checking equality of rational functions. Namely, note that
\begin{align*}
\frac{F(n-1,k)}{F(n,k)}&=\frac{1-q^{n-pk}}{1-q^{n-(p-1)k}},\\
\frac{F(n,k-1)}{F(n,k)}&=-\frac{q^{pk}}{1-q^k}\frac{\qff{q^{n-pk+1}}p}
{\qff{q^{n-(p-1)k+1}}{p-1}},
\intertext{and}
\frac{F(n-p,k)}{F(n,k)}&=q^{-n}\mathsf{Cert}(n,k).\qed
\end{align*}

Analogously, there is a refined version of the recurrence for $D_n$. The
certificate  in this case is
\begin{equation*}
\mathsf{Cert}(n,k)=q^n\frac{\qff{q^{n-pk}}{p}}
{\qff{q^{n-(p-1)k}}{p}}.
\end{equation*}

Summarizing, with the sum representation for $E_n$ and $D_n$ in hand, the
corresponding recurrences follow immediately by summing both sides of
the computer recurrences \eqref{zwei} over all $k\ge0$.


















































	









%\newpage

\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{1}

\bibitem{AnAsRo99}
G.~E.~Andrews, R.~Askey, and R.~Roy, \emph{Special functions}, Encyclopedia of
  Mathematics and its Applications, vol.~71, Cambridge University Press, 1999.

\bibitem{Andrews02}
G.~E. Andrews, \emph{Fibonacci numbers and {R}ogers--{R}amanujan identities},
  The Fibonacci Quarterly, to appear (2003), 15 pp.

\bibitem{Cigler81}
J.~Cigler, \emph{Elementare $q$--{I}dentit\"aten}, S\'eminaire Lotharingien de
  Combinatoire \textbf{B05a} (1981), 29 pp.

\bibitem{Cigler03}
J.~Cigler, \emph{
Some algebraic aspects of {M}orse code sequences}, 
Discrete Mathematics and Theoretical Computer Science \textbf{6} (2003), 
55--68.

\bibitem{Merlini02}
D.~Merlini, \emph{Private communication},  (2002).

\bibitem{MeSp02}
D.~Merlini and R.~Sprugnoli, \emph{Fountains and histograms}, J. Algorithms
  \textbf{44} (2002), no.~1, 159--176.

\bibitem{PauleRiese}
P.~Paule and A.~Riese, \emph{A {M}athematica {$q$}--analogue of {Z}eilberger's
  algorithm based on an algebraically motivated approach to
  {$q$}--hypergeometric telescoping}, Special functions, $q$--series and related
  topics (Toronto, ON, 1995), Fields Inst. Commun., vol.~14, Amer. Math. Soc.,
  Providence, RI, 1997, pp.~179--210. 


\bibitem{Schur17}
I.~Schur,
{\it Ein Beitrag zur additiven Zahlentheorie und zur
Theorie der Kettenbr\"uche}, S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl.,
1917, 302--321, reprinted in I. Schur, Gesammelte Abhandlungen, vol. 2,
pp. 117--136, Springer, 1973.

\end{thebibliography}

%\bibliography{C:/texfiles2001/pro_bib}


\end{document}