J. Symbolic Computation (1995) 11, 1–000

HYP and HYPQ

Mathematica packages for the manipulation of binomial sums and hypergeometric series, respectively q-binomial sums and basic hypergeometric series

C. Krattenthaler

Institut für Mathematik der Universität Wien,

Strudlhofgasse 4, A-1090 Wien, Austria

e-mail: KRATTPap.Univie.Ac.At

(Received 7 June 1995)

We give a brief description of the main features of the Mathematica packages HYP and HYPQ. HYP allows a convenient handling of binomial sums and hypergeometric series, while its “q-analogue”, the package HYPQ, allows a convenient handling of q-binomial sums and basic hypergeometric series. Both packages are available by anonymous ftp at

       pap.univie.ac.at.

1. Introduction

Binomial series and q-binomial series, such as

∑_{k=0}^{∞} \binom{M}{k}\binom{N}{R − k}, respectively ∑_{k=0}^{∞} q^{(M−k)(R−k)} [ \begin{matrix}M \\ k \end{matrix} ]_{q} [ \begin{matrix}N \\ R − k \end{matrix} ]_{q} ,

where the q-binomial coefficient is defined by

[ \begin{matrix}n \\ k \end{matrix} ]_{q} = \frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q^{n−k+1})}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)},

and hypergeometric series, defined by

rF_{s}[ \begin{matrix}a_{1},…, a_{r} \\ b_{1},…, b_{s} \end{matrix} ; z] = ∑_{n=0}^{∞} \frac{(a_{1})_{n} ⋯ (a_{r})_{n}}{n! (b_{1})_{n} ⋯ (b_{s})_{n}} z^{n}

with (a)_{n} := a(a + 1) ⋯ (a + n − 1), and basic hypergeometric series, defined by

rϕ_{s}[ \begin{matrix}a_{1},…, a_{r} \\ b_{1},…, b_{s} \end{matrix} ; q, z] = ∑_{n=0}^{∞} \frac{(a_{1}; q)_{n} ⋯ (a_{r}; q)_{n}}{(q; q)_{n}(b_{1}; q)_{n} ⋯ (b_{s}; q)_{n}} ((−1)^{n}q^{\binom{n}{2}})^{s−r+1} z^{n}

with (a; q)_{n} := (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}) frequently occur in several branches of mathematics, in particular in combinatorics and special functions theory. In fact, as was emphasized by Andrews (1974) (but is still not as accepted as it should be), “almost all” binomial sums admit a normal form. Namely, a binomial sum can (almost always) be

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1995 Academic Press Limited

converted into a hypergeometric series. This hypergeometric series is unique and therefore is the normal form of the binomial sum. The same is true for q-binomial series and basic hypergeometric series. And even better, there are not too many basic identities for hypergeometric, respectively basic hypergeometric series (most of them being known for more than 50 years) from which “everything else” can be derived. So these basic identities are sufficient to work with. However, there is a drawback, too. The conversion of a (q-)binomial sum into its (basic) hypergeometric form, and working with (basic) hypergeometric series amounts to working with cumbersome expressions which involve a lot of parameters. The Mathematica packages HYP and HYPQ were designed to remedy this, and thus take away the horror from (basic) hypergeometric series that (among non-experts) is commonly associated with them. The package HYP provides tools for conveniently manipulating binomial and hypergeometric expressions, while its “q-analogue”, the package HYPQ, provides tools for conveniently manipulating q-binomial and basic hypergeometric expressions. In the next section we describe the main features of these packages. Finally, in section 3 we display two short examples of computations done by the package HYP so that one gets an impression how the packages actually work.

From the examples it can be seen that the philosophy behind both packages is:

Do it by yourself!

The idea is that every step in a series of manipulations should be controlled by the user. Consequently, these packages do not make any attempt to sum or transform a series automatically. It is the user who has to tell the packages HYP and HYPQ which command has to be applied next. In order to help the user to decide which command could be applied next, for both packages a comprehensive manual giving a complete list of all the available objects with detailed descriptions, examples, and cross references is provided. Also, with the packages there comes a tutorial which contains numerous examples detailing many of the features of HYP and HYPQ.

Both packages are mainly rule-based (a feature which is heavily supported by Mathematica but unfortunately not by MAPLE). This gives a lot more flexibility in doing manipulations compared to sticking to functions only.

In order to use these packages you need a computer with some version of Mathematica installed. The input files for the packages and the TEX-files for the manuals and the tutorial are available by anonymous ftp at node pap.univie.ac.at. Contact the author for further information. In order to use the packages efficiently it suffices to have a basic knowledge of Mathematica. It is of great help to have an advanced knowledge of pattern matching, rules, and pure functions (cf. Wolfram (1991), sections 2.3, 2.4, 2.2.5).

Finally, for information about hypergeometric and basic hypergeometric series, we refer the reader to the standard books Bailey (1935), Gasper and Rahman (1990), Slater (1966).

For later use we introduce the short notation

Γ [ \begin{matrix}a_{1}, a_{2},…, a_{r} \\ b_{1}, b_{2},…, b_{s} \end{matrix} ] = \frac{Γ(a_{1}) Γ(a_{2}) ⋯ Γ(a_{r})}{Γ(b_{1}) Γ(b_{2}) ⋯ Γ(b_{s})},

where Γ(z) denotes the usual gamma function.

2. The main features

2.1. Converting binomial sums into hypergeometric notation and q-binomial sums into basic hypergeometric notation

Conversions like

\begin{matrix}∑_{k=0}^{∞} \binom{M}{k}\binom{N}{R − k} ⟶ \frac{(1 + N − R)_{R}}{R!}_{2}F_{1}[ \begin{matrix}−M, −R \\ 1 + N − R \end{matrix} ; 1] , \\ ∑_{k=0}^{∞} q^{(M−k)(R−k)} [ \begin{matrix}M \\ k \end{matrix} ]_{q} [ \begin{matrix}N \\ R − k \end{matrix} ]_{q} ⟶ q^{MR} \frac{(q^{1+N−R}; q)_{R}}{(q; q)_{R}}_{2}ϕ_{1}[ \begin{matrix}q^{−M}, q^{−R} \\ q^{1+N−R} \end{matrix} ; q, q] , \end{matrix}

are done by the rules SumF, respectively Sumph. See the first example.

2.2. Manipulations of hypergeometric and basic hypergeometric expressions

In order to do manipulations like (a)_{n} → (−1)^{n}(1 − a − n)_{n} the package HYP supplies 15 rules. In order to do manipulations like (a; q)_{n} → (−a)^{n}q^{\binom{n}{2}}(q^{1−n}/a; q)_{n} the package HYPQ supplies 18 rules. In particular, you can do all the manipulations which are the contents of the appendices I,II in Slater (1966) and the appendix I in Gasper and Rahman (1990). Additional tools are provided for reversing finite summations, for splitting summations, for shifting summation indices, for exchanging sums, etc.

2.3. Summations for hypergeometric and basic hypergeometric series

Summations like the Vandermonde summation (see Slater (1966), (1.7.7))

2F_{1}[ \begin{matrix}−R, −M \\ 1 + N − R \end{matrix} ; 1] ⟶ \frac{(1 + N)_{M}}{(1 + N − R)_{M}} ,

and the q-Vandermonde summation (see Gasper and Rahman (1990), (1.5.3))

2ϕ_{1}[ \begin{matrix}q^{−R}, q^{−M} \\ q^{1+N−R} \end{matrix} ; q, q] ⟶ q^{−MR} \frac{(q^{1+N}; q)_{M}}{(q^{1+N−R}; q)_{M}}

are implemented in form of rules. The package HYP contains 29, while the package HYPQ contains 37 summations. You may also ask for a list of all summation formulas which are (directly) applicable to some series. See the first example. Each implemented summation can also be displayed on the screen and, if you wish, be taken as a basis for further manipulation.

2.4. Transformations of hypergeometric and basic hypergeometric series

Transformations like (see Gasper and Rahman (1990), (3.1.1), (3.2.2))

3F_{2}[ \begin{matrix}a, b, −n \\ d, e \end{matrix} ; 1] ⟶ \frac{(e − b)_{n}}{(e)_{n}}_{3}F_{2}[ \begin{matrix}−n, b, d − a \\ d, 1 + b − e − n \end{matrix} ; 1] ,

respectively _{3}ϕ_{2}[ \begin{matrix}a, b, q^{−n} \\ d, e \end{matrix} ; q, q] ⟶ b^{n} \begin{matrix}(e/b; q) & n \\ (e; q) & n \end{matrix}_{3}ϕ_{2}[ \begin{matrix}q^{−n}, b, d/a \\ d, bq^{1−n}/e \end{matrix} ; q, \frac{aq}{e} ]

are implemented in form of rules. The package HYP contains 86, while the package HYPQ contains 106 transformations. You may also ask for a list of all transformation formulas which are (directly) applicable to a given series. See the second example. Again, each implemented transformation can also be displayed on the screen and optionally can be taken as a basis for further manipulation.

The summation and transformation formulas that are implemented cover the (almost) complete appendices III, IV of Slater (1966), appendices II, III of Gasper and Rahman (1990), and most of the identities from chapters 1–3 of Gasper and Rahman (1990). All the implemented identities are displayed in the manuals, together with respective references, thus constituting the largest currently available collection of hypergeometric, respectively basic hypergeometric identities that is located in one spot.

2.5. Contiguous relations

Each package includes about 100 contiguous relations (see Slater (1966) for definition) in form of rules.

2.6. Formal limits of hypergeometric expressions

The function Limes allows you for instance in Slater (1966), Appendix, (III.24)

3F_{2}[ \begin{matrix}a, 1 − a, c \\ d, 1 + 2c − d \end{matrix} ; 1] ⟶ 2^{1−2c}πΓ [ \begin{matrix}d, 1 + 2c − d \\ \frac{1}{2} + \frac{a}{2} + c − \frac{d}{2}, \frac{a}{2} + \frac{d}{2}, 1 − \frac{a}{2} + c − \frac{d}{2}, \frac{1}{2} − \frac{a}{2} + \frac{d}{2} \end{matrix} ]

(for the Γ-notation see the last paragraph of the introduction) to let c tend to infinity to obtain Slater (1966), Appendix, (III.7)

2F_{1}[ \begin{matrix}a, 1 − a \\ d \end{matrix} ; \frac{1}{2}] ⟶ 2^{1−d}\sqrt{π} Γ [ \begin{matrix}d \\ \frac{a}{2} + \frac{d}{2}, \frac{1}{2} − \frac{a}{2} + \frac{d}{2} \end{matrix} ] .

Similar things can be done with basic hypergeometric expressions. Here it is also possible to let the base q tend to 1, to derive from a basic hypergeometric identity a companion hypergeometric identity, of which the former is its q-analogue.

2.7. Gosper’s and Zeilberger’s algorithms

The Gosper and Zeilberger algorithms can be used within HYP, provided one gets Peter Paule and Markus Schorn’s Mathematica implementation of these algorithms. This implementation can be received via e-mail request to peter.paulerisc.uni-linz.ac.at. (See also Paule and Schorn (1995).) The Gosper algorithm (Gosper, 1978) does definite summation. The Zeilberger algorithm (Zeilberger (1990a), Zeilberger (1991)) finds a polynomial recurrence for a binomial or hypergeometric series (which necessarily exists for a sufficiently large order, see Zeilberger (1990b)). There also exist q-analogues for these algorithms. They will be accessible within HYPQ as soon as a Mathematica implementation of these q-analogues is available.

2.8. Transforming hypergeometric and basic hypergeometric Mathematica expressions into TEX-code

Of course, the packages HYP and HYPQ give full support for writing binomial, qbinomial, hypergeometric, and basic hypergeometric expressions in TEX-code. The user may choose between PlainTEX-, LaTEX-, AMS-TEX-, or AMS-LaTEX-compatibility.

3. Two examples

We give two examples for the usage of the package HYP. For those who are interested in basic hypergeometric series it should suffice to remark that everything works completely analogously in the package HYPQ.

In the first example we evaluate the Vandermonde sum. First we enter the sum,

In[1]:= Sum[Binomial[M,k]*Binomial[N,R-k],{k,0,Infinity}]

∞

             (   ) (       )
         \ ( M ) (   N   )
Out[1]= ⟩ (   ) (       )
         /   ( k ) ( R - k )
             (   ) (       )
         k=0

and convert it into hypergeometric notation.

In[2]:= %/.SumF

              -M, -R
         F            ; 1   (1 + N - R)
        2 1  1 + N - R                 R
Out[2]= --------------------------------
                      (1)
                         R

Then we ask which summations are (directly) applicable,

In[3]:= %/.SListe
Is R a nonnegative integer?
[y|n]:  y
Be sure to apply "FOrdne" before using the following information!

          S2101 (1 + N - R)     S2103 (1 + N - R)
                           R                     R
Out[3]= {{------------------}, {------------------}}
                 (1)                   (1)
                    R                     R

and apply the first of them (Slater (1966), (1.7.7)),

In[4]:= %2/.FOrdne/.S2101
Is R a nonnegative integer?
[y|n]:  y
        (1 + M + N - R)
                       R
Out[4]= ----------------
              (1)
                 R

In the second example we demonstrate the use of transformation formulas. As indicated in the introduction, the packages do not contain every hypergeometric, respectively basic hypergeometric identity whatsoever, but rather a good collection of basic identities. Hence, it may happen that some series cannot be summed directly by the implemented summation formulas, but can be summed after first having applied a transformation formula. Let us consider the following hypergeometric series.

In[1]:= F[{a,b,c+n},{c,1+a},1]

             a, b, c + n
Out[1]=  F              ; 1
        3 2   c, 1 + a

where n is a nonnegative integer. When we ask for an applicable summation formula,

In[2]:= %/.SListe
Out[2]= {}

we get an empty list as the answer. So, let us try to find applicable transformation formulas.

In[3]:= %1/.TListe
Is -c - n a nonnegative integer?
[y|n]:  n
Is -b a nonnegative integer?
[y|n]:  n
Is -a a nonnegative integer?
[y|n]:  n
Is -c - n a nonnegative integer?
[y|n]:  n
Is -b a nonnegative integer?
[y|n]:  n
Is -a a nonnegative integer?
[y|n]:  n
Is -c - n a nonnegative integer?
[y|n]:  n
Is -b a nonnegative integer?
[y|n]:  n
Is -a a nonnegative integer?
[y|n]:  n
Be sure to apply "FOrdne" before using the following information!
Out[3]= {{T3204}, {T3205}, {T3261}, {T3262}, {T3263}, {T3264}, {T3267},
⟩  {T3268}}

There are a lot of transformation formulas that can be applied. We try the first of them.

In[4]:= %1/.FOrdne/.T3204

              a, -b + c, -n           1 + a, 1 - b - n
Out[4]=  F                   ; 1 Γ
        3 2  c, 1 + a - b - n         1, 1 + a - b - n

Which summation formulas can be applied now?

In[5]:= %/.SListe
Is n a nonnegative integer?
[y|n]:  y
Be sure to apply "FOrdne" before using the following information!

                   1 + a, 1 - b - n               1 + a, 1 - b - n
Out[5]= {{S3201 Γ  }, {S3261 Γ  }}
                   1, 1 + a - b - n               1, 1 + a - b - n

Indeed, now the series can be summed! It is the Pfaff–Saalschütz summation (Slater (1966), (2.3.1.3)) and its nonterminating extension (Slater (1966), (2.4.4.4)) that can be applied. We use the former summation.

In[6]:= %4/.FOrdne/.S3201
Is n a nonnegative integer?
[y|n]:  y

           1 + a, 1 - b - n
        Γ  (b)  (-a + c)
           1, 1 + a - b - n      n         n

Out[6]= ------------------------------------
                   (-a + b)  (c)
                           n    n

References

Andrews, G.E. (1974). Applications of basic hypergeometric series. SIAM Review 16, 441–484. Bailey, W.N. (1935). Generalized hypergeometric series. Cambridge: Cambridge University Press. Gasper, G., Rahman, M. (1990). Basic hypergeometric series. Encyclopedia of Mathematics And Its

Applications 35, Cambridge: Cambridge University Press. Gosper, R.W. (1978). Decision procedure for indefinite hypergeometric summation. Proc. Nat. Acad.

Sci. USA 75, 40–42. Paule, P., Schorn, M. (1995). A Mathematica version of Zeilberger’s algorithm for proving binomial

coefficient identities. J. Symbolic Comput., same issue. Slater, L.J. (1966). Generalized hypergeometric functions. Cambridge: Cambridge University Press. Wolfram, S. (1991). Mathematica — A system for doing mathematics by computer. Second edition. New

York: Addison–Wesley. Zeilberger, D. (1990a). A fast algorithm for proving terminating hypergeometric identities. Discrete

Math. 80, 207–211. Zeilberger, D. (1990b). A holonomic systems approach to special functiions identities.J. Comput. Appl.

Math. 32, 321–368. Zeilberger, D. (1991). The method of creative telescoping. J. Symbolic Comput. 11, 195–204.