A q–ANALOGUE OF A FORMULA OF HERNANDEZ OBTAINED BY INVERTING A RESULT OF DILCHER

HELMUT PRODINGER

Abstract. We prove a q–analogue of the formula

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

by inverting a formula due to Dilcher.

1. The identities

Hernández in [5] proved the following identity:

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

However this identity does not really require a proof, since we will show that it is just an inverted form of an identity of Dilcher; [3]

∑_{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_{2} … i_{m}} .  (2)

Define for k ≥ 1

a_{k} := − ∑_{1≤i_{1}≤i_{2}≤···≤i_{m}=k} \frac{1}{i_{1}i_{2} … i_{m}}  and b_{k} := \frac{1}{k^{m}} ,

and a_{0} = b_{0} = 0, then the identities are

∑_{0≤k≤n} \binom{n}{k}(−1)^{k}a_{k} = ∑_{0≤k≤n} b_{k},

∑_{0≤k≤n} \binom{n}{k}(−1)^{k}b_{k} = ∑_{0≤k≤n} a_{k}.

They are inverse relations, as can be seen by introducing ordinary generating functions A(z) = ∑ a_{n}z^{n} and B(z) = ∑ b_{n}z^{n}. Then they are

Date: July 7, 1999.

This research was conducted while the author was a host of the projet Algo at INRIA, Rocquencourt. The funding came from the Austrian–French “Amadée” cooperation.

\frac{1}{1 − z} A(\frac{z}{z − 1}) = \frac{1}{1 − z} B(z),
\frac{1}{1 − z} B(\frac{z}{z − 1}) = \frac{1}{1 − z} A(z).

However

w = \frac{z}{z − 1} ⟷ z = \frac{w}{w − 1},

and the proof is finished We note that Dilcher’s sum appears also in disguised form in [4].

2. A q–analogue

Dilcher’s formula (2) was only a corollary of his elegant q–version;

∑_{1≤k≤n} \left[{n \atop k}\right]_{q}(−1)^{k−1} \frac{q^{\binom{k+1}{2}+(m−1)k}}{(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}}} .

Here, \left[{n \atop k}\right]_{q} denotes the Gaussian polynomial

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

with

(x; q)_{n} := (1 − x)(1 − xq) … (1 − xq^{n−1}).

Apart from Dilcher’s paper [3], the article [1] is also of some relevance in this context. Therefore it is a natural question to find a q–analogue of Hernández’ formula, or, what amount to the same, to find the appropriate inverse relations for the q–analogues. We state them in the following lemma which is almost surely not new. However, I found it more appealing to derive it myself rather than hunting for it in the vast q–literature. Lemma 1.

∑_{k=0}^{n} b_{k} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(−1)^{k}q^{\binom{k}{2}}a_{k},  (3)
∑_{k=0}^{n} q^{−k}a_{k} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(−1)^{k}q^{−kn+\binom{k}{2}}b_{k}.  (4)

Proof. First note that it is much easier to prove this than to find it (it took me a few hours, but I am not too experienced). We note that, as is usual in such cases, it is sufficient to prove it for a basis of the vector space of polynomials. Here, we choose a_{n} = q^{n}x^{n}(1 − \frac{1}{x}) for n ≥ 1 and a_{0} = 1.

A q–ANALOGUE OF A FORMULA OF HERNANDEZ 3

We need the following standard formulæ that are consequences of the q–binomial theorem (see e. g. [2]):

∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(−1)^{k}x^{k} = (x; q)_{n},

∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(x; q)_{k}x^{n−k} = 1

We plug the form of a_{n} into the right hand side of (3) and obtain

(1 − \frac{1}{x}) ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(−1)^{k}q^{k}x^{k} = (1 − \frac{1}{x})(qx; q)_{n} = −\frac{1}{x}(x; q)_{n+1} = ∑_{k=0}^{n} b_{k}.

Thus

b_{n} = −\frac{1}{x}(x; q)_{n+1} + \frac{1}{x}(x; q)_{n} = −\frac{1}{x}(x; q)_{n}(1 − xq^{n} − 1) = q^{n}(x; q)_{n}.

We are done if these values of a_{n} and b_{n} also satisfy the relation (4). Note that (4) can be rewritten as

∑_{k=0}^{n} q^{−k}a_{k} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{1/q}(−1)^{k}q^{−\binom{k+1}{2}}b_{k}.

We plug b_{n} into the right hand side of (4) and obtain

∑_{k=0}^{n} \left[{n \atop k}\right]_{1/q}(−1)^{k}q^{−\binom{k+1}{2}}q^{k}(x; q)_{k} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{1/q}(−1)^{k}x^{k}(\frac{1}{x}; \frac{1}{q})_{k} = x^{n} = ∑_{k=0}^{n} q^{−k}a_{k}.

Thus

q^{−n}a_{n} = x^{n} − x^{n−1} = x^{n}(1 − \frac{1}{x}).

We would like to remark that an alternative proof could be found by dealing with the matrices of connecting coefficients.

Define matrices

T := [\left[{n \atop k}\right]_{q}(−1)^{k}q^{\binom{k}{2}}]_{n,k} , S := [\left[{n \atop k}\right]_{q}(−1)^{k}q^{−kn+\binom{k}{2}}]_{n,k} ,

U = [1_{n≥k}]_{n,k}, and V = [q^{−k}1_{n≥k}]_{n,k}.

Then we have to prove that S = V T^{−1}U.

This is not too hard, since

T^{−1} = [\left[{n \atop k}\right]_{q}(−1)^{k}q^{−kn+\binom{k+1}{2}}]_{n,k} ,

and

T^{−1}U = [\left[{n − 1 \atop k − 1}\right]_{q}(−1)^{k}q^{−n(k−1)+\binom{k}{2}}]_{n,k} .

Theorem 1. [q–analogue of Hernández’ formula]

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

References

[1] 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.

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

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

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

[5] V. Hernández. Solution IV of problem 10490 (a reciprocal summation identity). American Mathematical Monthly, 106:589–590, 1999.

Helmut Prodinger, Centre for Applicable Analysis and Number Theory, Department of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg,

South Africa, email: helmut@gauss.cam.wits.ac.za.