Factors of alternating sums of products of binomial and q-binomial coefficients

Victor J. W. Guo, Frédéric Jouhet and Jiang Zeng

Abstract. In this paper we study the factors of some alternating sums of products of binomial and q-binomial coefficients. We prove that for all positive integers n_{1}, …, n_{m}, n_{m+1} = n_{1}, and 0 ≤ j ≤ m − 1,

\left[{n_{1} + n_{m} \atop n_{1}}\right]^{−1} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{jk^{2}+\binom{k}{2}} ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i} + k}\right] ∈ ℕ[q],

which generalizes a result of Calkin [Acta Arith. 86 (1998), 17–26]. Moreover, we show that for all positive integers n, r and j,

\left[{2n \atop n}\right]^{−1}\left[{2j \atop j}\right] ∑_{k=j}^{n}(−1)^{n−k}q^{A} \frac{1 − q^{2k+1}}{1 − q^{n+k+1}} \left[{2n \atop n − k}\right]\left[{k + j \atop k − j}\right]^{r} ∈ ℕ[q],

where A = (r − 1)\binom{n}{2} + r\binom{j+1}{2} + \binom{k}{2} − rjk, which solves a problem raised by Zudilin [Electron. J. Combin. 11 (2004), #R22].

AMS Subject Classifications (2000): 05A10, 05A30, 11B65.

1 Introduction

In 1998, Calkin [4] proved that for all positive integers m and n,

\binom{2n}{n}^{−1} ∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{m}  (1.1)

is an integer by arithmetical techniques. For m = 1, 2 and 3, by the binomial theorem, Kummer’s formula and Dixon’s formula, it is easy to see that (1.1) is equal to 0, 1 and \binom{3n}{n}, respectively. Recently in the study of finite forms of the Rogers-Ramanujan identities [9] we stumbled across (1.1) for m = 4 and m = 5, which gives

∑_{k=0}^{n} \binom{2n + k}{k}\binom{2n}{n + k}^{2} and ∑_{k=0}^{n} \binom{3n − k}{n − k}\binom{2n + k}{k}\binom{2n}{n + k}^{2},

respectively. Indeed, de Bruijn [3] has shown that for m ≥ 4 there is no closed form for (1.1) by asymptotic techniques. Our first objective is to give a q-analogue of Calkin’s result, which also implies that (1.1) is positive for m ≥ 2.

In 2004, Zudilin [14] proved that for all positive integers n, j and r,

\binom{2n}{n}^{−1}\binom{2j}{j} ∑_{k=j}^{n}(−1)^{n−k} \frac{2k + 1}{n + k + 1}\binom{2n}{n − k}\binom{k + j}{k − j}^{r} ∈ ℤ,  (1.2)

which was originally observed by Strehl [12] in 1994. In fact, Zudilin’s motivation was to solve the following problem, which was raised by Schmidt [11] in 1992 and was apparently not related to Calkin’s result.

Problem 1.1 (Schmidt [11]). For any integer r ≥ 2, define a sequence of numbers {c_{k}^{(r)}}_{k∈ℕ}, independent of the parameter n, by

∑_{k=0}^{n} \binom{n}{k}^{r}\binom{n + k}{k}^{r} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}c_{k}^{(r)},

Is it true that all the numbers c_{k}^{(r)} are integers?

At the end of his paper, Zudilin [14] raised the problem of finding and solving a q-analogue of Problem 1.1. Our second objective is to provide such a q-analogue.

For any integer n, define the q-shifted factorial (a)_{n} by (a)_{0} = 1 and

(a)_{n} = \begin{cases}(1 − a)(1 − aq) ⋯ (1 − aq^{n−1}), & n = 1, 2, …, \\ (1 − aq^{−1})(1 − aq^{−2}) ⋯ (1 − aq^{n})^{−1}, & n = −1, −2, …. \end{cases}

We will also use the compact notations for m ≥ 1:

(a_{1}, …, a_{m})_{n} := (a_{1})_{n} ⋯ (a_{m})_{n}, (a_{1}, …, a_{m})_{∞} := lim_{n→∞}(a_{1}, …, a_{m})_{n}.

The q-binomial coefficients are defined as

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

Since \frac{1}{(q)_{n}} = 0 if n < 0, we have \left[{n \atop k}\right] = 0 if k > n or k < 0.

The following is our first generalization of Calkin’s result.

Theorem 1.2. For m ≥ 3 and all positive integers n_{1}, …, n_{m}, there holds

∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{(m−1)k^{2}+\binom{k}{2}} ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i} + k}\right]

= \left[{n_{1} + n_{m} \atop n_{1}}\right] ∑_{λ} ∏_{i=1}^{m−2} q^{λ_{i}^{2}} \left[{λ_{i−1} \atop λ_{i}}\right]\left[{n_{i+1} + n_{i+2} \atop n_{i+1} − λ_{i}}\right],  (1.3)

where n_{m+1} = λ_{0} = n_{1} and the sum is over all sequences λ = (λ_{1}, …, λ_{m−2}) of nonnegative integers such that λ_{0} ≥ λ_{1} ≥ ⋯ ≥ λ_{m−2}.

Calkin [4] has given a partial q-analogue of (1.1) by considering the alternating sum ∑_{k=0}^{n}(−1)^{k}q^{jk}\left[{n \atop k}\right]^{m}. In this respect, besides (1.3), we shall also prove the following divisibility result.

Theorem 1.3. For all positive integers n_{1}, …, n_{m}, n_{m+1} = n_{1}, the alternating sum

S(n_{1}, …, n_{m}; j, q) := \left[{n_{1} + n_{m} \atop n_{1}}\right]^{−1} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{jk^{2}+\binom{k}{2}} ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i} + k}\right]

is a polynomial in q with nonnegative integral coefficients for 0 ≤ j ≤ m − 1.

We shall give two proofs of Theorem 1.2: The first one is based on a recurrence relation formula for S(n_{1}, …, n_{m}; j, q), which also leads to a proof of Theorem 1.3. The second one follows directly from Andrews’ basic hypergeometric identity between a single sum and a multiple sum [1, Theorem 4].

Theorem 1.4 (Andrews [1]). For every integer m ≥ 0, the following identity holds:

∑_{k≥0} \frac{(a, q\sqrt{a}, −q\sqrt{a}, b_{1}, c_{1}, …, b_{m}, c_{m}, q^{−N})_{k}}{(q, \sqrt{a}, −\sqrt{a}, aq/b_{1}, aq/c_{1}, …, aq/b_{m}, aq/c_{m}, aq^{N+1})_{k}} (\frac{a^{m}q^{m+N}}{b_{1}c_{1} ⋯ b_{m}c_{m}} )^{k}

= \frac{(aq, aq/b_{m}c_{m})_{N}}{(aq/b_{m}, aq/c_{m})_{N}} ∑_{l_{1},...,l_{m−1}≥0} \frac{(aq/b_{1}c_{1})_{l_{1}} ⋯ (aq/b_{m−1}c_{m−1})_{l_{m−1}}}{(q)_{l_{1}} ⋯ (q)_{l_{m−1}}}

× \frac{(b_{2}, c_{2})_{l_{1}} … (b_{m}, c_{m})_{l_{1}+···+l_{m−1}}}{(aq/b_{1}, aq/c_{1})_{l_{1}} … (aq/b_{m−1}, aq/c_{m−1})_{l_{1}+···+l_{m−1}}}

× \frac{(q^{−N})_{l_{1}+···+l_{m−1}}}{(b_{m}c_{m}q^{−N}/a)_{l_{1}+···+l_{m−1}}} \frac{(aq)^{l_{m−2}+···+(m−2)l_{1}}q^{l_{1}+···+l_{m−1}}}{(b_{2}c_{2})^{l_{1}} ⋯ (b_{m−1}c_{m−1})^{l_{1}+···+l_{m−2}}} . (1.4)

Note that there are two ingredients in Zudilin’s approach to Problem 1.1: one is Theorem 1.4 with q = 1 and the other is the Legendre transform. Now, a q-Legendre transform reads:

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

which is a special case of Carlitz’s q-Gould-Hsu inverse formula [5] (see also [10]). Using (1.5) and Theorem 1.4 in its full generality we are able to formulate and prove a q-analogue of Problem 1.1.

Theorem 1.5. For any integer r ≥ 1, define rational fractions c_{k}^{(r)}(q) of the variable q, independent of n, by writing

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

Then c_{n}^{(r)}(q) ∈ ℕ[q].

Remark. Since the r = 1 case is trivial, we suppose that r ≥ 2 in what follows. As \left[{n \atop k}\right]\left[{n+k \atop k}\right] = \left[{2k \atop k}\right]\left[{n+k \atop n−k}\right], invoking (1.5) we derive immediately from (1.6) that

q^{(1−r)\binom{n}{2}}\left[{2n \atop n}\right]c_{n}^{(r)}(q) = ∑_{j=0}^{n} \left[{2j \atop j}\right]^{r}t_{n,j}^{(r)}(q),

where

t_{n,j}^{(r)}(q) = q^{r\binom{j+1}{2}} ∑_{k=j}^{n}(−1)^{n−k} \frac{1 − q^{2k+1}}{1 − q^{n+k+1}} \left[{2n \atop n − k}\right]\left[{k + j \atop k − j}\right]^{r}q^{\binom{k}{2}−rjk}.

Therefore Theorem 1.5 is a consequence of the following theorem, which is our q-analogue of Zudilin’s result (1.2).

Theorem 1.6. For any integer r ≥ 2, we have

q^{(r−1)\binom{n}{2}}\left[{2j \atop j}\right]\left[{2n \atop n}\right]^{−1}t_{n,j}^{(r)}(q) ∈ ℕ[q].

As will be shown, Theorem 1.6 follows directly from Andrews’ identity (1.4). This paper is organized as follows. We will prove Theorems 1.2 and 1.3 in the

next section. The proof of Theorem 1.6 is given in Section 3. Some interesting divisibility results are given in Section 4. In the last section we will present four related conjectures.

2 Proof of Theorems 1.2 and 1.3

We will need two known identities in q-series. One is the q-Pfaff-Saalschütz identity [6, Appendix (II.12)] (see also [7, 13]):

\left[{n_{1} + n_{2} \atop n_{1} + k}\right]\left[{n_{2} + n_{3} \atop n_{2} + k}\right]\left[{n_{3} + n_{1} \atop n_{3} + k}\right] = ∑_{r=0}^{n_{1}−k} \frac{q^{k^{2}+2kr}(q)_{n_{1}+n_{2}+n_{3}−k−r}}{(q)_{r}(q)_{r+2k}(q)_{n_{1}−k−r}(q)_{n_{2}−k−r}(q)_{n_{3}−k−r}} , (2.1)

where \frac{1}{(q)_{n}} = 0 if n < 0, and the other is the q-Dixon identity:

∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{(3k^{2}−k)/2}\left[{n_{1} + n_{2} \atop n_{1} + k}\right]\left[{n_{2} + n_{3} \atop n_{2} + k}\right]\left[{n_{3} + n_{1} \atop n_{3} + k}\right] = \frac{(q)_{n_{1}+n_{2}+n_{3}}}{(q)_{n_{1}}(q)_{n_{2}}(q)_{n_{3}}} . (2.2)

A short proof of (2.2) is given in [8].

We first establish the following recurrence formula.

Lemma 2.1. Let m ≥ 3. Then for all positive integers n_{1}, …, n_{m} and any integer j, the following recurrence holds:

S(n_{1}, …, n_{m}; j, q) = ∑_{l=0}^{n_{1}} q^{l^{2}} \left[{n_{1} \atop l}\right]\left[{n_{2} + n_{3} \atop n_{2} − l}\right]S(l, n_{3}, …, n_{m}; j − 1, q).  (2.3)

Proof. For any integer k and positive integers a_{1}, …, a_{l}, let

C(a_{1}, …, a_{l}; k) = ∏_{i=1}^{l} \left[{a_{i} + a_{i+1} \atop a_{i} + k}\right],

where a_{l+1} = a_{1}. Then

S(n_{1}, …, n_{m}; j, q) = \frac{(q)_{n_{1}}(q)_{n_{m}}}{(q)_{n_{1}+n_{m}}} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{jk^{2}+\binom{k}{2}}C(n_{1}, …, n_{m}; k). (2.4)

We observe that for m ≥ 3, we have

C(n_{1}, …, n_{m}; k) = \frac{(q)_{n_{2}+n_{3}}(q)_{n_{m}+n_{1}}}{(q)_{n_{1}+n_{2}}(q)_{n_{m}+n_{3}}} \left[{n_{1} + n_{2} \atop n_{1} + k}\right]\left[{n_{1} + n_{2} \atop n_{2} + k}\right]C(n_{3}, …, n_{m}; k),

and, by letting n_{3} → ∞ in (2.1),

\left[{n_{1} + n_{2} \atop n_{1} + k}\right]\left[{n_{1} + n_{2} \atop n_{2} + k}\right] = ∑_{r=0}^{n_{1}−k} \frac{q^{r^{2}+2kr}(q)_{n_{1}+n_{2}}}{(q)_{r}(q)_{r+2k}(q)_{n_{1}−k−r}(q)_{n_{2}−k−r}} .

Plugging these into (2.4) we can write its right-hand side as

R := ∑_{k=−n_{1}}^{n_{1}} ∑_{r=0}^{n_{1}−k}(−1)^{k}C(n_{3}, …, n_{m}; k)\frac{q^{(r+k)^{2}+(j−1)k^{2}+\binom{k}{2}}(q)_{n_{2}+n_{3}}(q)_{n_{1}}(q)_{n_{m}}}{(q)_{r}(q)_{r+2k}(q)_{n_{1}−k−r}(q)_{n_{2}−k−r}(q)_{n_{m}+n_{3}}} .

Setting l = r + k, then −n_{1} ≤ l ≤ n_{1}, but if l < 0, at least one of the indices l + k and l − k is negative for any integer k, which implies that \frac{1}{(q)_{l−k}(q)_{l+k}} = 0 by convention. Therefore, exchanging the order of summation, we have

R = ∑_{l=0}^{n_{1}} \frac{q^{l^{2}}(q)_{n_{2}+n_{3}}(q)_{n_{1}}(q)_{n_{m}}}{(q)_{n_{1}−l}(q)_{n_{2}−l}(q)_{n_{m}+n_{3}}} ∑_{k=−l}^{l}(−1)^{k}C(n_{3}, …, n_{m}; k)\frac{q^{(j−1)k^{2}+\binom{k}{2}}}{(q)_{l−k}(q)_{l+k}} .

Now, in the last sum making the substitution

C(n_{3}, …, n_{m}; k) = \frac{(q)_{l−k}(q)_{l+k}(q)_{n_{m}+n_{3}}}{(q)_{n_{3}+l}(q)_{n_{m}+l}} C(l, n_{3}, …, n_{m}; k),

we obtain the right-hand side of (2.3).

First proof of Theorem 1.2. Letting n_{3} → ∞ in (2.2) yields that

S(n_{1}, n_{2}; 1, q) = 1.  (2.5)

Theorem 1.2 then follows by iterating (m − 2) times formula (2.3).

Second proof of Theorem 1.2. Since

\left[{M \atop N + k}\right] = (−1)^{k}q^{(M−N)k−\binom{k}{2}}\left[{M \atop N}\right]\frac{(q^{−M+N})_{k}}{(q^{N+1})_{k}} ,

by collecting the terms of index k and −k, the left-hand side of (1.3) can be written as

L := ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i}}\right] + ∑_{k=1}^{n_{1}}(1 + q^{k})(−1)^{k}q^{(m−1)k^{2}+\binom{k}{2}} ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i} + k}\right]

= ∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i}}\right] \{1 + ∑_{k=1}^{n_{1}}(1 + q^{k})(−1)^{(m−1)k}q^{(m−1)\binom{k+1}{2}} ∏_{i=1}^{m} q^{n_{i}k} \frac{(q^{−n_{i+1}})_{k}}{(q^{n_{i}+1})_{k}} \} .

Letting c_{1} = c_{2} = ⋯ = c_{m} = c → ∞ and a → 1 in Andrews’ formula (1.4) we get

1+ ∑_{k≥1}(1 + q^{k})\frac{(b_{1}, …, b_{m}, q^{−N})_{k}}{(q/b_{1}, …, q/b_{m}, q^{N+1})_{k}} (−1)^{mk}q^{m\binom{k}{2}} (\frac{q^{m+N}}{b_{1}b_{2} … b_{m}} )^{k}

= \frac{(q)_{N}}{(q/b_{m})_{N}} ∑_{l_{1},...,l_{m−1}≥0} \frac{(q)_{N}}{(q)_{l_{1}} ⋯ (q)_{l_{m−1}}(q)_{N−l_{1}−···−l_{m−1}}}

× ∏_{i=1}^{m−1} \frac{(b_{i+1})_{l_{1}+···+l_{i}}}{(q/b_{i})_{l_{1}+···+l_{i}}} (\frac{−1}{b_{i+1}} )^{l_{1}+···+l_{i}} q^{\binom{l_{1}+···+l_{i}}{2}+(m−i)l_{i}}.  (2.6)

Now, shifting m to m − 1 in (2.6), setting

N = n_{m}, b_{i} = q^{−n_{i}} for i = 1, …, m − 1,

and λ_{i} = l_{1} + ⋯ + l_{i} for i = 1, …, m − 2, one sees that L equals

∏_{i=1}^{m} \left[{n_{i} + n_{i+1} \atop n_{i}}\right] \frac{(q)_{n_{m}}^{2}}{(q^{1+n_{m−1}})_{n_{m}}} ∑_{0≤λ_{1}≤···≤λ_{m−2}} ∏_{i=1}^{m−2} \frac{(q^{−n_{i+1}})_{λ_{i}}(−1)^{λ_{i}}q^{\binom{λ_{i}+1}{2}+n_{i+1}λ_{i}}}{(q^{1+n_{i}})_{λ_{i}}(q)_{λ_{i}−λ_{i−1}}}

= \left[{n_{1} + n_{m} \atop n_{1}}\right] ∑_{0≤λ_{1}≤···≤λ_{m−2}} ∏_{i=1}^{m−2} q^{λ_{i}^{2}} \left[{λ_{i+1} \atop λ_{i}}\right]\left[{n_{i} + n_{i+1} \atop n_{i} + λ_{i}}\right],

where λ_{0} = 0 and λ_{m−1} = n_{m}. The latter identity is clearly equivalent to Theorem 1.2.

In order to prove Theorem 1.3, we shall need the following relation:

S(n_{1}, …, n_{m}; 0, q) = S(n_{1}, …, n_{m}; m − 1, q^{−1}) q^{n_{1}n_{2}+n_{2}n_{3}+···+n_{m−1}n_{m}}. (2.7)

As \left[{n \atop k}\right]_{q^{−1}} = \left[{n \atop k}\right]q^{k(k−n)}, Eq. (2.7) can be verified by substituting q by q^{−1} and then replacing k by −k in the definition of S(n_{1}, …, n_{m}; m − 1, q).

Proof of Theorem 1.3. We proceed by induction on m ≥ 1. By the q-binomial theorem [6, (II.3)], we have

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

In view of (2.5), it follows from (2.7) that

S(n_{1}, n_{2}; 0, q) = S(n_{1}, n_{2}; 1, q^{−1}) q^{n_{1}n_{2}} = q^{n_{1}n_{2}}.

So the theorem is valid for m ≤ 2.

Now suppose that the expression S(n_{1}, …, n_{m−1}; j, q) is a polynomial in q with nonnegative integral coefficients for some m ≥ 3 and 0 ≤ j ≤ m − 2. Then by the recurrence formula (2.3), so is S(n_{1}, …, n_{m}; j, q) for 1 ≤ j ≤ m − 1. It remains to show that S(n_{1}, …, n_{m}; 0, q) has the required property. By Theorem 1.2 we know that S(n_{1}, …, n_{m}; m−1, q) is a polynomial in q. Since the q-binomial coefficient \left[{n \atop k}\right] is a polynomial in q of degree k(n − k) (see [2, p. 33]), it is easy to see from the definition of S(n_{1}, …, n_{m}; m − 1, q) that the degree of the polynomial S(n_{1}, …, n_{m}; m−1, q) is less than or equal to n_{1}n_{2} +n_{2}n_{3} +⋯+ n_{m−1}n_{m}. It follows from (2.7) that S(n_{1}, …, n_{m}; 0, q) is also a polynomial in q with nonnegative integral coefficients. This completes the inductive step of the proof.

Remark. Though it is not necessary to check the m = 3 case to valid our induction argument, we think it is convenient to include here the formulas for m = 3. First, the q-Dixon identity (2.2) implies that

S(n_{1}, n_{2}, n_{3}; 1, q) = \left[{n_{1} + n_{2} + n_{3} \atop n_{2}}\right].

From (2.3) and (2.5) we derive

S(n_{1}, n_{2}, n_{3}; 2, q) = ∑_{l=0}^{n_{1}} q^{l^{2}} \left[{n_{1} \atop l}\right]\left[{n_{2} + n_{3} \atop n_{2} − l}\right].

Finally, applying (2.7) we get

S(n_{1}, n_{2}, n_{3}; 0, q) = S(n_{1}, n_{2}, n_{3}; 2, q^{−1}) q^{n_{1}n_{2}+n_{2}n_{3}}

= ∑_{l=0}^{n_{1}} q^{(n_{1}−l)(n_{2}−l)+n_{3}l}\left[{n_{1} \atop l}\right]\left[{n_{2} + n_{3} \atop n_{2} − l}\right].

3 Proof of Theorem 1.6

We will distinguish the cases where r ≥ 2 is even or odd, and treat separately the values r = 2 and r = 3.

• For r = 2, apply (1.4) specialized with m = 1, a = q^{−(2n+1)}, N = n − j, b_{1} = q^{−n} and c_{1} = q^{−(n−j)}. The left-hand side of (1.4) is then equal to

\left[{n + j \atop 2j}\right]^{−2}q^{−2\binom{n−j}{2}+\binom{n}{2}}t_{n,j}^{(2)}(q).

Equating this with the right-hand side gives

t_{n,j}^{(2)}(q) = \frac{(q)_{2n}(q)_{j}^{2}}{(q)_{n}(q)_{2j}(q)_{2j−n}(q)_{n−j}^{2}} q^{2\binom{n−j}{2}−\binom{n}{2}},

which shows that \left[{2j \atop j}\right]\left[{2n \atop n}\right]^{−1}q^{\binom{n}{2}}t_{n,j}^{(2)}(q) ∈ ℕ[q].

• For r = 3, apply (1.4) specialized with m = 1, a = q^{−(2n+1)}, N = n − j and b_{1} = c_{1} = q^{−(n−j)}. This yields in that case

t_{n,j}^{(3)}(q) = \frac{(q)_{2n}}{(q)_{3j−n}(q)_{n−j}^{3}} q^{3\binom{n−j}{2}−2\binom{n}{2}},

which shows that \left[{2j \atop j}\right]\left[{2n \atop n}\right]^{−1}q^{2\binom{n}{2}}t_{n,j}^{(3)}(q) ∈ ℕ[q].

• For r = 2s ≥ 4, apply (1.4) with m = s ≥ 2, a = q^{−(2n+1)}, N = n − j, b_{1} = q^{−n} and c_{1} = b_{i} = c_{i} = q^{−(n−j)}, ∀ i ∈ {2, …, s} to get

q^{(2s−1)\binom{n}{2}−2s\binom{n−j}{2}} t_{n,j}^{(2s)}(q) =

\frac{(q)_{2n}(q)_{j}}{(q)_{n}(q)_{2j}(q)_{n−j}} ∑_{l_{1}≥0} \left[{j \atop l_{1}}\right]\left[{n − l_{1} \atop j}\right]\left[{n − l_{1} + j \atop n − l_{1} − j}\right]q^{\binom{l_{1}}{2}+2j(s−1)l_{1}+(j+1−n)l_{1}}

× ∑_{l_{2}≥0} \left[{2j \atop l_{2}}\right]\left[{n − l_{1} − l_{2} + j \atop n − l_{1} − l_{2} − j}\right]^{2}q^{\binom{l_{2}}{2}+2j(s−2)l_{2}+(j+1−n)l_{2}} × ⋯

× ∑_{l_{s−1}≥0} \left[{2j \atop l_{s−1}}\right]\left[{n − l_{1} − ⋯ − l_{s−1} + j \atop n − l_{1} − ⋯ − l_{s−1} − j}\right]^{2}q^{\binom{l_{s−1}}{2}+2jl_{s−1}+(j+1−n)l_{s−1}}

× \left[{2j \atop n − l_{1} − ⋯ − l_{s−1} − j}\right]q^{\binom{l_{1}+···+l_{s−1}}{2}}.

As the condition l_{1} + ⋯ + l_{s−1} ≤ n − j holds in the last summation, we can see that for s ≥ 2, \left[{2j \atop j}\right]\left[{2n \atop n}\right]^{−1}q^{(2s−1)\binom{n}{2}} t_{n,j}^{(2s)}(q) ∈ ℕ[q].

• For r = 2s + 1 ≥ 5, apply (1.4) with m = s ≥ 2, a = q^{−(2n+1)}, N = n − j,

and b_{i} = c_{i} = q^{−(n−j)}, ∀ i ∈ {1, …, s} to get
q^{2s\binom{n}{2}−(2s+1)\binom{n−j}{2}}t_{n,j}^{(2s+1)}(q) =

\frac{(q)_{2n}}{(q)_{2j}(q)_{n−j}^{2}} ∑_{l_{1}≥0} \left[{2j \atop l_{1}}\right]\left[{n − l_{1} + j \atop n − l_{1} − j}\right]^{2}q^{\binom{l_{1}}{2}+2j(s−1)l_{1}+(j+1−n)l_{1}}

× ∑_{l_{2}≥0} \left[{2j \atop l_{2}}\right]\left[{n − l_{1} − l_{2} + j \atop n − l_{1} − l_{2} − j}\right]^{2}q^{\binom{l_{2}}{2}+2j(s−2)l_{2}+(j+1−n)l_{2}} × ⋯

× ∑_{l_{s−1}≥0} \left[{2j \atop l_{s−1}}\right]\left[{n − l_{1} − ⋯ − l_{s−1} + j \atop n − l_{1} − ⋯ − l_{s−1} − j}\right]^{2}q^{\binom{l_{s−1}}{2}+2jl_{s−1}+(j+1−n)l_{s−1}}

× \left[{2j \atop n − l_{1} − ⋯ − l_{s−1} − j}\right]q^{\binom{l_{1}+···+l_{s−1}}{2}}.

As the condition l_{1} + ⋯ + l_{s−1} ≤ n − j holds in the last summation, we can see that for s ≥ 2, \left[{2j \atop j}\right]\left[{2n \atop n}\right]^{−1}q^{2s\binom{n}{2}} t_{n,j}^{(2s+1)}(q) ∈ ℕ[q].

Remark. In the special case r = 2, our proof gives the following expression for the coefficients c_{n}^{(2)}(q):

c_{n}^{(2)}(q) = ∑_{j=0}^{n} \left[{2j \atop n}\right]\left[{n \atop j}\right]^{2}q^{2\binom{n−j}{2}}.  (3.1)

These coefficients are q-analogues of the famous c_{n}^{(2)}(1) involved in Apery’s proof of the irrationality of ζ(3):

c_{n}^{(2)}(1) = ∑_{j=0}^{n} \binom{2j}{n}\binom{n}{j}^{2} = ∑_{j=0}^{n} \binom{n}{j}^{3}.  (3.2)

As explained in [12], when q = 1, one can derive the last expression from (3.1) in an elementary way (by two iteration of the Chu-Vandermonde formula). But our q-analogue (3.1) does not lead to a natural q-analogue of (3.2).

4 Consequences of Theorems 1.2 and 1.3

Letting q = 1 in Theorem 1.2 we obtain a direct generalization of Calkin’s result (1.1).

Theorem 4.1. For m ≥ 3 and all positive integers n_{1}, …, n_{m}, there holds

∑_{k=−n_{1}}^{n_{1}}(−1)^{k} ∏_{i=1}^{m} \binom{n_{i} + n_{i+1}}{n_{i} + k} = \binom{n_{1} + n_{m}}{n_{1}} ∑_{λ} ∏_{i=1}^{m−2} \binom{λ_{i−1}}{λ_{i}}\binom{n_{i+1} + n_{i+2}}{n_{i+1} − λ_{i}},

(4.1)

where n_{m+1} = λ_{0} = n_{1} and the sum is over all sequences λ = (λ_{1}, …, λ_{m−2}) of nonnegative integers such that λ_{0} ≥ λ_{1} ≥ ⋯ ≥ λ_{m−2}.

Remark. For m = 1 and 2, it is easy to see that the left-hand side of (4.1) is equal to 0 and \binom{n_{1}+n_{2}}{n_{1}}, respectively. Calkin’s result follows from (4.1) by setting n_{i} = n for all i = 1, …, m.

Letting n_{1} = ⋯ = n_{m} = n in Theorem 1.3, we obtain a complete q-analogue of Calkin’s result. Corollary 4.2. For all positive m, n and 0 ≤ j ≤ m − 1,

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

is a polynomial in q with nonnegative integral coefficients.

Letting n_{2i−1} = m and n_{2i} = n for 1 ≤ i ≤ r in Theorem 1.3, we obtain Corollary 4.3. For all positive m, n, r and 0 ≤ j ≤ 2r − 1,

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

is a polynomial in q with nonnegative integral coefficients. In particular,

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

is divisible by \binom{m+n}{m}.

Letting n_{3i−2} = l, n_{3i−1} = m and n_{3i} = n for 1 ≤ i ≤ r in Theorem 1.3, we obtain Corollary 4.4. For all positive l, m, n, r and 0 ≤ j ≤ 3r − 1,

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

is a polynomial in q with nonnegative integral coefficients. In particular,

∑_{k=−l}^{l}(−1)^{k}\binom{l + m}{l + k}^{r}\binom{m + n}{m + k}^{r}\binom{n + l}{n + k}^{r}

is divisible by \binom{l+m}{l}, \binom{m+n}{m} and \binom{n+l}{n}.

Letting m = 2r + s, n_{1} = n_{3} = ⋯ = n_{2r−1} = n + 1 and let all the other n_{i} be n in Theorem 4.1, we get Corollary 4.5. For all positive r, s and n,

∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{r}\binom{2n + 1}{n + k}^{r}\binom{2n}{n + k}^{s}

is divisible by both \binom{2n}{n} and \binom{2n+1}{n}, and is therefore divisible by (2n + 1)\binom{2n}{n}. However, the following result is not a special case of Theorem 4.1.

Corollary 4.6. For all nonnegative r and s and positive t and n,

∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{r}\binom{2n + 1}{n + k}^{s}\binom{2n}{n + k}^{t}.

is divisible by \binom{2n}{n}.

Proof. We proceed by induction on |r − s|. The r = s case is clear from Corollary 4.5. Suppose the statement is true for |r − s| ≤ m − 1. By Theorem 4.1, one sees that

∑_{k=−n}^{n}(−1)^{k}\binom{2n + 2}{n + k + 1}^{m}\binom{2n + 1}{n + k + 1}^{s}\binom{2n + 1}{n + k}^{s}\binom{2n}{n + k}^{t}

= \frac{2n + 2}{2n + 1} ∑_{k=−n}^{n}(−1)^{k}\binom{2n + 2}{n + k + 1}^{m−1}\binom{2n + 1}{n + k + 1}^{s+1}\binom{2n + 1}{n + k}^{s+1}\binom{2n}{n + k}^{t−1}, (4.2)

where m, t ≥ 1, is divisible by

\frac{2n + 2}{2n + 1}\binom{2n + 1}{n} = 2\binom{2n}{n}.

By the binomial theorem, we have

\binom{2n + 2}{n + k + 1}^{m} = (\binom{2n + 1}{n + k + 1} + \binom{2n + 1}{n + k})^{m}
= ∑_{i=0}^{m} \binom{m}{i}\binom{2n + 1}{n + k + 1}^{i}\binom{2n + 1}{n + k}^{m−i}.  (4.3)

Substituting (4.3) into the left-hand of (4.2) and using the induction hypothesis and symmetry, we find that

∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{m+s}\binom{2n + 1}{n + k}^{s}\binom{2n}{n + k}^{t}

+ ∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{s}\binom{2n + 1}{n + k}^{m+s}\binom{2n}{n + k}^{t}

is divisible by 2\binom{2n}{n}. However, replacing k by −k, one sees that

∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{m+s}\binom{2n + 1}{n + k}^{s}\binom{2n}{n + k}^{t}

= ∑_{k=−n}^{n}(−1)^{k}\binom{2n + 1}{n + k + 1}^{s}\binom{2n + 1}{n + k}^{m+s}\binom{2n}{n + k}^{t}.

This proves that the statement is true for |r − s| = m.

It is clear that Theorems 1.3 and 4.1 can be restated in the following forms.

Theorem 4.7. For all positive integers n_{1}, …, n_{m} and 0 ≤ j ≤ m − 1, the alternating sum

(q)_{n_{1}} ∏_{i=1}^{m} \frac{(q)_{n_{i}+n_{i+1}}}{(q)_{2n_{i}}} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k}q^{jk^{2}+\binom{k}{2}} ∏_{i=1}^{m} \left[{2n_{i} \atop n_{i} + k}\right],

where n_{m+1} = 0, is a polynomial in q with nonnegative integral coefficients. Theorem 4.8. For all positive integers n_{1}, …, n_{m}, we have

n_{1}! ∏_{i=1}^{m} \frac{(n_{i} + n_{i+1})!}{(2n_{i})!} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k} ∏_{i=1}^{m} \binom{2n_{i}}{n_{i} + k} ∈ ℕ,

where n_{m+1} = 0.

It is easy to see that, for all positive integers m and n, the expression \frac{(2m)!(2n)!}{(m+n)!m!n!} is an integer. Letting n_{1} = ⋯ n_{r} = m and n_{r+1} = ⋯ = n_{r+s} = n in Theorem 4.8, we obtain Corollary 4.9. For all positive m, n, r and s,

∑_{k=−m}^{m}(−1)^{k}\binom{2m}{m + k}^{r}\binom{2n}{n + k}^{s}

is divisible by \frac{(2m)!(2n)!}{(m+n)!m!n!}.

In particular, we find that

∑_{k=−n}^{n}(−1)^{k}\binom{4n}{2n + k}^{r}\binom{2n}{n + k}^{s}

is divisible by \binom{4n}{n}, and

∑_{k=−n}^{n}(−1)^{k}\binom{6n}{3n + k}^{r}\binom{2n}{n + k}^{s}

is divisible by \frac{(6n)!(2n)!}{(4n)!(3n)!n!}.

From Theorem 4.8 it is easy to see that

n_{1}! ∏_{i=1}^{m} \frac{(n_{i} + n_{i+1})!}{(2n_{i})!} ∑_{k=−n_{1}}^{n_{1}}(−1)^{k} ∏_{i=1}^{m} \binom{2n_{i}}{n_{i} + k}^{r_{i}},

where n_{m+1} = 0, is a nonnegative integer for all r_{1}, …, r_{m} ≥ 1. For m = 3, letting (n_{1}, n_{2}, n_{3}) be (n, 3n, 2n), (2n, n, 3n), or (2n, n, 4n), we obtain the following two corollaries. Corollary 4.10. For all positive r, s, t and n,

∑_{k=−n}^{n}(−1)^{k}\binom{6n}{3n + k}^{r}\binom{4n}{2n + k}^{s}\binom{2n}{n + k}^{t}

is divisible by both \binom{6n}{n} and \binom{6n}{3n}. Corollary 4.11. For all positive r, s, t and n,

∑_{k=−n}^{n}(−1)^{k}\binom{8n}{4n + k}^{r}\binom{4n}{2n + k}^{s}\binom{2n}{n + k}^{t}

is divisible by \binom{8n}{3n}.

5 Some open problems

Based on computer experiments, we would like to present four interesting conjectures. The first two are refinements of Corollaries 4.10 and 4.11 respectively.

Conjecture 5.1. For all positive r, s, t and n,

∑_{k=−n}^{n}(−1)^{k}\binom{6n}{3n + k}^{r}\binom{4n}{2n + k}^{s}\binom{2n}{n + k}^{t}

is divisible by both 2\binom{6n}{n} and 6\binom{6n}{3n}.

Conjecture 5.2. For all positive r, s, t and n,

∑_{k=−n}^{n}(−1)^{k}\binom{8n}{4n + k}^{r}\binom{4n}{2n + k}^{s}\binom{2n}{n + k}^{t}

is divisible by 2\binom{8n}{3n}.

Let gcd(a_{1}, a_{2}, …) denote the greatest common divisor of integers a_{1}, a_{2}, ….

Conjecture 5.3. For all positive m and n, we have

gcd ( ∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{r}, r = m, m + 1, …) = \binom{2n}{n}.  (5.1)

Let d ≥ 2 be a fixed integer. Every nonnegative integer n can be uniquely written as

n = ∑_{i≥0} a_{i}d^{i},

where 0 ≤ a_{i} ≤ d−1 for all i and only finitely many number of b_{i} are nonzeros, denoted by n = [⋯ a_{1}a_{0}]_{d}, in which the first 0’s are omitted. Let n = [a_{1} ⋯ a_{r}]_{3} = [b_{1} ⋯ b_{s}]_{7} = [c_{1} ⋯ c_{t}]_{13}. We now define three statistics α(n), β(n) and γ(n) as follows.

• Let α(n) be the number of disconnected 2’s in the sequence a_{1} ⋯ a_{r}. Here two nonzero digits a_{i} and a_{j} are said to be disconnected if there is at least one 0 between a_{i} and a_{j}.

• Let β(n) be the number of 1’s in b_{1} ⋯ b_{s} which are not immediately followed by a 4, 5, or 6.

• Let γ(n) be the number of 1’s in c_{1} ⋯ c_{t} which are immediately followed by one of 7, …, 12, or immediately followed by a number of 6’s and then followed by one of 7, …, 12.

For instance, [20212]_{3} = 185 and so α(185) = 2; [10142]_{7} = 2480, and so β(2480) = 1; [1667]_{13} = 3296 and so γ(3296) = 1. The first n such that α(n) = 4 is [2020202]_{3} = 1640; the first n such that β(n) = 4 is [1111]_{7} = 400; while the first n such that γ(n) = 4 is [17171717]_{13} = 97110800.

We end this paper with the following conjecture.

Conjecture 5.4. For every positive integer n, we have

gcd ( ∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{3r}, r = 1, 2, …) = \binom{2n}{n}3^{α(n)},

gcd ( ∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{3r+1}, r = 1, 2, …) = \binom{2n}{n}7^{β(n)}13^{γ(n)},

gcd ( ∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{3r+2}, r = 1, 2, …) = \binom{2n}{n}.

Acknowledgments

This work was partially done during the first author’s visit to Institut Camille Jordan, Université Claude Bernard (Lyon I), and was supported by a French postdoctoral fellowship. We thank Christian Krattenthaler for conveying us his feeling that Theorem 1.2 should follow from Andrews’ formula [1, Theorem 1.4]. We also thank Wadim Zudilin for useful conversations during his visit in Lyon.

References

[1] G. E. Andrews, Problems and prospects for basic hypergeometric functions, Theory and application for basic hypergeometric functions, R. A. Askey, ed., Math. Res. Center, Univ. Wisconsin, Publ. No. 35, Academic Press, New York, 1975, pp. 191–224.

[2] G. E. Andrews, The Theory of Partitions, Cambridge University Press, Cambridge, 1998.

[3] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, New York, 1981.

[4] N. J. Calkin, Factors of sums of powers of binomial coefficients, Acta Arith. 86 (1998), 17–26.

[5] L. Carlitz, Some inverse relations, Duke Math. J. 40 (1973), 893–901.

[6] G. Gasper and M. Rahman, Basic Hypergeometric Series, Second Edition, Encyclopedia of Mathematics and Its Applications, Vol. 96, Cambridge University Press, Cambridge, 2004.

[7] V. J. W. Guo and J. Zeng, A combinatorial proof of a symmetric q-Pfaff-Saalschütz identity, Electron. J. Combin. 12 (2005), #N2.

[8] V. J. W. Guo and J. Zeng, A short proof of the q-Dixon identity, Discrete Math. 296 (2005), 259–261.

[9] V. J. W. Guo, F. Jouhet, and J. Zeng, New Finite Rogers-Ramanujan Identities, preprint, 2006, arXiv: math.CO/0604407.

[10] C. Krattenthaler, A new matrix inverse, Proc. Amer. Math. Soc. 124 (1996), 47–59.

[11] A. L. Schmidt, Legendre transforms and Apéry’s sequences, J. Austral. Math. Soc. Ser. A 58 (1995), 358–375.

[12] V. Strehl, Binomial identities — combinatorial and algorithmical aspects, Discrete Math. 136 (1994), 309–346.

[13] D. Zeilberger, A q-Foata proof of the q-Saalschütz identity, European J. Combin. 8 (1987), 461–463.

[14] W. Zudilin, On a combinatorial problem of Asmus Schmidt, Electron. J. Combin. 11 (2004), #R22.

Victor J. W. Guo^{1}, Frédéric Jouhet^{2} and Jiang Zeng^{3}

1Department of Mathematics, East China Normal University, Shanghai 200062, People’s Republic of China

jwguo@math.ecnu.edu.cn,  http://math.ecnu.edu.cn/~jwguo

2Université de Lyon, Université Lyon1, CNRS, UMR 5208 Institut Camille Jordan, Bâtiment du Doyen Jean Braconnier, 43, blvd du 11 novembre 1918, F-69622 Villeurbanne Cedex, France

jouhet@math.univ-lyon1.fr,  http://math.univ-lyon1.fr/~jouhet

3Université de Lyon, Université Lyon1, CNRS, UMR 5208 Institut Camille Jordan, Bâtiment du Doyen Jean Braconnier, 43, blvd du 11 novembre 1918, F-69622 Villeurbanne Cedex, France

zeng@math.univ-lyon1.fr,  http://math.univ-lyon1.fr/~zeng