qWZTheory and Bailey Chains
Peter Paule
RISC, J. Kepler University of Linz, Austria
Algorithms Seminar
February 16, 1998
[summary by Bruno Gauthier and Bruno Salvy]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Many combinatorial identities can be formulated in terms of
qhypergeometric sums, for instance, the celebrated RogersRamanujan
identities from additive number theory. Identities of this type can be
constructed iteratively from simpler ones, i.e., by proceeding along
Bailey chains. Another construction mechanism, different from this
classical one, arises within the context of qWZtheory. For
instance, as a byproduct of computer proofs, one automatically
obtains the socalled ``dual'' identities. The talk gives a short
tutorial introduction and discusses various relations between
these concepts.
The talk consists of four parts. The first part is an introduction to
Gaussian polynomials. The second part is a brief account of
qhypergeometric WZ theory. The parts that follow are variations
on this theme.
1 Gaussian polynomials
Let p(m,n;k) denote the number of partitions of k in at most
m parts, each part £ n . Clearly,
p(m,n;k) 
= 0, if k > mn, 
p(m,n;mn) 
= 1. 
Therefore the generating function
G_{m,n}(q) = å_{k=0}^{mn} p(m,n;k) q^{k}
is a polynomial in q of degree m n .
A few particular instances are:
G_{m,0}(q) 
= 1,
G_{0,n}(q) = 1,
G_{m,n}(q) = G_{n,m}(q),
G_{m,1}(q) = 

, 

G_{4,3}(q) 
= 1 + q + 2q^{2} + 3q^{3} + 4q^{4} + 4q^{5} + 5q^{6}
+ 4q^{7} + 4q^{8} + 3q^{9} + 2q^{10} + q^{11} + q^{12}. 
From the decomposition
p(m,n;k) = p(m1,n;kn)+ p(m,n1;k) (k³ n)
follows that
G_{m,n}(
q) =
q^{n} G_{m1,n}(
q) +
G_{m,n1}(
q).
(1)
By symmetry, we also have:
G_{m,n}(
q) =
G_{m1,n}(
q) +
q^{m} G_{m,n1}(
q).
(2)
So, by elimination between (1) and (2):
G_{m,n}(q)
= 

G_{m,m1}(q)
= 
(1q^{m+n}) ··· (1q^{m+1}) 

(1q^{n}) ··· (1q) 

G_{m,0}(q).

Using the standard notation (a;q)_{k}=(1a)(1aq)···(1aq^{k1}),
k = 1,2,... and (a;q)_{k}=1/(a;q)_{k} for k<0, we get a closed
form representation
of the Gaussian polynomials G_{m,n} :


:= G_{m,n}(q)
= 
(1q^{m+n}) ··· (1q^{m+1}) 

(1q^{n}) ··· (1q) 

= 
(q;q)_{m+n} 

(q;q)_{m} (q;q)_{n} 

.
(3) 
2 Some facts about qhypergeometric WZ theory
Definition 1
A sequence (t_{k}) is hypergeometric if the
ratio of two consecutive terms is a rational function of the summation
index k : t_{k+1}/t_{k}=P(k)/Q(k), where P and Q are
polynomials in k .
Definition 2
A sequence (t_{k}) is qhypergeometric if the
ratio of two consecutive terms is a rational function of q^{k} :
t_{k+1}/t_{k} = P(q^{k})/Q(q^{k}),
where P and Q are polynomials in q^{k} . (Note that q should be
contained in the coefficient field which should be of characteristic 0.)
2.1 From Gosper to Zeilberger
Gosper's algorithm for indefinite hypergeometric
summation [3] is
given as input a hypergeometric sequence (f_{k}) . This algorithm finds
a hypergeometric sequence (g_{k}) such that f_{k} = g_{k+1}  g_{k}
(then g_{k} is the product of f_{k} and a rational function in k).
From there by telescoping one gets:
Zeilberger's algorithm computes definite hypergeometric sums.
Given a proper hypergeometric sequence (F_{n,k})
(with finite support in k), this algorithm finds a hypergeometric
sequence (S_{k}) such that
The idea is to use an extension of Gosper's algorithm in order to find
polynomials a_{j}(n) and a proper hypergeometric term (G_{n,k})
such that


a_{j}(n) F_{n+j,k} = G_{n,k+1}  G_{n,k}. 
Then G_{n,k} is necessarily of the form R(n,k) F_{n,k} where R is a rational function called the ``certificate''.
Summing this equality yields the desired recurrence on S_{n}:
This algorithm has been implemented in Mathematica by P. Paule and M. Schorn:
Example 1
In[1]:= <<zb_alg.m
Fast Zeilberger by Peter Paule and Markus Schorn. (V 2.2)
Systembreaker = ENullspace
In[2]:= Zb[Binomial[n,k] x^k, k, n, 1]
Out[2]= {(1 + x) F[k, n]  F[k, 1 + n] == Delta[k, R F[k, n]]}
In[3]:= Show[R]
k
Out[3]= 
1  k + n
Both these algorithms extend to the qcase, a corresponding
implementation in Mathematica is due to A. Riese.
2.2 Example
A variation of a qanalogue of Gosper's and Zeilberger's algorithms can serve
in finding qanalogues of binomial identities. For instance, in order to
derive a qanalogue of the binomial theorem, the question is to find
a, b Î Z such that the following sequence
satisfies a recurrence of order one:
Riese's Mathematica package qZeil
automatically determines the
candidates a Î {1}, b Î Z.
Indeed, choosing a = 1 and b = 0 :
In[3]:= <<qZeil.m
Out[3]= Axel Riese's qZeilberger implementation version 1.8 loaded
In[4]:= qZeil[ qBinomial[n,k,q] x^k q^Binomial[k,2], {k,0,n}, n, 1]
1 + n
Out[4]= SUM[n] == ((1  q x) SUM[1 + n])
So, we obtain the qbinomial theorem in one of its standard forms:



x^{k}
q 

= (1+x) (1+qx) ··· (1+q^{n1}x). 
2.3 WZ duality
Given a hypergeometric sequence (f_{n,k}) ,
assume that Zeilberger's algorithm finds a_{1}, a_{2} and g_{n,k}
such that:
a_{1}(n) f_{n+1,k} + a_{2}(n) f_{n,k} = g_{n,k+1}  g_{n,k}.
Then, in case of finite support:
a_{1}(n) S_{n+1} + a_{2}(n) S_{n} = 0.
By using this in the form
a_{2}(n)/S_{n+1} =  a_{1}(n)/S_{n} , we
rewrite the relation above as:



+ 



= 
g_{n,k+1}  g_{n,k} 

S_{n+1}S_{n} 

. 
Defining F_{n,k} = f_{n,k}/S_{n} ,
and G_{n,k} = g_{n,k}/(a_{1}(n)S_{n+1}) , we arrive at:
F_{n+1,k} 
F_{n,k} =
G_{n,k+1} 
G_{n,k}.
(4)
This gives rise to the following definition:
Definition 3
A pair of sequences (F,G) that satisfy (4) is
called a ``WZ pair''.
Note that given such a WZpair (F having finite support),
from (4) follows that
å_{k} F_{n+1,k}  å_{k} F_{n,k} = 0 ,
which means that the corresponding sum sequence S_{n} := å_{k} F(n,k)
is a constant.
3 A Fibonacci qanalogue
The wellknown Fibonacci numbers are defined by F_{0} = 1, F_{1} = 1
and F_{n+2} = F_{n+1} + F_{n} . Does there exist a qanalogue of these
numbers?
In order to follow the strategy explained above (example 2.2),
we take as a starting point the following wellknown hypergeometric sum:
For the (a, b)Ansatz, we take:
and we want to determine a, b Î Z such that (F_{n}(q))
satisfies a linear recurrence of order 2. Riese's implementation delivers as
candidates: a Î {1,2,3} and b Î Z , but only the
choice a = 2 is successful. This means, only for a = 2 ,
the qanalogue of Zeilberger's algorithm delivers (" b
Î Z ) a recurrence of order 2, namely:

F_{n+2}(q) = F_{n+1}(q) + q 

F_{n}(q).
(5) 
Let us fix (for instance) b = 1 , and we obtain for this choice:
In the limit n ® ¥ :

F 

(q) = 


= 1 + 

b_{n} q^{n}
= 


1 

(1q^{5n+1})(1q^{5n+4}) 

,
(6) 
where b_{n} is the number of partitions of n into parts with minimal
difference two and the righthand side is one of the celebrated
RogersRamanujan identities [1].
Starting from (5), it is also possible to
conjecture and then prove (by qZeilberger) the following identity
due to I. Schur
4 The Bailey chain approach
Proposition 1






(q;q)_{nk} (q;q)_{n+k} 

(q;q)_{jk} (q;q)_{j+k} 

= 1.
(7) 
Proof. Denote by f_{n,j} the summand. Riese's
implementation yields:
f_{n,j}  f_{n1,j} = g_{n,j}  g_{n,j1},
where g_{n,j}
= 
q^{k+n} (q^{j}  q^{n}) 

(q^{n}  q^{k})(1q^{k+n}) 

f_{n,j}. 
This (q)WZpair implies that the sum over f_{n,j} is constant.
That this constant is 1 follows from instance from the evaluation
for n=k [1, 4].
This identity is a special case of a qhypergeometric formula
that can be proved combinatorially as explained in [4].
Multiplying (7) by an
arbitrary sequence (c_{k}), we obtain the following special case of
``Bailey's Lemma'':




c_{k} 

(q;q)_{nk} (q;q)_{n+k} 

= 







.
(8) 
Definition 4 Two sequences ((a)_{k Î }_{Z}, (b)_{n Î }_{N})
are called a Baileypair
when
b_{n} = 


a_{k} 

(q;q)_{nk} (q;q)_{n+k} 

. 
Now, let's walk in a ``Baileychain'' (using proposition 1)
starting with:
a_{k} = q^{(}^{)} (1)^{k}
and b_{n} as above. Using qZeil
, we get:
b_{n} = 



= 
(x;q)_{n} (q/x;q)_{n} 

(q;q)_{2n} 

. 
Note that in the limit n ® ¥ , this turns into
Jacobi's triple product identity:



= 

(1q^{j}) (1+q^{j1}x) (1+ 

). 

From there (6) follows when substituting q by q^{5} and x by q^{2}.
Now, with c_{k}=q^{k}^{2}a_{k} and x=1, (8) yields an
identity due to Rogers:
which can be found by the qZeilberger algorithm after ``creative
symmetrizing'' (i.e., multiplying the summand by 1+q^{k} in this example).
The second step in the Bailey chain approach
uses c_{k}=q^{2k}^{2}a_{k}. This gives:
In the limit n ® ¥ and by Jacobi's triple product
identity, this gives again (6).
The third step of the Bailey chain gives:
resulting when n®¥ in an identity due to B. Gordon




(1q^{7n+3}) (1q^{7n+4}) (1q^{7n+7})
= 



,

whose first automatic proof was given by Chyzak [2].
References
 [1]

Andrews (George E.). 
qseries: their development and application in analysis,
number theory, combinatorics, physics, and computer algebra. 
Published for the Conference Board of the Mathematical Sciences,
Washington, D.C., 1986, CBMS Regional Conference Series
in Mathematics, vol. 66, xii+130p.
 [2]

Chyzak (Frédéric). 
Groebner bases, symbolic summation and symbolic integration. In
Buchberger (B.) and Winkler (F.) (editors), Groebner Bases and
Applications. 
Cambridge University Press, 1998. Proceedings of the
Conference 33 Years of Gröbner Bases.
 [3]

Gosper (R. William). 
Decision procedure for indefinite hypergeometric summation. Proceedings of the National Academy of Sciences USA, vol. 75, n°1,
January 1978, pp. 4042.
 [4]

Paule (Peter). 
Über das Involutionsprinzip von Garsia und Milne. Bayreuther Mathematische Schriften, n°21, 1986,
pp. 295319. 
Diskrete Strukturen, algebraische Methoden und Anwendungen (Bayreuth,
1985).
 [5]

Paule (Peter) and Riese (Axel). 
A Mathematica qanalogue of Zeilberger's algorithm based on an
algebraically motivated approach to qhypergeometric telescoping. In Special functions, qseries and related topics, pp. 179210. 
American Mathematical Society, Providence, RI, 1997.
Proceedings of a workshop held in Toronto, ON, June 1995.
 [6]

Paule (Peter) and Schorn (Markus). 
A Mathematica version of Zeilberger's algorithm for proving
binomial coefficient identities. Journal of Symbolic Computation,
vol. 20, 1995, pp. 673698.
 [7]

Petkovsek (Marko), Wilf (Herbert), and Zeilberger (Doron). 
A=B. 
A. K. Peters, Wellesley, MA, 1996, xii+212p.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.