%------------plain TeX file
% New fonts
%
\font\bigbf=cmbx10 scaled\magstep1  % for headings
\font\titbf=cmbx10 scaled\magstep2  % for title of paper

\font\bigrm=cmr10  scaled\magstep1  % for author's name

\magnification=\magstep1
\nopagenumbers
%
% some definitiones
%
\def\aboveheaderskip{\vskip12mm plus4mm minus2mm}
\def\defeq{\mathrel{:=}}    % "defined as equal to"
\def\dx{{\rm d}x}           % "integral ornament"
\def\e{{\rm e}}             % Euler-number
\def\squr#1#2{
  {\vbox{\hrule height.#2pt
     \hbox{\vrule width.#2pt height#1pt\kern#1pt
           \vrule width.#2pt}
   \hrule height.#2pt}}}    % draws a square
\def\square{\squr59}        % draws a 'end-of-proof'-square
% The following macro puts a square at the right-hand margin of the
% last line of a paragraph. If it does not fit it is put on the right-hand
% margin of a line by itself.
\def\endproof{\hskip1em\hfill\hbox{}\hfill$\square$}
\let\vareps=\varepsilon     % an abbreviation

\centerline{\titbf The Concept of Bailey Chains}
\bigskip
\centerline{\bigrm Peter Paule}
\vskip5mm\aboveheaderskip
\centerline{\bigbf 0. Introduction}
\bigskip
In his expository lectures on $q$-series [3] G. E. Andrews devotes a whole
chapter to Bailey's Lemma (Th. 2.1, 3.1) and discusses some of its numerous 
possible
applications in terms of the ``Bailey chain'' concept. This name was introduced
by G. E. Andrews [2] to describe the iterative nature of Bailey's Lemma, which
was not observed by W. N. Bailey himself.

This iteration mechanism allows
to derive many $q$-series identities by ``reducing'' them to more elementary
ones. As an example, the famous Rogers-Ramanujan identities can be reduced
to the $q$-binomial theorem. 

G. E. Andrews [2] observed this iteration mechanism in
its full generality by an appropriate reformulation of Bailey's Lemma, whereas
P. Paule discovered important special cases [23]. 
W. N. Bailey never formulated his lemma in that way and consequently missed
the full power of its potential for iteration. In that paper [2] G. E. Andrews
introduced the notions of ``Bailey pairs'' and ``Bailey chains'' and
laid the foundations of a Bailey chain theory for discovering and proving
$q$-identities.

The purpose of this article is to give an introduction to that concept.
Therefore many theorems are not stated in full generality, for which we
refer to the literature.
\goodbreak\aboveheaderskip 
\centerline{\bigbf 1. Definitions and Tools}
\bigskip
A {\it hypergeometric\/} series (see e.g. W. N. Bailey [10]) is a series
  $$\sum c_n,$$
where 
  $$c_{n+1}\over c_n$$
is a rational function in $n$, i.e.
  $$c_0=1\hbox{\quad and\quad}
    {c_{n+1}\over c_n}={(n+a_1)(n+a_2)\cdots(n+a_i)\over
                        (n+b_1)(n+b_2)\cdots(n+b_j)}    {x\over n+1}.$$
Thus
  $$c_n={\langle a_1\rangle_n\cdots\langle a_i\rangle_n \over
         \langle b_1\rangle_n\cdots\langle b_j\rangle_n}  {x^n\over n!},$$
where
  $$\langle a\rangle_n\defeq a(a+1)\cdots(a+n-1)\hbox{\quad and\quad}
    \langle a\rangle_0\defeq1$$                       
Notation:                                                 
  $${}_iF_j\left({a_1,\ldots,a_i\atop b_1,\ldots,b_j};x\right)=
    \sum_{k=0}^\infty{\langle a_1\rangle_k\ldots\langle a_i\rangle_k \over
                      \langle b_1\rangle_k\ldots\langle b_j\rangle_k}
    {x^k\over k!}$$

Examples: 
\item{1.}{\it Wallis\/}:
  $${\pi\over2}=\lim_{n\to\infty}
    {\langle 1       \rangle_n\langle 1       \rangle_n \over
     \langle{1\over2}\rangle_n\langle{3\over2}\rangle_n}.$$
\medskip
\item{2.}The binomial series
  $${1\over(1-x)^\alpha}={}_1F_0(\alpha;\hbox{---};x)=
    \sum c_n\hbox{\quad with $\displaystyle{c_{n+1}\over c_n}=
                 {\alpha+n\over1+n}x$ and $c_0=1$.}$$
\medskip
\item{3.}$y={}_2F_1(a,b;c;x)$ is solution of
  $$x(1-x)y''+(c-(a+b+1)x)y'-aby=0$$
({\it hypergeometric differential equation\/}).
\medskip
\item{4.}The {\it Jacobi polynomials\/} (see e.g. R. Askey [7]) 
   ($\alpha,\beta>-1$)
  $$P_n^{(\alpha,\beta)}(x)={\langle\alpha+1\rangle_n\over n!}{}_2F_1\left(
    {-n,n+\alpha+\beta+1\atop\alpha+1};{1-x\over2}\right)$$
with orthogonality relation ($m\ne n$):
  $$\int_{-1}^1 P_n^{(\alpha,\beta)}(x)P_m^{(\alpha,\beta)}(x)
    (1-x)^\alpha(1+x)^\beta\dx=0.$$
\medskip
For many reasons it is convenient to extend this definition by introducing
an extra parameter $q$ (see e.g. L. Slater [30]):

\proclaim Definition. A\/ {\it basic-} (or $q$-)\/ {\it hypergeometric series}
is a series $\displaystyle\sum_{n=-\infty}^\infty c_n$, where $\displaystyle
{c_{n+1}\over c_n}$ is a rational function of $q^n$.

Example: The {\it theta-function}
  $$\sum c_n=\sum_{n=-\infty}^\infty q^{n^2}x^n\quad
    \hbox{($q=\e^{\pi ir}$, $x=\e^{2iz}$)}$$ 
where
  $${c_{n+1}\over c_n}=q^{2n+1}x, c_0=1.$$

Now we define
  $$(a;q)_n\defeq(a)_n\defeq(1-a)(1-qa)\cdots(1-q^{n-1}a)\quad
    \hbox{for $n=1,2,\ldots$}$$
and
  $$(a;q)_0\defeq(a)_0\defeq1,\quad
    (a;q)_\infty\defeq(a)_\infty\defeq\prod_{k=0}^\infty(1-q^ka)$$
and
  $$(a)_n\defeq{(a)_\infty\over(q^na)_\infty}\quad
    \hbox{for integer $n$.}$$
Observe that $\displaystyle{1\over(q)_n}=0$ for $n=-1,-2,\ldots$
\medskip
All following $q$-identities can be treated as formal power series identities.
If one likes to consider them as analytic ones, in most cases it will suffice
to take $q$ as real with $\left|q\right|<1$.
\medskip
Notation: $${}_i\varphi_j\left({a_1,\ldots,a_i \atop b_1,\ldots,b_j};q,x\right)
\defeq \sum_{k=0}^\infty{(a_1;q)_k\ldots(a_i;q)_k \over
                         (b_1;q)_k\ldots(b_j;q)_k}     {x^k\over(q)_k}$$

Example: The $q$-analogue of the binomial series is
  $$\sum c_n={}_1\varphi_0(a;\hbox{---};q;x)
  \hbox{\quad with $\displaystyle
    {c_{n+1} \over c_n}={1-aq^n \over 1-q^{n+1}}x$, $c_0=1$}.$$
Setting $a=q^\alpha$ we obtain
  $${c_{n+1}\over c_n}=
  {1-q^{\alpha+n}\over1-q}\cdot{1-q\over1-q^{1+n}}x,$$
which is for $q=1$ equal to
  $${\alpha+n\over1+n}x,$$
as in ${}_1F_0(\alpha;\hbox{---};x)$.
\bigskip
In order to emphasize the analogy to the $q=1$ case, we introduce the {\it
Gaussian polynomials\/} (or {\it $q$-binomial coefficients\/}) (see e.g.
G. Andrews [4]):
  $${n\brack k}\defeq\cases{\displaystyle{(q)_n\over(q)_k(q)_{n-k}} 
                                 &if $0\le k\le n$\cr
                            0    &else\cr}.$$
We shall also write $$\eqalign{
  {n\brack k}&={[n]!\over[k]!\,[n-k]!},
    \hbox{\quad where $[n]!\defeq[n][n-1]\ldots[1]$,}\cr
  [0]!&\defeq1\hbox{\quad and\quad}[n]\defeq{1-q^n\over1-q}=1+q+\cdots+q^{n-1},
    \quad[0]\defeq1.\cr}$$
From this definition it obvious that
  $${n\brack k}\Big|_{q=1}={n\choose k}.$$
\bigskip
Now we introduce the $q$-binomial theorem in the notion of J. Cigler (cf.\ 
the survey article [15]):
\proclaim Theorem 1.1. Let $\cal R$ denote the ring of all power series in the
variable $x$ over the reals (or formal power series in $x$, respectivly).
For linear operators $A,B$ on $\cal R$ with $BA=qAB$ the following formula
holds ($n=0,1,2,\ldots$):
  $$(A+B)^n=\sum_{k=0}^n{n\brack k}A^k B^{n-k}.\eqno(1)$$

\noindent{\bf Proof.} The proof is an easy induction exercise using the
recursive formula
  $${n+1\brack k}=q^k{n\brack k}+{n\brack k-1}.\eqno(2)$$ \endproof

Examples:
\item{1.}$(\underline{x}f)(x)\defeq xf(x)$, $(\vareps f)(x)\defeq f(qx)$ and
$(\vareps^{-1}f)(x)\defeq f(q^{-1}x)$ for $f\in{\cal R}$. Now we have $BA=qAB$
for e.g.\ $A=\underline{x}\vareps$, $B=\vareps$ or $A=\vareps^{-1}$,
$B=\underline{x}$.
\item{2.}Observing that $(\underline{x}\vareps)^k1=q^{k\choose2}x^k$ and
$(\underline{x}\vareps+\vareps)^k1=(x+1)(qx+1)\cdots(q^{k-1}x+1)$ we obtain
by setting $A=\underline{x}\vareps$ and $B=\vareps$ in (1):
  $$\sum_{k=0}^n{n\brack k}q^{k\choose2}x^k=(1+x)(1+qx)\cdots
    (1+q^{n-1}x).\eqno(3)$$
\item{3.}A further consequence of Theorem 1.1 is the infinite form of the
$q$-binomial theorem (cf.\ [15]):
  $$\sum_{k=0}^\infty {(a)_k\over(q)_k} x^k =
    {(ax)_\infty\over(x)_\infty}.\eqno(4)$$
Now for $a=q^\alpha$ the $q$-analogy becomes evident:
  $${}_1F_0(\alpha;\hbox{---};x)=
    \sum_{k=0}^\infty {\langle\alpha\rangle_k \over k!} =
    \sum_{k=0}^\infty {\alpha+k-1 \choose k} x^k =
    {1\over(1-x)^\alpha}$$
and
  $${}_1\varphi_0(q^\alpha;\hbox{---};x)=
    \sum_{k=0}^\infty {(q^\alpha)_k \over (q)_k} x^k =
    \sum_{k=0}^\infty {\alpha+k-1\brack k} x^k = 
    {1\over(x)_\alpha}.$$
\item{4.}The $q$-binomial theorem (3) gives ($x\ne0$):
  $$\sum_{k=-\infty}^\infty {2j\brack j-k}(-1)^k x^k q^{{1\over2}k^2} =
    (x^{-1}q^{1\over2})_j(xq^{1\over2})_j\eqno(5)$$
(The sum on the left is actually finite!), which in the limit $j\to\infty$
becomes:
  $$\sum_{k=-\infty}^\infty (-1)^k q^{{1\over2}k^2} x^k =
    (q)_\infty (x^{-1}q^{1\over2})_\infty (x q^{1\over2})_\infty.\eqno(6)$$
(Note that
  $${2j\brack j-k}={(q)_{2j} \over (q)_{j-k}(q)_{j+k}} \to {1\over(q)_\infty}
    \quad\hbox{for $j\to\infty$}.)$$
\medskip
Identity (6) is called {\it Jacobi triple product identity\/} and serves
as a fundamental tool for transforming sums into products and vice versa.
\bigskip
We give a prominent example, one of the {\it Rogers-Ramanujan identities\/}
(see e.g. G. Andrews [4]):
  $$\sum_{n=0}^\infty {q^{n^2}\over(q)_n} =
    \prod_{n=0}^\infty {1\over (1-q^{5n+1})(1-q^{5n+4})}.\eqno(7)$$

By (6) ($q$ replaced by $q^5$ and $x=-q^{1\over2}$) the product on the right is
equal to $${1\over(q)_\infty} (q^5;q^5)_\infty (q^2;q^5)_\infty
(q^3;q^5)_\infty = {1\over(q)_\infty} \sum_{k=-\infty}^\infty (-1)^k
q^{{5\over2}k^2-{1\over2}k}.$$ Now to prove (7) means to prove
$${1\over(q)_\infty} \sum_{k=-\infty}^\infty (-1)^k
q^{{5\over2}k^2-{1\over2}k} = \sum_{n=0}^\infty {q^{n^2}\over (q)_n}.\eqno(8)$$
This is exactly the point where the Bailey chain concept enters the stage. In
the following we shall see how identities of this type can be reduced by
Bailey chain iteration to identities of a simpler form or to well-known ones,
respectively. In particular we shall demonstrate, how the Rogers-Ramanujan
identity (8) is iterated to a special case of the $q$-binomial theorem (5).
Further we shall derive the iteration mechanism for that and many other
important applications as a consequence of the $q$-binomial theorem in the
form (1). This is followed by a closer investigation of the inner structure 
of that mechanism, i.e.\ how to ``walk along'' Bailey chains.
\goodbreak\aboveheaderskip   

\centerline{\bigbf 2. Bailey Pairs and Bailey Chains}
\bigskip 
{\bf 2.1 Bailey's Lemma}
In distilling some of the work of L. J. Rogers [27, 28] and others W. N. Bailey
formulated the following fundamental $q$-series transform [(3.1), 9]: 
\proclaim Theorem 2.1 \it (Bailey's Lemma). % Note the blank before the '%'!
  $$\sum_{k=0}^\infty
            (r_1)_k(r_2)_k \left(xq \over r_1 r_2\right)^k b_k =
    {\left(xq \over r_1\right)_\infty \left(xq \over r_2\right)_\infty \over
     (xq)_\infty \left(xq \over r_1 r_2\right)_\infty}
    \sum_{k=0}^\infty
      {(r_1)_k(r_2)_k \over
       \left(xq \over r_1\right)_k \left(xq \over r_2\right)_k}
      \left(xq \over r_1 r_2\right)^k a_k,\eqno(9)$$
where
  $$b_n=\sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}} \quad
    \hbox{$n=0,1,2,\ldots$} \eqno(10)$$

Following G. E. Andrews [2] we say, sequences $a=(a_n)$, $b=(b_n)$ related
like (10) form a {\it Bailey pair\/} $(a,b)$.
\bigskip
Using Bailey's Lemma as a tool for proving identities of the Rogers-Ramanujan
type, like identity (7) or e.g.\ one of the {\it G\"ollnitz-Gordon\/}
identities
  $${1\over (q^2;q^2)_\infty} \sum_{n=-\infty}^\infty (-1)^n q^{4n^2-n} =
    \sum_{k=0}^\infty {q^{2k^2} \over (q^2;q^2)_k (-q;q^2)_k}, \eqno(11)$$
one has to look for a suitable Bailey pair $(a,b)$, which after insertion
into (9) with special chosen parameters $r_1$, $r_2$ yields the desired
identity.

By a skillful application of this procedure L. J. Slater gave a list of
130~identities of that type in 1950 [29]. As we shall see, by using the
Bailey chain concept the search for appropriate Bailey pairs and the problem
of proving or discovering such identities are far easier to handle and to
solve.
\bigskip
In 1972 [6] G. E. Andrews showed how Bailey's Lemma fits into the frame of
a connection-coefficient problem: Let
  $$P_k (x;\alpha,\beta|q)\defeq
    {}_2\varphi_1 \left({q^{-k},\alpha\beta q^{k+1} \atop \alpha\beta};
                        q,xq \right)$$
({\it $q$-Jacobi polynomials}).

Now Bailey's Lemma is essentially equivalent to the following expansion:
  $$p_n(x)=\sum_{k=0}^n c_{nk} P_k(x;\alpha,\beta|q),$$
where
  $$p_n(x)= {}_3\varphi_2 \left(
    {r_1,r_2,q^{-n} \atop \alpha q, {r_1r_2q^{-n}\over\alpha\beta q}};
    q, xq \right)$$
and ($\alpha\beta q\defeq x$)
  $$c_{nk} =
    {\left(xq\over r_1\right)_n\left(xq\over r_2\right)_n(xq)_{k-1}
        (1-xq^{2k})(r_1)_k(r_2)_k(q^{-n})_k       \over
     (xq)_n\left(xq\over r_1r_2\right)_n
        \left(xq\over r_1\right)_k\left(xq\over r_1\right)_k
        (q)_k(xq^{n+1})_k}
    \left( xq^{n+1} \over r_1r_2 \right)^k.$$
\medskip
\noindent{\bf 2.1 Bailey chains.} In order to describe its potential for
iteration we consider the following special case ($r_1=q^{-m}$, $r_2=q^{-n}$,
$a_k$ replaced by $q^{-k^2}a_k$ and $m\to\infty$) of Bailey's Lemma:
  $$\sum_{k=0}^n {a_k x^k \over (q)_{n-k} (xq)_{n+k}} =
    \sum_{j=0}^n {q^{j^2} x^j \over (q)_{n-j}}
    \sum_{k=0}^j {a_k q^{-k^2} \over (q)_{j-k} (xq)_{j+k}}. \eqno(12)$$

Because of its importance we give a separate proof of this identity (cf.\ 
Paule [25]).
\medskip
\noindent{\bf Proof.} We need Theorem~1.1 together with the following facts,
which are easily checked: for all $f,g\in \cal R$ 
  $$\eqalignno{
    &\vareps(fg)=(\vareps f)(\vareps g),                 &\hbox{(i)}\cr
    &(\vareps^{-1}+\underline{x})(xq)_\infty=(xq)_\infty.&\hbox{(ii)}\cr}$$
Now we apply the $q$-binomial Theorem~(1) with $A=\vareps^{-1}$ and
$B=\underline{x}$ as follows: $$\eqalignno{     
  \sum_{k=0}^n {a_k x^k\over (q)_{n-k} (xq)_{n+k}}                                 
   & = {1\over(xq)_\infty}\left( \sum_{k=0}^n {a_k x^k \over (q)_{n-k}}
         \vareps^{n+k} (xq)_\infty \right)                             \cr
   &\buildrel \rm (ii) \over=
       {1\over(xq)_\infty}\left( \sum_{k=0}^n {a_k x^k \over (q)_{n-k}}
         \vareps^{n+k} (\vareps^{-1}+\underline{x})^{n-k}
          (xq)_\infty \right) \cr
   &\buildrel (1) \over=
       {1\over(xq)_\infty}\left( \sum_{k=0}^n {a_k x^k \over (q)_{n-k}}
         \vareps^{n+k} \sum_{j=0}^{n-k} {n-k \brack j}
         (\vareps^{-1})^{n-k-j} \underline{x}^j(xq)_\infty \right)     \cr
   &\buildrel \rm (i) \over=
       {1\over(xq)_\infty}\left( \sum_{k=0}^n {a_k x^k \over (q)_{n-k}}
         \sum_{j=0}^{n-k} {n-k \brack j} q^{j(j+2k)}
                          x^j(q^{j+2k+1}x)_\infty \right)              \cr
   & = \sum_{k=0}^n {a_k x^k \over (q)_{n-k}}
         \sum_{j=k}^n {n-k \brack j-k} q^{j^2-k^2}
                      {x^{j-k} \over (xq)_{j+k}}                       \cr
   & = \sum_{j=0}^n {q^{j^2} x^j \over (q)_{n-j}}
         \sum_{k=0}^j {a_k q^{-k^2} \over (q)_{j-k} (xq)_{j+k}}.
     &\square\cr}$$
\medskip
If $x=1$ or $q$ for many applications it is of advantage to symmetrize (12)
as follows: (Observe that all sums are finite!)
  $$\sum_{k=-\infty}^\infty {c_k \over (q)_{n-k} (q)_{n+k}} =
    \sum_{j=0}^\infty {q^{j^2} \over (q)_{n-j}}
       \sum_{k=-\infty}^\infty {c_k q^{-k^2} \over (q)_{j-k} (q)_{j+k}}
    \eqno(13)$$
(in (1): $x=1$, $a_0=c_0$ and $a_k=c_k+c_{-k}$ for $k\ge 1$),
  $$\sum_{k=-\infty}^\infty {c_k \over (q)_{n-k} (q)_{n+1+k}} =
    \sum_{j=0}^\infty {q^{j^2+j} \over (q)_{n-j}}
       \sum_{k=-\infty}^\infty {c_k q^{-k^2-k} \over (q)_{j-k} (q)_{j+1+k}}
    \eqno(14)$$
(in (1): $x=q$ and $a_k={q^{-k} \over 1-q}(c_k+c_{-k-1})$ for $k\ge0$).

Writing Bailey's Lemma as (12) (or (13), (14), respectively) its potential
for iteration now leaps to our eyes, namely:
\medskip
\noindent{\sl The second sums of the right-hand sides are of the same form
as the corresponding sums on the left-hand sides. Thus we may iterate them
substituting the whole formula (modified e.g.\ by taking $c_kq^{-k^2}$ instead
of $c_k$) in the place of the second sum of the right-hand side as often
as we want, in order to reduce the initial sum on the left to a simpler
or well-known one.}
\medskip
Example: In the limit $n\to\infty$ (13) becomes
  $${1\over(q)_\infty} \sum_{k=-\infty}^\infty c_k =
    \sum_{j=0}^\infty q^{j^2} \sum_{k=-\infty}^\infty
    {c_k q^{-k^2} \over (q)_{j-k} (q)_{j+k}}. \eqno(15)$$
With the above iteration-algorithm the Rogers-Ramanujan identity~(8) now
is easily {\it computed\/} as follows: $$\eqalign{
  {1\over(q)_\infty} \sum_{k=-\infty}^\infty
    (-1)^k q^{{5\over2}k^2-{1\over2}k}
  &\buildrel(15)\over=
      \sum_{j=0}^\infty q^{j^2}
        \sum_{k=-\infty}^\infty
          {(-1)^k q^{{3\over2}k^2-{1\over2}k} \over (q)_{j-k} (q)_{j+k}}\cr
  &\buildrel(15)\over=
      \sum_{j=0}^\infty q^{j^2}
        \sum_{l=0}^\infty {q^{l^2}\over(q)_{j-l}}
          \sum_{k=-\infty}^\infty
            {(-1)^k q^{{1\over2}k^2-{1\over2}k} \over (q)_{l-k} (q)_{l+k}}\cr
  &\buildrel(5)\over=
      \sum_{j=0}^\infty q^{j^2}
        \sum_{l=0}^\infty {q^{l^2} \over (q)_{j-l}}
                          {(q)_l (1)_l \over (q)_{2l}}        \cr
  & = \sum_{j=0}^\infty {q^{j^2} \over (q)_j}.                \cr}$$
The last line follows from the fact that ${(1)_0=1}$ and ${(1)_l=
(1-1)(1-q)\cdots(1-q^{l-1})=0}$ for all $l\ge1$.\endproof

Now we formulate as a

\proclaim Theorem 2.2. Given a Bailey pair $(a,b)=\bigl((a_n),(b_n)\bigr)$
a new Bailey pair $(a',b')=\bigl((a_n'),(b_n')\bigr)$ is constructed by
  $$a_n'=q^{n^2}x^na_n \quad\hbox{and}\quad
    b_n'=\sum_{j=0}^n {q^{j^2} x^j \over (q)_{n-j}} b_j \quad
    \hbox{$n=0,1,2,\ldots$}$$

\noindent{\bf Proof.} The proof is an immediate consequence of equation~(12)
with $a_k$ replaced by $a_k q^{k^2}$.\endproof

\proclaim Definition. The sequence
  $$\bigl((a_n),(b_n)\bigr)\to\bigl((a_n'),(b_n')\bigr)
    \to\bigl((a_n''),(b_n'')\bigr)\to\cdots$$
is called a\/ {\rm Bailey chain} (cf.\ Andrews [2]).

\noindent{\bf Remark.} To include the symmetrized versions~(13) and~(14)
among that concept, we call sequences $a=(a_n)_{n=-\infty}^\infty$,
$b=(b_n)_{n\ge0}$ with
  $$b_n = \sum_{k=-\infty}^\infty {a_k \over (q)_{n-k} (q)_{n+k}}
    \quad \hbox{or} \quad
    b_n = \sum_{k=-\infty}^\infty {a_k \over (q)_{n-k} (q)_{n+1+k}}$$
also a {\it Bailey pair\/} $(a,b)$.

With this definition Theorem~2.2 remains valid with $x=1$ or $q$ according
the equations~(13) and~(14).

Example: for the Rogers-Ramanujan identity~(8) the Bailey chain corresponding
to our iteration (cf.\ the example above) is as follows: We start with the
simplest pair
  $$(a,b)=\bigl((a_n)_{n=-\infty}^\infty,(b_n)_{n\ge0}\bigr),$$
where
  $$a_n=(-1)^n q^{n\choose2},\quad
    b_n=\delta_{n0} \quad (\defeq\cases{1&if $n=0$\cr 0&else\cr}),$$
then  
  $$(a',b')=\bigl((a_n')_{n=-\infty}^\infty,(b'_n)_{n\ge0}\bigr),$$
where (Theorem 2.2 with $x=1$)
  $$a_n'=q^{n^2} a_n=(-1)^n q^{{3\over2}n^2-{1\over2}n},\quad
    b_n'=\sum_{j=0}^n {q^{j^2} \over (q)_{n-j}} b_j = {1\over(q)_n},$$
and
  $$(a'',b'')=\bigl((a_n'')_{n=-\infty}^\infty,(b_n'')_{n\ge0}\bigr),$$
where (Theorem 2.2 with $x=1$)
  $$a_n''=q^{n^2}a_n'=(-1)^n q^{{5\over2}n^2-{1\over2}n},\quad
    b_n''=\sum_{j=0}^n {q^{j^2} \over (q)_{n-j}} b_j' = 
          \sum_{j=0}^n {q^{j^2} \over (q)_{n-j} (q)_j}.$$

It is interesting to look at the corresponding Bailey pair identities:
$$\eqalignno{
  (a,b)    &\iff \sum_{k=-\infty}^\infty {(-1)^k q^{{1\over2}k^2-{1\over2}k}
                   \over (q)_{n-k} (q)_{n+k}} = \delta_{n0},    &(16)\cr
  (a',b')  &\iff \sum_{k=-\infty}^\infty {(-1)^k q^{{3\over2}k^2-{1\over2}k}
                   \over (q)_{n-k} (q)_{n+k}} = {1\over(q)_n},  &(17)\cr
  (a'',b'')&\iff \sum_{k=-\infty}^\infty {(-1)^k q^{{5\over2}k^2-{1\over2}k}
                   \over (q)_{n-k} (q)_{n+k}} = \sum_{j=0}^\infty
                 {q^{j^2}\over (q)_{n-j} (q)_j}.                &(18)\cr}$$
In the limit $n\to\infty$ equation~(18) becomes the Rogers-Ramanujan
identity~(8).

Thus starting with the special case~(16) of the $q$-binomial theorem~(5)
and by walking along the Bailey chain
  $$(a,b)\to(a'b')\to(a'',b''),$$
we have proved equation~(8) and as a by-product identities~(17) and~(18).
\medskip
\noindent{\bf Remark.} Note that equation~(18) is a {\it finite\/} sum
identity, which yields in the limit~$n\to\infty$ the Rogers-Ramanujan
identity~(8).
\medskip
In the following section we shall have a closer look at the question how
to construct Bailey pairs and to walk along Bailey chains.
\medskip
\noindent{\bf 2.3 Bailey pairs and walking along Bailey chains.} An efficient
use of the iteration mechanism of Bailey's Lemma depends on our knowledge
of Bailey pairs. For that, one may consult L. Slater's list [29]. But in 
addition
to those classical examples there exist many other interesting pairs, which
naturally arise in different contexts, as G. Andrews pointed out in [3].

Now we shall describe some techniques how to find Bailey pairs and how to
construct new Bailey pairs out of given ones as in Theorem~2.2. Further
we shall see that there are several ways how to walk along Bailey chains,
which introduces the more general concept of a Bailey lattice (cf. [13] and
[1]).    

First we observe:

\proclaim Theorem 2.3. A Bailey pair 
$ (a,b) = \bigl ((a_n), (b_n) \bigr)$ is uniquely determined by one of the 
sequences $ (a_n) $ or $ (b_n) $, respectively.
\bigskip
\noindent{\bf Proof}. This is proved by the inversion formula 
  $$ a_n = \cases{\displaystyle (1-xq^{2n}) \sum_{k=0}^n 
     (-1)^{n-k} q^{n-k \choose 2} 
     {(xq)_{n+k-1} \over (q)_{n-k}} b_k & if $ n \ge 1 $ \cr
     b_0 & $ n=0 $ \cr}  $$
iff
  $$ b_n = \sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}} \eqno (19) $$
(cf.\ Andrews [(4.1), 2]).  \endproof

Example: For arbitrary parameter $x$ we obtain with $ b_n=\delta_{0,n} (n=0,1,
\cdots) $
  $$ a_n=(-1)^n q^{{n \choose 2}} (1-xq^{2n}) {(xq)_{n-1} \over (q)_n} \quad
     (n \ge 1), a_0=1 $$
(cf.\ equation (16) in case $x=1$). As G. Andrews pointed out [3], this Bailey
pair lies behind the majority of the identities in L. Slater's list [29].

\noindent{\bf Remark.} Putting $ x = q^N $, 
$ \displaystyle B_n = {(q)_{2n+N} \over (q)_N} b_n $ and $ A_n = a_n $ this
inverse relation reads as:
   $$ B_n = \sum_{k=0}^n {2n+N \brack n-k} A_k $$
iff
   $$ A_n = \sum_{k=0}^n (-1)^{n-k} q^{n-k \choose 2} 
      {[2n+N] \over [n+N+k]} {n+N+k \brack n-k} B_k, \eqno (20) $$
which is a $q$-analogue of one of J. Riordon's inversion relations of the
Legendre type (cf.\ e.g. Hofbauer [20]).
          
I. Gessel and D. Stanton have first pointed out [18] that the Bailey transform
can be viewed as a matrix inversion, which contains (19) as a special case.
Using a matrix inverse observed by D. Bressoud [12] this approch is generalized
in [1] in order to establish the concept of Bailey lattices. 

The inverse relation (20) independently was derived by C. Krattenthaler
[22] as an application of his $q$-Lagrange formula (cf.\ also [26]).
\bigskip
A Bailey chain is in fact doubly infinite, for the pair $(a,b)$ can be uniquely
reconstructed from $ (a', b') $. Thus we also can move to the left in a
Bailey chain:
    $$ \cdots \leftarrow \bigl ((a_n), (b_n) \bigr) \leftarrow    
         \bigl ((a'_n), (b'_n) \bigr) \leftarrow \cdots $$
With respect to the Bailey chain of Theorem~2.2 we explicitly have 
\proclaim Theorem 2.4. 
  $$ b'_n = \displaystyle \sum_{k=0}^n {q^{k^2} x^k \over (q)_{n-k}} b_k \iff 
     b_n = \sum_{k=0}^n (-1)^{n-k} {q^{{n-k \choose 2}-n^2} \over (q)_{n-k}}
     x^{-n} b'_k. \eqno(21) $$

\noindent{\bf Proof.} For a proof see equation (3.42) of Andrews [3], which 
contains
(21) as a special case.    \endproof
\bigskip
\noindent{\bf Remark.} Substituting $ \rho_1 = q^{-a} $, $ \rho_2 = q^{-b}
$ and $ a = q^N $ in equation (3.42) of Andrews [3], equation (21) results from
the following inverse relation:
  $$ A_n = \sum_{k=0}^n {p+k \brack k} B_{n-k} \iff B_n = \sum_{k=0}^n (-1)^k
     q^{{k \choose 2}} {p+1 \brack k} A_{n-k}. \eqno(22) $$
This relation was proved by C. Krattenthaler in [21] as an application of
his $q$-Lagrange formula.
\bigskip
Another important way to produce a new Bailey pair $ \bigl ((A_n), (B_n)
\bigr) $ from a given one $ \bigl ((a_n), (b_n) \bigr) $ is the following
(see Andrews [2]).
\proclaim Theorem 2.5. If $ a_n = a_n (x,q) $, $ b_n = b_n(x,q) $ and 
    $$ \displaystyle b_n = \sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}} $$
then
    $$ \displaystyle B_n = \sum_{k=0}^n {A_k \over (q)_{n-k} (xq)_{n+k}}, $$
where $ A_k \defeq A_k (x,q) \defeq x^k q^{k^2} a_k (x^{-1}, q^{-1}) $ and
$ B_k \defeq b_k (x,q) \defeq x^{-k} q^{-k^2-k} b_k (x^{-1}, q^{-1}) $.

Example: From the well-known Gaussian identity
   $$\eqalignno{ 
     &\displaystyle \sum_{k=-\infty}^\infty {(-1)^k \over (q)_{n-k} (q)_{n+k}} =
      {1 \over (q^2-1) (q^4-1) \cdots (q^{2n}-1)}  &(23)\cr} $$
(see, e.g., Cigler [15, (1.4.7)]) we obtain by replacing $q$ by $q^{-1}$
   $$ \eqalignno{
      &\sum_{-\infty}^\infty {(-1)^k q^{k^2} \over (q)_{n-k} (q)_{n+k}} =
      {1 \over (q^2-1) (q^4-1) \cdots (q^{2n}-1)} &(24)\cr} $$
In many applications the following Bailey pair generation is useful
(cf.\ Paule [Lemma 2, 24])

\proclaim Lemma 2.1. If $ c \in {\bf R} $ and 
  $$ \displaystyle b_n = \sum_{k= - \infty}^\infty {(-1)^k q^{ck^2-ck} \over 
     (q)_{n-k} (q)_{n+k}} $$
then
  $$ \displaystyle q^{-n} b_n = \sum_{k= -\infty}^\infty {(-1)^k q^{ck^2-(c-1)
     k} \over (q)_{n-k} (q)_{n+k}}. $$

Thus given a Bailey pair $ \bigl ((a_n)_{-\infty}^{\infty}, 
(b_n)_0^{\infty} \bigr) $, where  $ a_n = (-1)^n q^{cn^2 - cn}, $ 
a new Bailey pair is constituted by
$ \bigl ((q^n a_n)_{-\infty}^{\infty}, (q^{-n} b_n)_0^{\infty} \bigr)$. 
\bigskip
One example of the wide range of application of the Bailey chain concept
lies in the field of multiple series generalizations of identities of the
Rogers-Ramanujan type (cf.\ Andrews [2]).

As an example we consider the analytic counterpart to Gordon's partition
theorem~[19] discovered by Andrews [5]:
  $$ \prod^{\infty}_{{\scriptstyle n=1 \atop 
                      \scriptstyle n\not\equiv 0,\pm r \pmod{2s+1}} \atop
                     \scriptstyle 1 \le r \le s}
         {(1-q^n)^{-1}} = 
     \sum_{n_1 \ge \cdots n_{s-1} \ge 0} {q^{n^2_1 + n^2_2 + \cdots + 
     n^2_{s-1} + n_r + \cdots + n_{s-1}} \over (q)_{n_1-n_2} (q)_{n_2-n_3}
     \cdots (q)_{n_{s-1}}}.\eqno(25) $$

According Jacobi's identity (6) the left hand side of (25) is equal to 
  $$ {1 \over (q)_\infty} \sum_{k= -\infty}^\infty (-1)^k 
     q^{(s+{1 \over 2})k^2 - (s-r+{1 \over2})k} \defeq A_{r,s}. $$

Now the case $r=s$ is immediately obtained by walking along a Bailey
chain as far as we arrive at a simple special case (16) of the $q$-binomial
theorem.                        
  $$\eqalign{  
     A_{s,s}   
     & = {1 \over (q)_\infty} \sum_{k=-\infty}^\infty (-1)^k   
         q^{(s+{1 \over 2})k^2 - {1 \over 2}k}                      \cr
     &\buildrel (15) \over=
          \sum_{n_1=0}^{\infty} q^{n^2_1}  
          \sum_{k=-\infty}^\infty {(-1)^k q^{(s+{1 \over 2})k^2 - 
          {1 \over 2}k} \over (q)_{n_1-k} (q)_{n_1+k}}          \cr
     &\buildrel (13) \over=
          \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty {q^{n^2_2} 
          \over (q)_{n_1-n_2}} \cdots \sum_{n_{s-1}=0} {q^{n^2_{s-1}} \over
          (q)_{n_{s-2}-n_{s-1}}} \times {}                         \cr
     &\quad \times \sum_{nB_{s=0}}^{\infty} {q^{n^2_s} \over (q)_{n_{s-1}-n_s}}
          \sum_{k=-\infty}^\infty {(-1)^k q^{{1 \over 2}k^2-{1 \over 2}k}
          \over (q)_{n_s-k} (q)_{n_s+k}}                           \cr
     &\buildrel (16) \over=
          \sum_{n_1 \ge \cdots n_{s-1} \ge 0} {q^{n^2_1+n^2_2+ \cdots +
          n^2_{s-1}} \over (q)_{n_1-n_2} (q)_{n_2-n_3} 
          \cdots (q)_{n_{s-1}}}. \cr} $$

We observe that for $r\ne s$ this Bailey chain does not arrive at the 
$q$-binomial theorem. Now the way out of that problem is to leave the original
chain at some point by switching to a new Bailey pair and continuing the
Bailey chain walk with that new pair as a new starting point. If desired,
we may repeat this process. Moving like that the authors of [1] would call
a walk in a {\it Bailey lattice}. 
                               
As an example we look at the case $r\ne s$ of equation (25) (cf.\ Paule [24]). 
We have 
  $$ A_{r,s} \buildrel (15) \over= \sum_{n_1=0}^\infty q^{n^2_1}
\sum_{k=-\infty}^\infty {(-1)^k q^{(s-{1 \over 2})k^2-(s-r+{1\over 2})k} \over
(q)_{n_1-k} (q)_{n_1+k}}. $$ 
Now we apply (13) $(r-1)$-times, which gives
  $$\eqalign{ A_{r,s}&= \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty
     {q^{n^2_2} \over (q)_{n_1-n_2}} \cdots \sum_{n_r=0}^\infty {q^{n^2_r} \over
     (q)_{n_{r-1}-n_r}} \times {} \cr
   &\quad \times \sum_{k=-\infty}^\infty {(-1)^k
     q^{(s-r+{1\over 2})k^2-(s-r+{1\over2})k} \over 
     (q)_{n_r-k} (q)_{n_r+k}}. \cr} $$
According to Lemma~2.1 we now switch to a new Bailey pair: 
  $$\eqalign{
     A_{r,s}&= \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty 
     {q^{n^2_2} \over
     (q)_{n_1-n_2}} \cdots \sum_{n_r=0}^\infty {q^{n^2_r} \over
     (q)_{n_{r-1}-n_r}}\times {} \cr 
    &\quad \times q^{n_r} \sum_{k=-\infty}^\infty
     {(-1) q^{(s-r+{1\over 2})k^2-
     (s-r-{1\over 2})k} \over (q)_{n_r-k} (q)_{n_r+k}}. \cr} $$
Now we move one step in the new Bailey chain by (13): 
  $$\eqalign{ 
     A_{r,s}&=\sum_{n_1=0}^\infty
     q^{n^2_1} \sum_{n_2=0}^\infty {q^{n^2_2} \over (q)_{n_1-n_2}} \cdots
    \sum_{n_r=0}^\infty {q^{n^2_r+n_r} \over (q)_{n_{r-1}-n_r}} \times {} \cr
   &\quad \times \sum_{n_{r+1}=0}^\infty 
    {q^{n^2_{r+1}} \over (q)_{n_r-n_{r+1}}}
    \sum_{k=-\infty}^\infty 
     {(-1)^k q^{(s-r-{1\over 2})k^2-(s-r-{1\over2})k} \over
     (q)_{n_{r+1}-k} (q)_{n_{r+1}+k}}. \cr}  $$
We repeat this process of applying Lemma~2.1 followed by~(13) until we arrive
at
  $$\eqalign{ 
     A_{r,s}&= \sum_{n_1 \ge \cdots \ge n_s \ge 0} 
     {q^{n_1^2+n^2_2+\cdots + n^2_s+n_r+\cdots +n_s} \over
     (q)_{n_1-n_2} (q)_{n_2-n_3} \cdots (q)_{n_{s-1}-n_s}} \times {} \cr
    &\quad \times
     \sum_{k=-\infty}^\infty {(-1)^k q^{{1\over 2}k^2-{1\over 2}k} \over
     (q)_{n_s-k} (q)_{n_s+k}}, \cr} $$
which now is reduced by the special case (16) of the $q$-binomial theorem to
  $$ A_{r,s}= \sum_{n_1 \ge \cdots \ge n_{s-1} \ge 0} 
     {q^{n^2_1+\cdots +n^2_{s-1}+n_r+\cdots +n_{s-1}} \over (q)_{n_1-n_2}
     (q)_{n_2-n_3} \cdots (q)_{n_{s-1}}}. $$
This proves equation (25).   \endproof
\bigskip
Now there is another Bailey chain walk to prove equation~(25) which brings
identity~(14), the counterpart of~(13), into play
(cf.\ Agarwal-Andrews-Bressoud [1]). To demonstrate this we first need

\proclaim Lemma 2.2. If $c \in {\bf R} $ and 
   $$ b_n= \sum_{k=-\infty}^\infty {(-1)^k q^{(c+1)k^2-ck} \over (q)_{n-k}
      (q)_{n+k}} $$
then
   $$ b_n= \sum_{k=-\infty}^\infty {(-1)^k q^{(c+1)k^2+ck} \over (q)_{n-k}
      (q)_{n+1+k}}, $$
and vice versa.

\noindent{\bf Proof.} To prove Lemma 2.2 is equivalent to show that 
  $$ \sum_{k=-\infty}^\infty {2n+1 \brack n-k}(-1)^k q^{(c+1)k^2+ck}
     =(1-q^{2n+1}) \sum_{k=-\infty}^\infty {2n \brack n-k} (-1)^k
     q^{(c+1) k^2-ck}. $$
Using the recurrence formula 
  $$ {r+1 \brack s} = {r \brack s}+q^{r-s+1} {r \brack s-1} $$
the left hand side of this equation becomes
  $$ \eqalign{
     \sum_{k=-\infty}^\infty {2n \brack n-k}(-1)^k
     q^{(c+1)k^2+ck}-q^{n+1} \sum_{k=-\infty}^\infty {2n \brack n-k}
     (-1)^k q^{(c+1)k^2-(c+1)k} \hfill \cr
     =(1-q^{2n+1}) \sum_{k=-\infty}^\infty {2n \brack n-k}(-1)^k
     q^{(c+1)k-ck}. \cr} $$
The last line follows by Lemma 2.1.\endproof
\bigskip
Behind Lemma 2.2 lies the following important observation:
\medskip
\noindent{\sl It is possible to pass from a Bailey pair $ \bigl ((a_n), (b_n)
\bigr) $ {\rm relative to $x$}, i.e.
   $$ b_n= \sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}}, $$
to a Bailey pair $ \bigl((a'_n), (b'_n) \bigr) $ {\rm relative to
$y$}, i.e.
   $$ b'_n= \sum_{k=0}^n {a'_k \over (q)_{n-k} (yq)_{n+k}}. $$}
In practice $y$ will be $x$ times an integer power of $q$.

Example: By Lemma 2.2 we immediately get 
   $$ \sum_{k=-\infty}^\infty {(-1)^k q^{{3 \over 2}k^2+{1\over 2}k} \over
      (q)_{n-k} (q)_{n+1+k}}={1 \over (q)_n},  \eqno(26) $$
the counterpart of the Bailey pair corresponding to equation~(17).

\noindent{\bf Remark.} This problem was first considered by D. Bressoud
[1] and Agarwal-Andrews-Bressoud [13] in the general context of matrix inversion
and motivated these authors to introduce the notion of a {\it Bailey lattice}.
\bigskip
Now we present a second proof of equation (25) by a different Bailey chain
walk:
 $$\eqalign{
    A_{r,s}
    &\buildrel (15) \over=
   \sum_{n_1=0}^\infty q^{n^2_1} \sum_{k=-\infty}^\infty {(-1)^k 
    q^{(s-{1\over 2})k^2-(s-r+{1\over 2})k} \over (q)_{n_1-k} 
    (q)_{n_1+k}}                                            \cr
   &\buildrel (13) \over=
    \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty {q^{n^2_2} \over 
    (q)_{n_1-n_2}} \cdots \sum_{n_{r-1}=0}^\infty {q^{n^2_{r-1}} \over
    (q)_{n_{r-2}-n_{r-1}}} \times {}                        \cr
   &\quad \times \sum_{k=-\infty}^\infty
    {(-1)^k q^{(s-r+{3\over 2})k^2-(s-r+
    {1\over 2})k} \over (q)_{n_{r-1}-k} (q)_{n_{r-1}+k}}    \cr
   &\buildrel \rm(Lemma\ 2.2) \over=
    \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty {q^{n^2_2} \over
    (q)_{n_1-n_2}} \cdots \sum_{n_{r-1}=0} ^\infty {q^{n^2_{r-1}} \over
    (q)_{n_{r-2}-n_{r-1}}} \times {}                        \cr
   &\quad \times \sum_{k=-\infty}^\infty {(-1)^k q^{(s-r+{3\over 2})k^2+
    (s-r+{1\over 2})k} \over (q)_{n_{r-1}-k} (q)_{n_{n-r}+1+k}}. \cr} $$
Now we walk along the Bailey chain by repeated application of (14) as far
as we arrive at
  $$ \eqalign{
       A_{r,s}&= 
          \sum_{n_1=0}^\infty q^{n^2_1} \sum_{n_2=0}^\infty 
          {q^{n^2_2} \over (q)_{n_1-n_2}} \cdots \sum_{n_{r-1=0}}^\infty
          {q^{n^2_{r-1}} \over (q)_{n_{r-2}-n_{r-1}}} \times{} \cr
          & \quad \times \sum_{n_{r=0}}^\infty {q^{n^2_r+n_r} \over
          (q)_{n_{r-1}-n_r}} \cdots \sum_{n_{s-1=0}}^\infty
          {q^{n^2_{s-1}+n_{s-1}} \over (q)_{n_{s-2}-n_{s-1}}} \times {}\cr     
          &\quad \times \sum_{k=-\infty}^\infty {(-1)^k q^{{3\over 2}k^2+
          {1\over 2}k} \over (q)_{n_{s-1}-k} (q)_{n_{s-1}+1+k}}  \cr
          &= \sum_{n_1\ge\cdots\ge n_{s-1}\ge0} {q^{n^2_1+n_2^2+\cdots+
          n^2_{s-1}+n_r+\cdots+n_{s-1}} \over (q)_{n_1-n_2} (q)_{n_2-n_1}
          \cdots (q)_{n_{s-1}}}.          \cr} $$
The last line follows from equation (26). This proves equation (25). \endproof
\bigskip
In this proof we first walked along the Bailey chain corresponding to
identity~(13). After that, we made a side-step changing the parameter $x=1$
to $x=q$ and continued our walk along the Bailey chain corresponding to
identity~(14). Finally we arrived at a Bailey pair, which we recognized as the 
$(x=q)$-counterpart (26) of (17).

Thus we have seen that identity (25) has been proved by two different walks
in a Bailey lattice.

In Agarwal-Andrews-Bressoud [1] identity (25) is proved as a special case of
a very general theorem [Theorem 3.1, 1], which is based on a Bailey lattice
walk with one parameter change of $x$ to $xq^{-1}$.
\bigskip
Concluding this section we make some remarks on changing the parameter $x$.
\bigskip                                           
Given a Bailey pair $ \bigl((a_n), (b_n) \bigr)$, i.e.
  $$ b_n= \sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}}, $$
we substitute $x=q^N$. This motivates the following 

\proclaim Definition. Two sequences $(A_n)$, $(B_n)$ form a\/
{\rm $q$-binomial} (or simply\/ {\rm binomial})\/ {\rm Bailey pair relative
to $N$}, if 
  $$ B_n= \sum_{k=0}^n {2n+N \brack n-k} A_k. $$
\bigskip
Each Bailey pair $ \bigl ((a_n), (b_n) \bigr)$, where
  $ b_n= \sum_{k=0}^n {a_k \over (q)_{n-k} (xq)_{n+k}} $ with $x=q^N$,
can be turned into a binomial Bailey pair (by defining $ A_n \defeq a_n$
and $ B_n \defeq {(q)_{2n+N} \over (q)_N}b_n $) and vice versa.

Now changing the parameter $x$ to $xq^{-1}$ is expressed as
\proclaim Theorem 2.6. If $ \bigl ((A_n), (B_n) \bigr) $ is a binomial Bailey
pair relative to $N$, i.e.
  $$ B_n= \sum_{k=0}^n {2n+N \brack n-k}A_k, $$
then $ \bigl ((A'_n), (B'_n) \bigr) $ is a binomial Bailey pair relative
to $N-1$, i.e.
  $$ B'_n= \sum_{k=0}^n {2n+N-1 \brack n-k} A'_k, $$
where 
  $$ A'_n \defeq {A_k \over [2k+N]}-q^{2k+N-2} 
        {A_{k-1} \over [2k+N-2]} \quad{(A_{-1} \defeq 0)} $$
and
     $$ B'_n \defeq {B_n \over [2n+N]}. $$

\noindent{\bf Proof.} For $k\ne n$ we conclude from
  $$ {2n+N \brack n-k}={[2n+N] \over [n-k]} {2n+N-1 \brack n-k-1} $$
and
  $$ {2n+N-1 \brack n-k}=
     {[n+k+N] \over [n-k]} {2n+N-1 \brack n-k-1} =
     \left ({[2k+N] \over [n-k]}+q^{2k+N} \right) {2n+N-1 \brack n-k-1} $$
that
  $$ {2n+N \brack n-k}={[2n+N] \over [2k+N]} \left ({2n+N-1 \brack n-k}
     -q^{2k+N} {2n+N-1 \brack n-k-1} \right). $$
Thus
  $$ \eqalign{
     B'_n & = {B_n \over [2n+N]}= {1 \over [2n+N]} \sum_{k=0}^n
              {2n+N \brack n-k}A_k   \cr
          & = {A_n \over [2n+N]}+ \sum_{k=0}^{n-1} {2n+N-1 \brack n-k} 
              {A_k \over [2k+N]}- \sum_{k=1}^n {2n+N-1 \brack n-k}
              {q^{2k+N-2}A_{k-1} \over [2k+N-2]}      \cr
          & = {2n+N-1 \brack n} {A_0 \over [N]}+ \sum_{k=1}^n {2n+N-1 \brack
              n-k}A'_k,  \cr} $$
which proves Theorem 2.6.  \endproof
\bigskip
It is easily seen that the important Lemma 2.2 is contained in Theorem 2.6
as a special case: (set $N=1$ and $A_k=(-1)^k q^{(c+1)k^2+ck})$.

As we shall see in the next section a generalization of Theorem 2.6, which
is the key result (Lemma 1.2) of the Agarwal-Andrews-Bressoud paper~[1],
is also a straight-forward application of Theorem 2.6.
\bigskip
What happens if we want to change the parameter $x$ to $xq$? We treat this
question as a transition from a binomial Bailey pair relative to $N-1$ to
a binomial Bailey pair relative to $N$. The inversion of Theorem~2.6 yields
\proclaim Theorem 2.7. If $ \bigl ((A'_n), (B'_n) \bigr) $ is a binomial
Bailey pair relative to $N-1$, i.e.
   $$ B'_n=\sum_{k=0}^n {2n+N-1 \brack n-k} A'_k, $$
then $ \bigl ((A_n), (B_n) \bigr) $ is a binomial Bailey pair relative to
$N$, i. e. 
  $$ B_n=\sum_{k=0}^n {2n+N \brack n-k}A_k, $$
where
  $$ A_k \defeq [2k+N] q^{k^2+(N-1)k} \sum_{j=0}^k q^{-j^2-(N-1)j} A'_j$$
and
  $$ B_n \defeq [2n+N]B'_n. $$
\bigskip
\noindent{\bf Proof.} The proof is a simple matrix inversion using the
inversion relation
  $$ x_k=\sum_{j=0}^k y_j  \iff y_k=x_k-x_{k-1} \quad{(x_{-1} \defeq 0)},$$
with
  $$ \displaystyle x_k \defeq q^{-k^2-(N-1)k} {A_k \over [2k+N]}, y_k \defeq
     q^{-k^2-(N-1)k}A'_k, $$
assuming that $(A_k)$ and $(A'_k)$ are connected as in Theorem~2.6. \endproof

Example: Identity (24) can be rewritten as 
  $$ \sum_{k=0}^n {2n \brack n-k}A'_k=B'_n, $$ 
where $A'_0=1$, $A'_k=2(-1)^k q^{k^2} \quad{k \ge 1}$ and $B'_n=(q;q^2)_n$.

Now Theorem~2.7 with $N=1$ yields
  $$ A_k=[2k+1](-1)^k q^{k^2} \hbox{and} B_n=[2n+1](q;q^2)_n, $$
which gives
  $$ \sum_{k=-\infty}^\infty {2n+1 \brack n-k}(-1)^k q^{k^2}=(q;q^2)_{n+1}$$
as the $(N=1)$-counterpart of (24).
\goodbreak\aboveheaderskip   

\centerline{\bigbf 3. Generalizations}
\bigskip 
{\bf 3.1 An extension of Bailey's Lemma.} In this section we shall consider
a generalization of Bailey's Lemma, which contains Theorem 2.1 as a limiting
case.                                      
\proclaim Definition. For $ n_1+n_2+\cdots +n_j=n $ we define
  $$ {n \brack n_1, n_2,\cdots , n_j} \defeq \displaystyle {[n]! \over [n_1]!
     [n_2]!\cdots [n_j]!} $$
($q$-multinomial coefficient).

We formulate this extended form of Bailey's Lemma in the language of
$q$-multinomial coefficients:

\noindent{\bf Theorem 3.1.} {\it If $ \bigl ((A_n), (B_n) \bigr) $ is a binomial
Bailey pair relative to $N$, then $ \bigl ((A'_n), (B'_n) \bigr) $ is also
a binomial Bailey pair relative to $N$, where
  $$ A'_k \defeq {2a+N \brack a-k} {2b+N \brack b-k} q^{Nk+k^2}A_k $$
and}
  $$ B'_n \defeq \displaystyle{[2a+N]![2b+N]![2n+N]! \over [a+b+N]![b+n+N]!
     [n+a+N]!} \sum_{j=0}^n {a+b+n+N-j \brack a-j, b-j, n-j, 2j+N} q^{N_j
     +j^2} B_j. $$
This is what G. Andrews denotes by "Baileys's Lemma" in [(2.3)-(2.6), 2] with
$ \rho_1=q^{-a}, \rho_2=q^{-b} $ and the parameter $a$ replaced by $q^N(=x)$.
\bigskip
W. N. Bailey described in \S 4 of [9] how to get Theorem~3.1, but he never
carried it out explicitly. The reason for that may lie in the
fact that he did not observe the iteration mechanism hidden in his Lemma
(Theorem~2.2). Bailey's Lemma was first stated in full generality by G.
Andrews in [2] and P. Paule [23] independently observed the important special
cases $N=0$ and $N=1$ of 
 $$ \eqalignno{
    & \sum_{k=0} {a+b+N \brack a-k} {b+c+N \brack b-k} {c+a+N \brack c-k}
     q^{k^2+Nk}A_k \cr
    &= \sum_{j=0} {a+b+c+N-j \brack a-j, b-j, c-j, 2j+N} q^{j^2+Nj}B_j, 
     & (27)\cr} $$
where
  $$ B_j=\sum_{k=0}^j {2j+N \brack j-k}A_k $$
(see D1 and D2 of Paule [23]).

It is easily checked that (27) is an equivalent reformulation of Theorem~3.1.
\bigskip
Now we come back to the key result Lemma~1.2 of Agarwal-Andrews-Bressoud
[1], which can be rewritten as 
  $$ \eqalignno{
    & \sum_{k=0}^n {a+b+N-1 \brack a-k} {b+n+N-1 \brack b-k} {n+a+N-1 \brack
     n-k} q^{k^2+(N-1)k}A'_k  \cr
    &= \sum_{j=0}^n {a+b+n+N-1 \brack a-j, b-j, n-j, 2j+N-1} q^{j^2+(N-1)j}
     B'_j, & (28)\cr} $$
where
  $$ A'_k= \displaystyle {A_k \over [2k+N]}-q^{2k+N-2} {A_{k-1} \over [2k+N-2]}
     \quad (A_{-1} \defeq 0) $$
and
  $$ B'_n= \displaystyle {B_n \over [2n+N]}. $$
(See (1.9) of Agarwal-Andrews-Bressoud [1] with $ \rho=q^{-a}, 
\delta=q^{-b} $ and $ a=q^N$.)
\bigskip
Now, if $ \bigl ((A_n), (B_n) \bigr) $ forms a binomial Bailey pair,
equation~(28), i. e. Lemma 1.2 of [1], is immediately proved by (27) and
Theorem~2.6.
\bigskip
If we let $c$ tend to infinity in equation (27), we obtain a formula, which
is equivalent to Theorem~2.1. (cf.\ Paule [24]). In this resulting formula
it is possible to send $b$ to infinity, which gives identity (12) with $x$
replaced by $q^N$, and finally $a$ to infinity, which yields a general equation
(15) (with parameter $x=q^N$ instead $x=1$).
\bigskip
G. Andrews observed [3] that also in this general case we can walk backwards
in the Bailey chain. Thus is, because walking along the Bailey chain now
means to construct a sequence of Bailey pairs
  $$ \cdots \rightarrow \bigl ((A_n), (B_n) \bigr) \rightarrow    
         \bigl ((A'_n), (B'_n) \bigr) \rightarrow \cdots $$ 
{\it according to Theorem~3.1,} a process, which can be reversed by
  $$ A_k={2a+N \brack a-k}^{-1} {2b+N \brack b-k}^{-1} q^{-k^2-Nk}A'_k $$
and
  $$ \eqalign{
    B_n
     &= q^{-n^2-Nn} \displaystyle{(q)_{a-n} (q)_{b-n} \over (q)_a (q)_b
        (q)_{a+N} (q)_{b+N}} \times {}             \cr
     &\quad \times \sum_{k=0}^n (-1)^{n-k} q^{n-k \choose 2} {a+b+N+1 \brack
      n-k} B'_k.  \cr} $$
Also this extension of (21) is an application of the inverse relation~(22).
\bigskip
If $N=0$ or $N=1$ it is possible to symmetrize identity (27) as follows:
  $$ \eqalignno{
     &\sum_{k=-\infty}^\infty {a+c+\rho \brack a-k} {b+c+\rho \brack b-k}
     {c+a+\rho \brack c-k} c_k  &(29)           \cr
     &= \sum_{j=0}^\infty {a+b+c+\rho-j \brack a-j, b-j, c-j, 2j+\rho} 
     q^{j^2+\rho j}                    \times {}             \cr
     & \quad \times \sum_{k=-\infty}^\infty {2j+1 \brack j-k} 
       q^{-k^2-\rho k}c_k, \cr}$$
where $ \rho=0$ or $1$ (cf.\ Paule [23]).

Example. In [$(B)$ and $(B'), 14$] P. Cartier and D. Foata proved 
 $$ \eqalignno{
    &\sum_{k=-\infty}^\infty \left({b+c+\rho \atop c+k} \right) 
    \left({c+a+\rho \atop a+k} \right) \left({a+b+\rho \atop b+k} \right)
    u^{p+k} v^{p-k+\rho} \cr
    &= \sum_{n=0}^p \displaystyle {(a+b+c-n+\rho)! \over (a-n)! (b-n)! (c-n)!}
    (uv)^{p-n} {(u+v)^{2n+\rho} \over (2n+\rho)!}, & (30)\cr} $$  
where $ \rho=0 $ or $1$. (For the case $ \rho=0$ see D. Foata [17])

By (29) and the $q$-binomial theorem in the form (5) or its $(N=1)$-counterpart
 $$ \sum_{k=-\infty}^\infty {2n+1 \brack n-k} (-1)^k x^k q^{{1\over 2}k^2}
    = (x^{-1} q^{{1\over 2}})_n (xq^{{1\over 2}})_{n+1}, \eqno(31) $$
respectively, the following $q$-analogue of (30) can be given:
  $$ \eqalignno{
     &\sum_{k=-\infty}^\infty {b+c+\rho \brack c+k} {c+a+1 \brack a+k}  
     {a+b+\rho \brack b+k} q^{{3\over 2}k^2-{1\over 2}k} 
     ({u \over v})^k  & (32)\cr
     &= \sum_{n=0} \displaystyle {[a+b+c-n+\rho]! \over [a-n]![b-n]![c-n]!}
     {(-{v\over u}q^{1-\rho})_n 
     (-{u\over v} q^\rho)_{n+\rho} \over [2n+\rho]!}, \cr} $$
where $\rho=0$ or $1$.

\noindent{\bf Remark.} In proving equation (30) P. Cartier and D. Foata
gave a purely combinatorial proof of 
  $$ \eqalignno{
     & \left({b+c+\rho \atop c+k} \right) \left({c+a+\rho \atop a+k} \right)
     \left({a+b+\rho \atop b+k} \right)       & (33) \cr  
     &= \sum_n \displaystyle {(a+b+c+n-\rho)! \over (a-n)! (b-n)! (c-n)!
     (n+k)!(n-k+\rho)!}, \cr} $$
where $ \rho=0$ or $1$ (a {\it Pfaff-Saalsch\"utz} summation).

From that the proof of (29), the extension of Bailey's Lemma in the cases
$N=0$ or $1$, for $q=1$ is simple: one just has to multiply equation (32)
by coefficients $c_k$ and to sum over all possible $k'$s and finally change
the order of summation.

Recently [31] D. Zeilberger $q$-analogized the Cartier-Foata proof of (32)
to show
  $$ \eqalignno{
     &{b+c \brack c+k} {c+a \brack a+k} {a+b \brack b+k}=   &(34) \cr
     &= \sum_n q^{n^2-k^2} \displaystyle {[a+b+c-n]! \over [a-n]! [b-n]!
     [c-n]! [n+k]! [n-k]!}. \cr}$$
This gives equation (29) with $ \rho=0$ as described above.
\bigskip
\noindent{\bf 3.2 Concluding Remarks.} Bailey's Lemma and the concept of
Bailey chains have a wide range of application in additive number theory,
combinatories and special functions, and physics (R. J. Baxter's hard hexagon
model in statistical mechanics, see e.g. R. J. Baxter [11]). For these 
applications one should consult
G. Andrews [2] and his $q$-series compendium [3], which contains also an
extensive reference list.

In [2] G. Andrews pointed out that {\it all} of the 130 Rogers-Ramanujan type
identities given in Slater's list [29] posess multiple series generalizations
as equation (25), which contains the Rogers-Ramanujan identities. 
(e.g. $ s=2 $ and $ r=2 $ in (25) yields (7)).

Let us close with an example of H. Cohen [16], where two important special cases
of equation (25) arise in an {\it algebraic} context:
  $$   \sum_{G \atop p^{k-1}G=0} \mid Aut G \mid^{-1} =             
       \prod^{\infty}_{{\scriptstyle n=1 \atop 
                      \scriptstyle n\not\equiv 0,\pm k \pmod{2k+1}}}  
                      (1-p^{-n})^{-1} $$
and
  $$  \sum_{G \atop p^{k-1}G=0} {\mid Aut G \mid^{-1} \over \mid G \mid} =             
       \prod^{\infty}_{{\scriptstyle n=1 \atop 
                      \scriptstyle n\not\equiv 0,\pm 1 \pmod{2k+1}}}  
                      (1-p^{-n})^{-1} $$
where the sums are over all isomorphism classes of abelian $p$-groups
annihilated by $ p^{k-1}$ ($p$ a prime).
\goodbreak\aboveheaderskip 
\centerline{\bigbf 4. References}
\bigskip                     
1. A. K. AGARWAL, G. E. ANDREWS, D. M. BRESSOUD, The Bailey Lattice, J.
Indian Math. Soc., to appear.
\bigskip
2. G. E. ANDREWS, Multiple series Rogers - Ramanujan type identities, Pac.
J. Math., 114 (1984), 267-283.
\bigskip
3. G. E. ANDREWS, "$q$-series: their development and application in analysis,
number theory, combinatories, physics and computer algebra", CBMS Regional
Conference Series in Mathematics, 66 (AMS, Providence, 1986).
\bigskip
4. G. E. ANDREWS, "The Theory of Partitions", Encyclopedia of Mathematics
and its Applications, vol. 2., Addison - Wesley, 1976.
\bigskip
5. G. E. ANDREWS, An analytic generalization of the Rogers - Ramanujan
identities for odd moduli, Proc. Nat. Acad. Sci. USA, 71 (1974), 4082-4085.
\bigskip
6. G. E. ANDREWS, Connection coefficient problems and partitions, Proc.
of Symposia in Pure. Math. 34 (1972), 1-24. 
\bigskip
7. R. ASKEY, Preface of "Special Functions: Group Theoretical Aspects and
Applications", Editors: R. A. Askey, T. H. Koornwinder and W. Schempp, D.
Reidel, 1984.
\bigskip
8. W. N. BAILEY, Some identities in combinatory analysis, Proc. London Math.
Soc. (2), 49 (1947), 421-435.
\bigskip
9. W. N. BAILEY, Identities of the Rogers - Ramanujan type, Proc. London Math.
Soc. (2), 50 (1949), 1-10.
\bigskip
10. W. N. BAILEY: "Generalized Hypergeometric Series". Cambridge Univ. Press
1935 (Reprinted: Hafner New York 1964).
\bigskip
11. R. J. BAXTER, "Exactly Solved Models in Statistical Mechanics", Acad.
Press 1982.
\bigskip
12. D. M. BRESSOUD, A matrix inverse, Proc. of the AMS 88 (1983), 446-448.
\bigskip
13. D. M. BRESSOUD, The Bailey Lattice: An Introduction, to appear in the
Proceedings of the Ramanujan Centenary Conference, Illinois at Urbana -
Champaign, 1987.
\bigskip
14. P. CARTIER, D. FOATA, "Problemes combinatoires de commutation et
rearrangements", Springer Lect. Notes in Math. 85 (1969).
\bigskip
15. J. CIGLER, Elementare $q$-Identit\"aten, Seminaire Lotharingen de
Combinatoire, $5^e$ Session, Sainte-Croix-aux Mines, 1982.
\bigskip
16. H. COHEN, On the $p^k$-rank of finite abelian groups and Andrew's
generalizations of the Rogers - Ramanujan identities, Indag. Math. 88 (1985),
377-383.
\bigskip
17. D. FOATA, Etude algebrique de certains problemes d'Analyse Combinatoire
et du Calcul des Probabilites, Publ. Inst. Statist. Univ. Paris, 14 (1965),
81-241. 
\bigskip
18. I. GESSEL, D. STANTON, Applications of $q$-Lagrange inversion to basic
hypergeometric series, Trans. Amer. Math. Soc., 277 (1983), 173-201.
\bigskip
19. B. GORDON, Some identities in combinatorial analysis, Quart. J. Math.
Oxford Ser., 12 (1961), 285-290.
\bigskip
20. J. HOFBAUER, Langrange Inversion, Seminaire Lotharingien de Combinatoire,
6 eme session, Burg Feuerstein 1982.
\bigskip
21. C. KRATTENTHALER, "$q$-Lagrangeformel und inverse Relationen", Ph.
D. Thesis, University of Vienna, 1982.
\bigskip
22. C. KRATTENTHALER, A new $q$-Lagrange formula and some applications,
Proc. of the AMS 90 (1984), 338-344.
\bigskip
23. P. PAULE, "Zwei neue Transformationen als elementare Anwendungen der
$q$-Vandermonde Formel", Ph. D. Thesis, University of Vienna, 1982.
\bigskip                                                     
24. P. PAULE, On identities of the Rogers - Ramanujan type, J. Math. Anal.
and Appl. 107 (1985), 255-284.
\bigskip
25. P. PAULE, A note on Bailey's lemma, J. Comb. Th. (A) 44 (1987), 164-167.
\bigskip
26. P. PAULE, Ein neuer Weg zur $q$-Lagrange Inversion, Bayreuther Math.
Schriften 18 (1985), 1-37.
\bigskip
27. L. J. ROGERS, Second memoir on the expansion of certain infinite products,
Proc. London Math. Soc. 25 (1894), 318-343.
\bigskip
28. L. J. ROGERS, Third memoir on the expansion of certain infinite products,
Proc. London Math. Soc. 26 (1895), 15-32.
\bigskip
29. L. J. SLATER, Further identities of the Rogers - Ramanujan type, Proc.
London Math. Soc. (2), 54 (1952), 147-167.
\bigskip
30. L. J. SLATER: "Generalized Hypergeometric Functions". Cambridge Univ.
Press, London and New York, 1966.
\bigskip
31. D. ZEILBERGER, A $q$-Foata proof of the $q$-Saalsch\"utz identity,
preprint. 
\bigskip
\bigskip
\noindent{\it Peter Paule, RISC-Linz (Research Institute for Symbolic 
Computation), 
Johannes-Kepler-Universit\"at Linz, A-4040 LINZ, AUSTRIA}
\bye
   
