SOME APPLICATIONS OF THE q–RICE FORMULA

HELMUT PRODINGER

Abstract. We evaluate alternating sums involving q–binomial coefficients using a contour integration technique. In this way we rederive very easily some results due to Van Hamme, Uchimura (simplified!), Dilcher, Andrews, Crippa, and Simon.

Dedicated to my friend Wojtek Szpankowski on the occasion of his 50th birthday

1. Introduction

Rice’s method has been a tremendous success in Computer Science, see [5] and [10]; the latter book devotes a whole chapter to it. It is based on the integral representation

∑_{k=1}^{n} \binom{n}{k}(−1)^{k}f(k) = \frac{(−1)^{n}}{2πi} ∫_{C} \frac{n!}{z(z − 1) … (z − n)}f(z) dz,

where C (positively oriented) encloses the poles 1, 2, …, n and no others. Extending the curve of integration and taking the extra negative residues into account, we get identities, provided the integrals goes to zero, which it does for a large class of functions f(z). The proof is by Cauchy’s integral formula, and the survey [5] contains all the technicalities and many examples.

One simple example is

\begin{aligned}∑_{k=1}^{n} \binom{n}{k}(−1)^{k−1} \frac{1}{k} & = \frac{(−1)^{n−1}}{2πi} ∫_{C} \frac{n!}{z^{2}(z − 1) … (z − n)} dz \\ & = (−1)^{n} Res_{z=0} \frac{n!}{z^{2}(z − 1) … (z − n)} \\ & = (−1)^{n}[z^{1}]\frac{n!}{(z − 1) … (z − n)} \\ & = [z^{1}]\frac{1}{(1 − z)(1 − \frac{z}{2}) … (1 − \frac{z}{n})} \\ & = [z^{1}](1 + z)(1 + \frac{z}{2}) … (1 + \frac{z}{n}) = H_{n}. \end{aligned}  (1)

Here we want to consider a q–version of this formula and show how useful it is. Assume that q is a parameter with |q| < 1, then we define the q–binomial coefficients (Gaussian

Date: July 30, 2001.

2 HELMUT PRODINGER

polynomials) as usually by

\left[{n \atop k}\right]_{q} := \frac{(q; q)_{n}}{(q; q)_{k}(q; q)_{n−k}} ,

with (z; q)_{n} := (1 − z)(1 − zq) … (1 − zq^{n−1}), see e. g. [1]. The formula is now this:

∑_{k=1}^{n}(−1)^{k−1}q^{\binom{k}{2}}\left[{n \atop k}\right]_{q}f(q^{−k}) = \frac{1}{2πi} ∫_{C} \frac{(q; q)_{n}}{(z; q)_{n+1}} f(z) dz,  (2)

where C encircles the poles q^{−1}, …, q^{−n} and no others. This follows immediately from

Res_{z=q^{−k}} \frac{(q; q)_{n}}{(z; q)_{n+1}} = (−1)^{k−1}q^{\binom{k}{2}}\left[{n \atop k}\right]_{q}.

(P. Borwein used a similar formula in [3].) In this paper we are only interested in deriving identities, leaving applications to asymptotic expansions to future research. For that we use

∑_{k=1}^{n}(−1)^{k−1}q^{\binom{k}{2}}\left[{n \atop k}\right]_{q}f(q^{−k}) = (−1)^{n+1} Res_{z} \{f(z)\frac{(q; q)_{n}}{(z; q)_{n+1}} \} ,

where the sum is extended to all poles z of f(z)(q; q)_{n}/(z; q)_{n+1} not in {q^{−1}, …, q^{−n}} and the function f(z) is a rational function. This formula, being exact, is the basis of the identities discussed in the present paper. The proof is verbatim as in [5]: A rational function is of polynomial growth, i. e. f(z) = O(|z|^{s}) for some s. If n > s + 1, then the integral in (2), taken over a circle of radius R (avoiding poles of the integrand), tends to zero for R → ∞. All our applications (next section) are of that type. The gentle reader is invited to provide more examples, also for larger classes of functions than just rational functions.

2. Applications

The first one it the formula of Van Hamme [6], see also [2]:

S := ∑_{k=1}^{n} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{1 − q^{k}} \left[{n \atop k}\right]_{q} = ∑_{k=1}^{n} \frac{q^{k}}{1 − q^{k}} .

For that one, f(z) = \frac{1}{z−1}, and we must now do this computation:

S = − Res_{z=1} \frac{(q; q)_{n}}{(z; q)_{n+1}} \frac{1}{z − 1}

= [(z − 1)^{1}]\frac{(q; q)_{n}}{(1 − zq) … (1 − zq^{n})}

= [w^{1}]\frac{(q; q)_{n}}{(1 − q − wq) … (1 − q^{n} − wq^{n})}

= [w^{1}]\frac{1}{(1 − \frac{wq}{1−q}) … (1 − \frac{wq^{n}}{1−q^{n}})}

= \frac{q}{1 − q} + ⋯ + \frac{q^{n}}{1 − q^{n}} .

The limit (after multiplication by 1 − q) for q → 1 is just (1).

The next one is Uchimura’s [9] generalization for m ∈ ℕ (actually it works for all real m different from 0, −1, …, −n):

S := ∑_{k=1}^{n} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{1 − q^{k+m}} \left[{n \atop k}\right]_{q} = ∑_{k=1}^{n} \frac{q^{k}}{1 − q^{k}} /\left[{k + m \atop k}\right]_{q}.

Here, f(z) = \frac{1}{z−q^{m}}, and

S = − Res_{z=1} \frac{(q; q)_{n}}{(z; q)_{n+1}} \frac{1}{z − q^{m}} − Res_{z=q^{m}} \frac{(q; q)_{n}}{(z; q)_{n+1}} \frac{1}{z − q^{m}}

= \frac{1}{1 − q^{m}} − \frac{(q; q)_{n}(q; q)_{m−1}}{(q; q)_{m+n}} ,

which is better (closed form!) than Uchimura’s formula. To prove the equivalence we use induction on n. For n = 0, everything evaluates to zero, and the inductive step goes like this:

∑_{k=1}^{n+1} \frac{q^{k}}{1 − q^{k}} /\left[{k + m \atop k}\right]_{q} = \frac{1}{1 − q^{m}} − \frac{(q; q)_{n}(q; q)_{m−1}}{(q; q)_{m+n}} + \frac{q^{n+1}}{1 − q^{n+1}} /\left[{n + 1 + m \atop n + 1}\right]_{q}

= \frac{1}{1 − q^{m}} − \frac{(q; q)_{n}(q; q)_{m−1}}{(q; q)_{m+n}} + \frac{q^{n+1}(q; q)_{n}(q; q)_{m}}{(q; q)_{n+1+m}}

= \frac{1}{1 − q^{m}} − \frac{(q; q)_{n}(q; q)_{m−1}}{(q; q)_{m+n+1}} [1 − q^{n+1+m} − q^{n+1}(1 − q^{m})]

= \frac{1}{1 − q^{m}} − \frac{(q; q)_{n+1}(q; q)_{m−1}}{(q; q)_{m+n+1}} ,

as desired.

The limit of this formula for q → 1 is

∑_{k=1}^{n} \frac{(−1)^{k−1}}{k + m} \binom{n}{k} = \frac{1}{m} − \frac{n!(m − 1)!}{(m + n)!}.

Since the case m = 0 is well understood, let us now consider the case m = −M, M ∈ {1, …, n}:

4 HELMUT PRODINGER

We consider the sum

S := ∑_{{k=1 \atop k≠M}}^{n} \left[{n \atop k}\right]_{q} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{1 − q^{k−M}} .

The negative residue at z = 1 is \frac{1}{1−q^{m}} as before; now we compute the negative residue at z = q^{−M}:

− Res_{z=q^{−M}} \frac{(q; q)_{n}}{(z; q)_{n+1}} \frac{1}{z − q^{−M}}

= q^{−M}[(z − q^{−M})^{1}]\frac{(q; q)_{n}}{(1 − z) … (1 − zq^{M−1})(1 − zq^{M+1}) … (1 − zq^{n})}

= q^{−M}(q; q)_{n}[w^{1}]\frac{1}{(1 − q^{−M}) … (1 − q^{−1})(1 − \frac{w}{1−q^{−M}} ) … (1 − \frac{wq^{M−1}}{1−q^{−1}} )}

× \frac{1}{(1 − q) … (1 − q^{n−M})(1 − \frac{wq^{M+1}}{1−q} ) … (1 − \frac{wq^{n}}{1−q^{n−M}} )}

= q^{−M} \frac{(q; q)_{n}}{(q^{−M}; q)_{M}(q; q)_{n−M}} [\frac{1}{1 − q^{−M}} + ⋯ + \frac{q^{M−1}}{1 − q^{−1}} + \frac{q^{M+1}}{1 − q} + ⋯ + \frac{q^{n}}{1 − q^{n−M}} ].

Consequently, the sum is evaluated:

S = \frac{1}{1 − q^{−M}} + (−1)^{M}q^{\binom{M+1}{2}}\left[{n \atop M}\right]_{q} ∑_{{i=0 \atop i≠M}}^{n} \frac{q^{i−M}}{1 − q^{i−M}};

it looks nicer in this form:

∑_{{k=0 \atop k≠M}}^{n} \left[{n \atop k}\right]_{q} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{1 − q^{k−M}} = (−1)^{M}q^{\binom{M+1}{2}}\left[{n \atop M}\right]_{q} ∑_{{i=0 \atop i≠M}}^{n} \frac{q^{i−M}}{1 − q^{i−M}} .

The limit for q → 1 is

∑_{{k=0 \atop k≠M}}^{n} \binom{n}{k}\frac{(−1)^{k−1}}{k − M} = (−1)^{M} \binom{n}{M}(H_{n−M} − H_{M}).

Higher powers of (1 − q^{k+m}), like

∑_{k=1}^{n} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{(1 − q^{k+m})^{d}} \left[{n \atop k}\right]_{q}

can also be handled (compare [5] and [7] for the classical case); it involves Bell polynomials and is quite messy but not difficult. The next one is Dilcher’s sum [4]:

∑_{1≤k≤n} \left[{n \atop k}\right]_{q}(−1)^{k−1} \frac{q^{\binom{k}{2}+mk}}{(1 − q^{k})^{m}} = ∑_{1≤i_{1}≤i_{2}≤···≤i_{m}≤n} \frac{q^{i_{1}}}{1 − q^{i_{1}}} … \frac{q^{i_{m}}}{1 − q^{i_{m}}} .

This time,

f(z) = \frac{1}{(z − 1)^{m}} ,

and we must compute

− [(z − 1)^{−1}]\frac{1}{(z − 1)^{m}} \frac{(1 − q) … (1 − q^{n})}{(1 − z)(1 − zq) … (1 − zq^{n})}

= [(z − 1)^{m}]\frac{(1 − q) … (1 − q^{n})}{(1 − zq) … (1 − zq^{n})}

= [w^{m}]\frac{1}{(1 − \frac{wq}{1−q}) … (1 − \frac{wq^{n}}{1−q^{n}})}

= ∑_{1≤i_{1}≤i_{2}≤···≤i_{m}≤n} \frac{q^{i_{1}}}{1 − q^{i_{1}}} … \frac{q^{i_{m}}}{1 − q^{i_{m}}} .

As Dilcher noted, the limit for q → 1 is

∑_{1≤k≤n} \binom{n}{k}(−1)^{k−1} \frac{1}{k^{m}} = ∑_{1≤i_{1}≤i_{2}≤···≤i_{m}≤n} \frac{1}{i_{1} … i_{m}} .

(Dilcher’s formula can be inverted, which is then a q–version of a formula of Hernández, see [8].)

In [2] (Theorem 2.1) the authors are concerned with the sum

S(m) := ∑_{k≥1} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{(q; q)_{k}(1 − q^{k})^{m}} ,

as they want to reduce it to certain simpler functions.

We introduce the finite forms

S_{n}(m) := ∑_{k=1}^{n} \frac{(−1)^{k−1}q^{\binom{k+1}{2}}}{(1 − q^{k})^{m}} \left[{n \atop k}\right]_{q},

so that lim_{n→∞} S_{n}(m) = S(m), and apply the now familiar technique. Observe the similarity to Dilcher’s sum! We have

f(z) = \frac{z^{m−1}}{(z − 1)^{m}} ,

and compute

S_{n}(m) = −[(z − 1)^{−1}]\frac{z^{m−1}}{(z − 1)^{m}} \frac{(1 − q) … (1 − q^{n})}{(1 − z)(1 − zq) … (1 − zq^{n})}

= [(z − 1)^{m}]z^{m−1} \frac{(1 − q) … (1 − q^{n})}{(1 − zq) … (1 − zq^{n})}

= [w^{m}](1 + w)^{m−1} \frac{1}{(1 − \frac{wq}{1−q}) … (1 − \frac{wq^{n}}{1−q^{n}})}

= ∑_{h=0}^{m−1} \binom{m − 1}{h}[w^{h+1}]\frac{1}{(1 − \frac{wq}{1−q}) … (1 − \frac{wq^{n}}{1−q^{n}})}

= ∑_{h=0}^{m−1} \binom{m − 1}{h} ∑_{1≤i_{1}≤i_{2}≤···≤i_{h+1}≤n} \frac{q^{i_{1}}}{1 − q^{i_{1}}} … \frac{q^{i_{h+1}}}{1 − q^{i_{h+1}}} .

Everything is now fully explicit.

References

[1] G. Andrews. The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications. Addison–Wesley, 1976.

[2] G. Andrews, D. Crippa, and K. Simon. q–series arising from the study of random graphs. SIAM Journal on Discrete Mathematics, 10:41–56, 1997.

[3] P. Borwein. Padé approximations for the q–elementary functions. Constructive Approximation, 4:391–402, 1988.

[4] K. Dilcher. Some q–series identities related to divisor functions. Discrete Mathematics, 145:83–93, 1995.

[5] P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: Finite differences and Rice’s integrals. Theoretical Computer Science, 144:101–124, 1995.

[6] L. Van Hamme. Advanced problem 6407. American Mathematical Monthly, 40:703–704, 1982.

[7] P. Kirschenhofer. A note on alternating sums. Electronic Journal of Combinatorics, 3(2):R7, 10 pages, 1996.

[8] H. Prodinger. A q–analogue of a formula of Hernández obtained by inverting a result of Dilcher. Australasian Journal of Combinatorics, 21:271–274, 2000.

[9] K. Uchimura. A generalization of identities for the divisor generating function. Utilitas Mathematica, 25:377–379, 1984.

[10] W. Szpankowski. Average Case Analysis of Algorithms on Sequences. John Wiley, 2001.

Helmut Prodinger The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics University of the Witwatersrand, P. O. Wits 2050 Johannesburg, South Africa

email: helmut@gauss.cam.wits.ac.za,
homepage: http://www.wits.ac.za/helmut/index.htm