q-WZ-Theory 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 q-hypergeometric sums, for instance, the celebrated Rogers-Ramanujan 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 q-WZ-theory. For instance, as a by-product of computer proofs, one automatically obtains the so-called ``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 q-hypergeometric 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 Gm,n(q) = åk=0mn p(m,n;k) qk is a polynomial in q of degree m n .

A few particular instances are:
Gm,0(q)
= 1,     G0,n(q) = 1,     Gm,n(q) = Gn,m(q),     Gm,1(q) =
1-qm+1
1-q
,
G4,3(q) = 1 + q + 2q2 + 3q3 + 4q4 + 4q5 + 5q6 + 4q7 + 4q8 + 3q9 + 2q10 + q11 + q12.
From the decomposition
p(m,n;k) = p(m-1,n;k-n)+ p(m,n-1;k)      (k³ n)
follows that
Gm,n(q) = qn Gm-1,n(q) + Gm,n-1(q).     (1)
By symmetry, we also have:
Gm,n(q) = Gm-1,n(q) + qm Gm,n-1(q).     (2)
So, by elimination between (1) and (2):
Gm,n(q) =
1-qm+n
1-qn
Gm,m-1(q) =
(1-qm+n) ··· (1-qm+1)
(1-qn) ··· (1-q)
Gm,0(q).

Using the standard notation (a;q)k=(1-a)(1-aq)···(1-aqk-1), k = 1,2,... and (a;q)k=1/(a;q)-k for k<0, we get a closed form representation of the Gaussian polynomials Gm,n :
é
ë
m+n
n
ù
û
:= Gm,n(q) =
(1-qm+n) ··· (1-qm+1)
(1-qn) ··· (1-q)
=
(q;q)m+n
(q;q)m (q;q)n
.     (3)

2   Some facts about q-hypergeometric WZ theory

Definition 1   A sequence (tk) is hypergeometric if the ratio of two consecutive terms is a rational function of the summation index k : tk+1/tk=P(k)/Q(k), where P and Q are polynomials in k .

Definition 2   A sequence (tk) is q-hypergeometric if the ratio of two consecutive terms is a rational function of qk : tk+1/tk = P(qk)/Q(qk), where P and Q are polynomials in qk . (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 (fk) . This algorithm finds a hypergeometric sequence (gk) such that fk = gk+1 - gk (then gk is the product of fk and a rational function in k). From there by telescoping one gets:
n
å
k=0
fk = gn+1 - g0.

Zeilberger's algorithm computes definite hypergeometric sums. Given a proper hypergeometric sequence (Fn,k) (with finite support in k), this algorithm finds a hypergeometric sequence (Sk) such that
 
å
k
Fn,k = Sn.
The idea is to use an extension of Gosper's algorithm in order to find polynomials aj(n) and a proper hypergeometric term (Gn,k) such that
J
å
j=0
aj(n) Fn+j,k = Gn,k+1 - Gn,k.
Then Gn,k is necessarily of the form R(n,k) Fn,k where R is a rational function called the ``certificate''. Summing this equality yields the desired recurrence on Sn:
J
å
j=0
aj(n) Sn+j = 0.
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 q-case, a corresponding implementation in Mathematica is due to A. Riese.

2.2   Example

A variation of a q-analogue of Gosper's and Zeilberger's algorithms can serve in finding q-analogues of binomial identities. For instance, in order to derive a q-analogue of the binomial theorem, the question is to find a, b Î Z such that the following sequence satisfies a recurrence of order one:
Sn(q) =
n
å
k=0
é
ë
n
k
ù
û
xk q
a
æ
è
k
2
ö
ø
+ b k
 
,
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 q-Zeilberger 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 q-binomial theorem in one of its standard forms:
n
å
k=0
é
ë
n
k
ù
û
xk q
æ
è
k
2
ö
ø
 
= (1+x) (1+qx) ··· (1+qn-1x).

2.3   WZ duality

Given a hypergeometric sequence (fn,k) , assume that Zeilberger's algorithm finds a1, a2 and gn,k such that:
a1(n) fn+1,k + a2(n) fn,k = gn,k+1 - gn,k.
Then, in case of finite support:
a1(n) Sn+1 + a2(n) Sn = 0.
By using this in the form a2(n)/Sn+1 = - a1(n)/Sn , we rewrite the relation above as:
a1(n)
Sn
fn+1,k
Sn+1
+
a2(n)
Sn+1
fn,k
Sn
=
gn,k+1 - gn,k
Sn+1Sn
.
Defining Fn,k = fn,k/Sn , and Gn,k = gn,k/(a1(n)Sn+1) , we arrive at:
Fn+1,k - Fn,k = Gn,k+1 - Gn,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 WZ-pair (F having finite support), from (4) follows that åk Fn+1,k - åk Fn,k = 0 , which means that the corresponding sum sequence Sn := åk F(n,k) is a constant.

3   A Fibonacci q-analogue

The well-known Fibonacci numbers are defined by F0 = 1, F1 = 1 and Fn+2 = Fn+1 + Fn . Does there exist a q-analogue of these numbers? In order to follow the strategy explained above (example 2.2), we take as a starting point the following well-known hypergeometric sum:
Fn =
n
å
k=0
æ
è
n-k
k
ö
ø
.
For the (a, b)-Ansatz, we take:
Fn(q) =
n
å
k=0
é
ë
n-k
k
ù
û
q
a
æ
è
k
2
ö
ø
+ b k
 
,
and we want to determine a, b Î Z such that (Fn(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 q-analogue of Zeilberger's algorithm delivers (" b Î Z ) a recurrence of order 2, namely:
Fn+2(q) = Fn+1(q) + q
n+b
 
Fn(q).     (5)
Let us fix (for instance) b = 1 , and we obtain for this choice:
Fn(q) =
n
å
k=0
é
ë
n-k
k
ù
û
q
k2
 
.
In the limit n ® ¥ :
F
 
¥
(q) =
¥
å
k=0
q
k2
 
(q;q)k
= 1 +
¥
å
n=1
bn qn =
¥
Õ
k=1
1
(1-q5n+1)(1-q5n+4)
,     (6)
where bn is the number of partitions of n into parts with minimal difference two and the right-hand side is one of the celebrated Rogers-Ramanujan identities [1].

Starting from (5), it is also possible to conjecture and then prove (by q-Zeilberger) the following identity due to I. Schur
F2n(q)=
 
å
k
qk(10k+1)
é
ë
2n
n-5k
ù
û
-
 
å
k
q(2k-1)(5k-2)
é
ë
2n
n-5k+2
ù
û
.

4   The Bailey chain approach

Proposition 1  
n
å
j=0
q
j2-k2
 
(q;q)n-j
(q;q)n-k (q;q)n+k
(q;q)j-k (q;q)j+k
= 1.     (7)

Proof. Denote by fn,j the summand. Riese's implementation yields:
fn,j - fn-1,j = gn,j - gn,j-1,     where     gn,j =
qk+n (qj - qn)
(qn - qk)(1-qk+n)
fn,j.
This (q)WZ-pair implies that the sum over fn,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 q-hypergeometric formula that can be proved combinatorially as explained in [4].

Multiplying (7) by an arbitrary sequence (ck), we obtain the following special case of ``Bailey's Lemma'':
 
å
k
ck
(q;q)n-k (q;q)n+k
=
 
å
j ³ 0
q
j2
 
(q;q)n-j
 
å
k
ck q
-k2
 
(q;q)j-k (q;q)j+k
.     (8)

Definition 4   Two sequences ((a)k Î Z, (b)n Î N) are called a Bailey-pair when
bn =
 
å
k
ak
(q;q)n-k (q;q)n+k
.
Now, let's walk in a ``Bailey-chain'' (using proposition 1) starting with: ak = q(
k
2
) (-1)k and bn as above. Using qZeil, we get:
bn =
 
å
k
q
æ
è
k
2
ö
ø
 
xk
(q;q)n-k (q;q)n+k
=
(-x;q)n (-q/x;q)n
(q;q)2n
.
Note that in the limit n ® ¥ , this turns into Jacobi's triple product identity:
 
å
k
q
æ
è
k
2
ö
ø
 
xk
=
¥
Õ
j=1
(1-qj) (1+qj-1x) (1+
qj
x
).
From there (6) follows when substituting q by q5 and x by -q2.

Now, with ck=qk2ak and x=-1, (8) yields an identity due to Rogers:
 
å
k
(-1)k q
3
2
k2 -
1
2
k
 
(q;q)n-k (q;q)n+k
=
1
(q;q)n
,
which can be found by the q-Zeilberger algorithm after ``creative symmetrizing'' (i.e., multiplying the summand by 1+qk in this example).

The second step in the Bailey chain approach uses ck=q2k2ak. This gives:
 
å
k
(-1)k q
5
2
k2 -
1
2
k
 
(q;q)n-k (q;q)n+k
=
 
å
j ³ 0
q
j2
 
(q;q)n-j(q;q)j
.
In the limit n ® ¥ and by Jacobi's triple product identity, this gives again (6). The third step of the Bailey chain gives:
 
å
k
(-1)k q
7
2
k2 -
1
2
k
 
(q;q)n-k (q;q)n+k
=
 
å
j ³ 0
q
j2
 
(q;q)n-j
j
å
l=0
q
l2
 
(q;q)j-l (q;q)l
,
resulting when n®¥ in an identity due to B. Gordon
1
(q;q)
 
¥
¥
Õ
n=0
(1-q7n+3) (1-q7n+4) (1-q7n+7) =
¥
å
l,j=0
q
(j+l)2 +l2
 
(q;q)j (q;q)l
,
whose first automatic proof was given by Chyzak [2].



References

[1]
Andrews (George E.). -- q-series: 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. 40--42.

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

[5]
Paule (Peter) and Riese (Axel). -- A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated approach to q-hypergeometric telescoping. In Special functions, q-series and related topics, pp. 179--210. -- 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. 673--698.

[7]
Petkovsek (Marko), Wilf (Herbert), and Zeilberger (Doron). -- A=B. -- A. K. Peters, Wellesley, MA, 1996, xii+212p.

This document was translated from LATEX by HEVEA.