A Method For Examining Divisibility Properties Of Some Binomial Sums

Jovan Mikić J.U. SŠC “Jovan Cvijić” 74480 Modriča Bosnia and Herzegovina

                   jnmikic@gmail.com

Abstract

We introduce a notion that we call a “D sum” and use it to examine the divisibility properties of some binomial sums. The method of D sums consists of two theorems and their proofs. We present two applications of our method to non-negative sums with absolute values. The third application is for a known alternating binomial sum. In particular, our method of D sums can be used to prove Dixon’s formula.

1 Introduction

Let m, n, and k be non-negative integers such that m ≥ 2. We consider the sum

S(n, m) = ∑_{k=0}^{n} \binom{n}{k}^{m}F (n, k),  (1)

where F (n, k) is an integer-valued function that depends only on n and k.

The aim is to examine some divisibility properties of sums of the form S(n, m). To do this, we introduce the notion of “D sums”.^{1} Definition 1. Let n, j, and t be non-negative integers such that j ≤ ⌊\frac{n}{2}⌋. Then the D sums for S(n, m) are as follows:

1So-named in honor of professor Duško Jojić.

D_{S}(n, j, t) = ∑_{l=0}^{n−2j} \binom{n − j}{l}\binom{n − j}{j + l}\binom{n}{j + l}^{t}F (n, j + l).  (2)

Obviously, for m ≥ 2, the equation

S(n, m) = D_{S}(n, 0, m − 2)  (3)

holds.

Hence, we can see the sum D_{S}(n, j, m − 2) as a generalization of the sum S(n, m).

We search for new theorems and facts about D_{S}(n, j, t) sums, which may be useful for studying S(n, m) sums.

Let n, j, and t be as in Definition 1. The method of D sums consists of the following two theorems:

Theorem 2.

D_{S}(n, j, t + 1) = ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n}{j + u}\binom{n − j}{u}D_{S}(n, j + u, t).

Theorem 3.

D_{S}(n, j, 0) = ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n − j}{j + u}\binom{n − 2j − u}{u} ∑_{v=0}^{n−2j−2u} \binom{n − 2j − 2u}{v}F (n, j + u + v).

Together, Theorems 2 and 3 give a recursive definition of a D_{S} sum.

2 Background

In 1891, Dixon [11] found the following identity [16, Eq. (6.6), p. 51]:

∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{3} = (−1)^{n}\binom{2n}{n}\binom{3n}{2n},  (4)

where n is a non-negative integer. The absolute value of the right-hand side is sequence \underline{A006480} in the On-Line Encyclopedia of Integer Sequences.

Moreover, Dixon [12] established the following generalization of Eq. (4):

∑_{k=−a}^{a}(−1)^{k}\binom{a + b}{a + k}\binom{b + c}{b + k}\binom{c + a}{c + k} = \frac{(a + b + c)!}{a! · b! · c!},  (5)

where a, b, and c are non-negative integers. Both identities are known in the literature as Dixon’s identities or Dixon’s formulas. For a = b = c = n, Eq. (5) becomes Eq. (4).

There are many proofs of Eq. (5): for example, see [13, 15, 17, 21]. However, there are not so many direct proofs of Eq. (4). Our goal is to give an elementary proof of Eq. (4) without using Eq. (5).

In order to find the desired proof, we discovered the method of D sums. Unfortunately, the method of D sums does not work on Eq. (5).

In 1998, Calkin [9, Thm. 1] proved that the alternating binomial sum ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{m} is divisible by \binom{2n}{n} for all non-negative integers n and all positive integers m. Calkin used arithmetical techniques in his proof.

There are several generalizations of Calkin’s result. In 2007, Guo, Jouhet, and Zeng proved, among other things, two generalizations of Calkin’s result [18, Thm. 1.2, Thm. 1.3]. In the same paper they proposed several conjectures including Conjecture 5.3 which is a refinement of Calkin’s result. In 2010, Cao and Pan [10, Thm. 1.1] proved, among other results, Conjecture 5.3.

The rest of the paper is structured as follows. In Sections 3 and 4, we prove our main Theorems 2 and 3, respectively. In Section 5, we give a brief explanation of our method of D sums.

In Section 6, we consider two non-negative sums with absolute values: S_{1}(2n, m) = ∑_{k=0}^{2n} \binom{2n}{k}^{m}|n − k| and S_{2}(2n + 1, m) = ∑_{k=0}^{2n+1} \binom{2n+1}{k}^{m} |\frac{2n+1}{2} − k|. We assert, among other, that the first sum S_{1}(2n, m) is divisible by n\binom{2n}{n} for all positive integers n and all positive integers m . Similarly, we assert, among other, that the second sum S_{2}(2n+1, m) is divisible by (2n + 1)\binom{2n}{n} for all non-negative integers n and all positive integers m.

In Section 7, we begin with motivation for studying S_{1}(2n, m) and S_{2}(2n + 1, m) sums. Then we apply the method of D sums to prove our assertions for the sum S_{1}(2n, m). Proofs of our assertions for the second sum S_{2}(2n + 1, m) are omitted because they are similar to the proofs for the first sum S_{1}(2n, m).

In Section 8, we consider the alternating binomial sum S_{3}(2n, m) = ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{m}. We give a sketch of the proof of Calkin’s result [9, Thm. 1] by using our method of D

sums. Also, we give a sketch of the proof of Eq. (4).

3 Proof of Theorem 2

We use three well-known binomial identities.

The first one is the Chu-Vandermonde convolution formula:

∑_{k=0}^{c} \binom{a}{k}\binom{b}{c − k} = \binom{a + b}{c},  (6)

where a, b, and c are non-negative integers.

Let a, b, and c be non-negative integers such that a ≥ b ≥ c. The second identity is

\binom{a}{b}\binom{b}{c} = \binom{a}{c}\binom{a − c}{b − c}.  (7)

The third identity is symmetry of binomial coefficients. Proof. Let n, j, and t be as in Definition 1. By Definition 1, we know that

D_{S}(n, j, t + 1) = ∑_{l=0}^{n−2j} \binom{n − j}{l}\binom{n − j}{j + l}\binom{n}{j + l}^{t+1}F (n, j + l).  (8)

According to Eq. (6), we have

\binom{n − j}{l} = ∑_{u=0}^{l} \binom{n − 2j − l}{u}\binom{j + l}{l − u}.  (9)

Obviously, the following inequalities

u ≤ l,  (10)
u ≤ n − 2j − l.  (11)

hold.

From Inequalities (10) and (11), we obtain the following inequalities:

0 ≤ u ≤ ⌊\frac{n − 2j}{2} ⌋,  (12)
u ≤ l ≤ n − 2j − u.  (13)

We use Eq. (9), the symmetry \binom{n−j}{j+l} = \binom{n−j}{n−2j−l}, and the symmetry \binom{j+l}{l−u} = \binom{j+l}{j+u}, and then permute terms in Eq. (8). Thus Eq. (8) becomes as follows:

D_{S}(n, j, t + 1) = ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − 2j − l}{u}\binom{j + l}{l − u}\binom{n − j}{j + l}\binom{n}{j + l}^{t+1}F (n, j + l) (Eq. (9))

= ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − 2j − l}{u}\binom{j + l}{j + u}\binom{n − j}{n − 2j − l}\binom{n}{j + l}\binom{n}{j + l}^{t}F (n, j + l) ( by symmetry)

= ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{n − 2j − l}\binom{n − 2j − l}{u}\binom{n}{j + l}\binom{j + l}{j + u}\binom{n}{j + l}^{t}F (n, j + l) (perm.) (14)

We apply Eq. (7) twice. It follows that

\binom{n − j}{n − 2j − l}\binom{n − 2j − l}{u} = \binom{n − j}{u}\binom{n − j − u}{n − 2j − l − u} and  (15)
\binom{n}{j + l}\binom{j + l}{j + u} = \binom{n}{j + u}\binom{n − j − u}{l − u}.  (16)

If we use Eqns. (15) and (16), Eq. (14) becomes

D_{S}(n, j, t + 1)

= ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{u}\binom{n − j − u}{n − 2j − l − u}\binom{n}{j + u}\binom{n − j − u}{l − u}\binom{n}{j + l}^{t}F (n, j + l). (17)

We now exchange the order of summation. If we take Inequalities (12) and (13) into consideration along with the symmetry \binom{n−j−u}{n−2j−l−u} = \binom{n−j−u}{j+l}, Eq. (17) becomes

D_{S}(n, j, t + 1)

= ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} ∑_{l=u}^{n−2j−u} \binom{n − j}{u}\binom{n − j − u}{n − 2j − l − u}\binom{n}{j + u}\binom{n − j − u}{l − u}\binom{n}{j + l}^{t}F (n, j + l) (Ineq.)

= ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} ∑_{l=u}^{n−2j−u} \binom{n − j}{u}\binom{n − j − u}{j + l}\binom{n}{j + u}\binom{n − j − u}{l − u}\binom{n}{j + l}^{t}F (n, j + l) (symmetry)

= ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n}{j + u}\binom{n − j}{u} ∑_{l=u}^{n−2j−u} \binom{n − j − u}{l − u}\binom{n − j − u}{j + l}\binom{n}{j + l}^{t}F (n, j + l). (18)

We substitute u + v for l. From the Inequality (12), we know that 0 ≤ j + u ≤ ⌊\frac{n}{2}⌋. Then Eq. (18) becomes as follows:

∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n}{j + u}\binom{n − j}{u} ∑_{v=0}^{n−2j−2u} \binom{n − j − u}{v}\binom{n − j − u}{j + u + v}\binom{n}{j + u + v}^{t}F (n, j + u + v)

= ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n}{j + u}\binom{n − j}{u}D_{S}(n, j + u, t) (by Eq. (2)).  (19)

From Eqns. (18) and (19), we obtain

D_{S}(n, j, t + 1) = ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n}{j + u}\binom{n − j}{u}D_{S}(n, j + u, t).

This completes the proof of Theorem 2.

4 Proof of Theorem 3

The proof of Theorem 3 is similar to the proof of Theorem 2. We use the same three binomial identities as in the previous proof.

Proof. By Definition 1 and Eq. (2), we know that

D_{S}(n, j, 0) = ∑_{l=0}^{n−2j} \binom{n − j}{l}\binom{n − j}{j + l}F (n, j + l).  (20)

We use Eq. (9) and the symmetry \binom{j+l}{l−u} = \binom{j+l}{j+u}. Again, Inequalities (10), (11), (12), and (13) hold.

Then Eq. (20) becomes as follows:

D_{S}(n, j, 0) = ∑_{l=0}^{n−2j} (∑_{u=0}^{l} \binom{n − 2j − l}{u}\binom{j + l}{l − u}) \binom{n − j}{j + l}F (n, j + l) (by Eq. (9))

= ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{j + l}\binom{j + l}{l − u}\binom{n − 2j − l}{u}F (n, j + l) (permutation)

= ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{j + l}\binom{j + l}{j + u}\binom{n − 2j − l}{u}F (n, j + l) (by symmetry). (21)

By Eq. (7) and the symmetry \binom{n−2j−u}{l−u} = \binom{n−2j−u}{n−2j−l} , it follows that

\binom{n − j}{j + l}\binom{j + l}{j + u} = \binom{n − j}{j + u}\binom{n − 2j − u}{n − 2j − l}.  (22)

If we use Eq. (22), Eq. (21) becomes

D_{S}(n, j, 0) = ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{j + u}\binom{n − 2j − u}{n − 2j − l}\binom{n − 2j − l}{u}F (n, j + l).  (23)

By Eq. (7) and the symmetry \binom{n−2j−2u}{n−2j−l−u} = \binom{n−2j−2u}{l−u}, it follows that

\binom{n − 2j − u}{n − 2j − l}\binom{n − 2j − l}{u} = \binom{n − 2j − u}{u}\binom{n − 2j − 2u}{l − u}.  (24)

If we use Eq. (24), Eq. (23) becomes

D_{S}(n, j, 0) = ∑_{l=0}^{n−2j} ∑_{u=0}^{l} \binom{n − j}{j + u}\binom{n − 2j − u}{u}\binom{n − 2j − 2u}{l − u}F (n, j + l).  (25)

We exchange the order of summation. If we take Inequalities (12) and (13) into consideration, Eq. (25) becomes as follows:

D_{S}(n, j, 0) = ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} ∑_{l=u}^{n−2j−u} \binom{n − j}{j + u}\binom{n − 2j − u}{u}\binom{n − 2j − 2u}{l − u}F (n, j + l) (Ineq.)

= ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n − j}{j + u}\binom{n − 2j − u}{u} ∑_{l=u}^{n−2j−u} \binom{n − 2j − 2u}{l − u}F (n, j + l).  (26)

We substitute l by u + v. Then Eq. (26) becomes

D_{S}(n, j, 0) = ∑_{u=0}^{⌊ \frac{n−2j}{2} ⌋} \binom{n − j}{j + u}\binom{n − 2j − u}{u} ∑_{v=0}^{n−2j−2u} \binom{n − 2j − 2u}{v}F (n, j + u + v). (27)

Eq. (27) completes the proof of Theorem 3.

5 How Does This Method Work?

In one particular situation, Theorem 2 implies a simple consequence which is important for us.

Let n be a fixed non-negative integer. Let t_{0} be a non-negative integer, and let j be an arbitrary integer in the range 0 ≤ j ≤ ⌊\frac{n}{2}⌋. Suppose that q = q(n) is a positive integer which divides D_{S}(n, j, t_{0}) sums for all j in the given range. We want q to be as large as possible. Then it can be shown, by Theorem 2, that q divides D_{S}(n, j, t_{0} + 1) for all j in the given range.

By induction, it follows that q divides D_{S}(n, j, t) for all t such that t ≥ t_{0} and for all j in the given range. By Eq. (3), it follows that q divides S(n, t + 2) for all t such that t ≥ t_{0}. This is exactly how this method works.

6 Two applications for non-negative sums

We give two applications of our method of D sums for non-negative sums with absolute values.

Let n and j be non-negative integers such that j ≤ n, and let t and m be positive integers. First, we consider the sum S_{1}(2n, m) = ∑_{k=0}^{2n} \binom{2n}{k}^{m}|n − k|. It is known [4, p. 3] that

∑_{k=0}^{2n} \binom{2n}{k}|n − k| = n\binom{2n}{n}.  (28)

Therefore, we have

S_{1}(2n, 1) = n\binom{2n}{n}.

We establish the following two lemmas: Lemma 4.

D_{S_{1}}(2n, j, 0) = n\binom{2n − j}{n}\binom{2n − j − 1}{n} for 0 ≤ j ≤ n.

Lemma 5.

D_{S_{1}}(2n, j, 1) = n\binom{2n}{n} ∑_{u=0}^{n−1−j} \binom{n}{j + u}\binom{2n − j}{u}\binom{2n − j − u − 1}{n} for 0 ≤ j ≤ n.

In particular, Lemmas 4 and 5 imply the following formulas:

S_{1}(2n, 2) = n\binom{2n}{n}\binom{2n − 1}{n},  (29)
S_{1}(2n, 3) = n\binom{2n}{n} ∑_{u=0}^{n−1} \binom{n}{u}\binom{2n}{u}\binom{2n − u − 1}{n}.  (30)

If n is a positive integer, Lemma 5 suggests setting q_{1}(2n) = n\binom{2n}{n}.

We establish the following theorem: Theorem 6. Let n be a positive integer. The sum D_{S_{1}}(2n, j, t) is divisible by n\binom{2n}{n} for all positive integers t and all integers j such that 0 ≤ j ≤ n.

We conclude that Corollary 7. Let n be a positive integer. The sum S_{1}(2n, m) is divisible by n\binom{2n}{n} for all positive integers m .

Next, we consider the sum S_{2}(2n + 1, m) = ∑_{k=0}^{2n+1} \binom{2n+1}{k}^{m} |\frac{2n+1}{2} − k|. It is known [4, p. 3] that

∑_{k=0}^{2n+1} \binom{2n + 1}{k} |\frac{2n + 1}{2} − k| = (2n + 1)\binom{2n}{n}.  (31)

Therefore, we have

S_{2}(2n + 1, 1) = (2n + 1)\binom{2n}{n}.

We establish the following two lemmas: Lemma 8.

D_{S_{2}}(2n + 1, j, 0) = (2n + 1 − j)\binom{2n − j}{n}^{2} for 0 ≤ j ≤ n.

Lemma 9.

D_{S_{2}}(2n + 1, j, 1) = (2n + 1)\binom{2n}{n} ∑_{u=0}^{n−j} \binom{n}{j + u}\binom{2n + 1 − j}{u}\binom{2n − j − u}{n} for 0 ≤ j ≤ n.

In particular, Lemmas 8 and 9 imply the following formulas:

S_{2}(2n + 1, 2) = (2n + 1)\binom{2n}{n}^{2},  (32)
S_{2}(2n + 1, 3) = (2n + 1)\binom{2n}{n} ∑_{u=0}^{n} \binom{n}{u}\binom{2n + 1}{u}\binom{2n − u}{n}.  (33)

Lemma 9 suggests setting q_{2}(2n + 1) = (2n + 1)\binom{2n}{n}. We establish the following theorem:

Theorem 10. Let n be a non-negative integer. The sum D_{S_{2}}(2n + 1, j, t) is divisible by (2n + 1)\binom{2n}{n} for all positive integers t and all integers j such that 0 ≤ j ≤ n.

We conclude that

Corollary 11. Let n be a non-negative integer. Then the sum S_{2}(2n + 1, m) is divisible by (2n + 1)\binom{2n}{n} for all positive integers m.

Due to clarity and brevity of this paper, we prove only Lemma 4, Lemma 5, Theorem 6, and Corollary 7. Proofs of Lemma 8, Lemma 9, Theorem 10, and Corollary 11 are similar to proofs of Lemma 4, Lemma 5, Theorem 6, and Corollary 7, respectively. Therefore, proofs of Lemma 8, Lemma 9, Theorem 10, and Corollary 11 are omitted.

7 Details of Theorem 6

7.1 Motivation

The Identity (28) has a long history [6, Introduction]. It was a problem in the 1974 Putnam competition [2, Problem A4]. Best [3, Thm. 3] considered this identity in an application to Hadamard matrices. See also [14, Thm. 15.2], [1, Chapter 2.5], and [7].

Tuenter [22] considered centered binomial sums of the form

S_{r}(n) = ∑_{k=0}^{2n} \binom{2n}{k}|n − k|^{r},

which are a generalization of the Identity (28).

Brent [4] considered binomial sums

U_{r}(n) = ∑_{k=0}^{n} \binom{n}{k}|n/2 − k|^{r},

which are a generalization of Tuenter’s sums. Brent gave recurrence relations for U_{r}(n), where he used facts U_{1}(2n) = n\binom{2n}{n} and U_{1}(2n + 1) = (2n + 1)\binom{2n}{n}. Brent cited a solution by Hillman [20] of the Putnam problem 35-A4. Hillman gave a closed form for U_{1}(n), i.e., U_{1}(n) = n\binom{n−1}{⌊ \frac{n}{2} ⌋}.

Identities (28) and (31) are connected with the following binomial identity [5, 6]:

∑_{i=−n}^{n} ∑_{j=−n}^{n} \binom{2n}{n + i}\binom{2n}{n + j}|i^{2} − j^{2}| = 2n^{2}\binom{2n}{n}^{2}.  (34)

The Identity (34) can be used in proofs of lower bounds for the Hadamard maximal determinant problem.

We consider the sum S_{1}(2n, m) as another generalization of the Identity (28). Similarly, we consider the sum S_{2}(2n + 1, m) as another generalization of the Identity (31).

7.2 Proof of Lemma 4

Let n be a non-negative integer, and let m be a positive integer. We defined the sum S_{1}(2n, m) as

S_{1}(2n, m) = ∑_{k=0}^{2n} \binom{2n}{k}^{m}|n − k|.  (35)

Obviously, the sum S_{1}(2n, m) is an instance of the sum (1), where

F_{1}(2n, k) = |n − k|.  (36)

Let j be a non-negative integer such that j ≤ n.

The proof of Lemma 4 is based on Theorem 3 and Eq. (28).

Proof. By Theorem 3, we have

D_{S_{1}}(2n, j, 0) = ∑_{u=0}^{⌊ \frac{2n−2j}{2} ⌋} \binom{2n − j}{j + u}\binom{2n − 2j − u}{u} ∑_{v=0}^{2n−2j−2u} \binom{2n − 2j − 2u}{v}F_{1}(2n, j + u + v)

= ∑_{u=0}^{n−j} \binom{2n − j}{j + u}\binom{2n − 2j − u}{u} ∑_{v=0}^{2n−2j−2u} \binom{2n − 2j − 2u}{v}F_{1}(2n, j + u + v)  (37)

= ∑_{u=0}^{n−j} \binom{2n − j}{j + u}\binom{2n − 2j − u}{u} ∑_{v=0}^{2n−2j−2u} \binom{2n − 2j − 2u}{v}|n − j − u − v|.  (38)

Note that in Eq. (37), we used Eq. (36).

By Eq. (28), we obtain

∑_{v=0}^{2n−2j−2u} \binom{2n − 2j − 2u}{v}|n − j − u − v| = (n − j − u)\binom{2(n − j − u)}{n − j − u}.  (39)

If we use Eq. (39), the symmetry \binom{2n−j}{j+u} = \binom{2n−j}{2n−2j−u}, and the symmetry \binom{2n−2j−u}{u} = \binom{2n−2j−u}{2n−2j−2u}, Eq. (38) becomes as follows:

∑_{u=0}^{n−j} \binom{2n − j}{j + u}\binom{2n − 2j − u}{u}(n − j − u)\binom{2(n − j − u)}{n − j − u} (by Eq. (39))  (40)
= ∑_{u=0}^{n−1−j} \binom{2n − j}{2n − 2j − u}\binom{2n − 2j − u}{2n − 2j − 2u}\binom{2n − 2j − 2u}{n − j − u}(n − j − u) (symmetry). (41)

Note that the last term of the sum in Eq. (40) is equal to zero. Furthermore, we have

\binom{2n − 2j − u}{2n − 2j − 2u}\binom{2n − 2j − 2u}{n − j − u} = \binom{2n − 2j − u}{n − j − u}\binom{n − j}{n − j − u} (by Eq. (7))

= \binom{2n − 2j − u}{n − j}\binom{n − j}{u} (by symmetry).

Therefore, we obtain

\binom{2n − 2j − u}{2n − 2j − 2u}\binom{2n − 2j − 2u}{n − j − u} = \binom{2n − 2j − u}{n − j}\binom{n − j}{u}.  (42)

If we use Eq. (42), Eq. (41) becomes

D_{S_{1}}(2n, j, 0) = ∑_{u=0}^{n−1−j} \binom{2n − j}{2n − 2j − u}\binom{2n − 2j − u}{n − j}\binom{n − j}{u}(n − j − u).  (43)

By Eq. (7) and the symmetry \binom{2n−j}{n−j} = \binom{2n−j}{n}, it follows that

\binom{2n − j}{2n − 2j − u}\binom{2n − 2j − u}{n − j} = \binom{2n − j}{n}\binom{n}{n − j − u}.  (44)

If we use Eq. (44), Eq. (43) becomes as follows:

D_{S_{1}}(2n, j, 0) = ∑_{u=0}^{n−1−j} \binom{2n − j}{n}\binom{n}{n − j − u}\binom{n − j}{u}(n − j − u) (by Eq. (44))
= \binom{2n − j}{n} ∑_{u=0}^{n−1−j} \binom{n − j}{u}(n − j − u)\binom{n}{n − j − u} (permutation) (45)

It is well-known that

k\binom{n}{k} = n\binom{n − 1}{k − 1}.  (46)

By Eq. (46), we get

(n − j − u)\binom{n}{n − j − u} = n\binom{n − 1}{n − 1 − j − u}.  (47)

If we use Eq. (47), Eq. (45) becomes

D_{S_{1}}(2n, j, 0) = n\binom{2n − j}{n} ∑_{u=0}^{n−1−j} \binom{n − j}{u}\binom{n − 1}{n − 1 − j − u}.  (48)

By Eq. (6) and the symmetry \binom{2n−1−j}{n−1−j} = \binom{2n−1−j}{n}, we get

∑_{u=0}^{n−1−j} \binom{n − j}{u}\binom{n − 1}{n − 1 − j − u} = \binom{2n − 1 − j}{n}.  (49)

Finally, if we put Eq. (49) in Eq. (48), we obtain

D_{S_{1}}(2n, j, 0) = n\binom{2n − j}{n}\binom{2n − 1 − j}{n}.

This completes the proof of Lemma 4.

7.3 Proof of Lemma 5

This proof is based on Theorem 2 and Lemma 4. Proof. By Theorem 2, we have

D_{S_{1}}(2n, j, 1) = ∑_{u=0}^{⌊ \frac{2n−2j}{2} ⌋} \binom{2n}{j + u}\binom{2n − j}{u}D_{S_{1}}(2n, j + u, 0) (by Theorem 2)
= ∑_{u=0}^{n−j} \binom{2n}{j + u}\binom{2n − j}{u}D_{S_{1}}(2n, j + u, 0).  (50)

By Lemma 4, we get

D_{S_{1}}(2n, j + u, 0) = n\binom{2n − j − u}{n}\binom{2n − 1 − j − u}{n}.  (51)

Then Eq. (50) becomes as follows:

D_{S_{1}}(2n, j, 1) = ∑_{u=0}^{n−j} \binom{2n}{j + u}\binom{2n − j}{u}n\binom{2n − j − u}{n}\binom{2n − 1 − j − u}{n} (by Eq. (51))

= n ∑_{u=0}^{n−j} \binom{2n}{j + u}\binom{2n − j − u}{n}\binom{2n − j}{u}\binom{2n − 1 − j − u}{n} (permutation)

= n ∑_{u=0}^{n−j} \binom{2n}{2n − j − u}\binom{2n − j − u}{n}\binom{2n − j}{u}\binom{2n − 1 − j − u}{n}.  (52)

Note that we used the symmetry \binom{2n}{j+u} = \binom{2n}{2n−j−u} in Eq. (52). Furthermore, the last term in Eq. (52) equals zero.

It is readily verified that

\binom{2n}{2n − j − u}\binom{2n − j − u}{n} = \binom{2n}{n}\binom{n}{j + u}.  (53)

Then Eq. (52) becomes as follows:

D_{S_{1}}(2n, j, 1) = n ∑_{u=0}^{n−j} \binom{2n}{n}\binom{n}{j + u}\binom{2n − j}{u}\binom{2n − 1 − j − u}{n} (by Eq. (53))

= n\binom{2n}{n} ∑_{u=0}^{n−1−j} \binom{n}{j + u}\binom{2n − j}{u}\binom{2n − 1 − j − u}{n}.  (54)

Eq. (54) implies that

D_{S_{1}}(2n, j, 1) = n\binom{2n}{n} ∑_{u=0}^{n−1−j} \binom{n}{j + u}\binom{2n − j}{u}\binom{2n − 1 − j − u}{n}.

This completes the proof of Lemma 5.

7.4 Proof of Theorem 6

We assume that n is a fixed positive integer and j is a fixed non-negative integer such that j ≤ n. We use induction on t.

Proof. When t = 1, D_{S_{1}}(2n, j, t) is divisible by n\binom{2n}{n}. This follows from Lemma 5. The base case of induction is confirmed.

We now assume that D_{S_{1}}(2n, k, t) is divisible by n\binom{2n}{n} for all non-negative integers k such that k ≤ n.

What happens with D_{S_{1}}(2n, j, t + 1)? By Theorem 2, we have

D_{S_{1}}(2n, j, t + 1) = ∑_{u=0}^{n−j} \binom{2n}{j + u}\binom{2n − j}{u}D_{S_{1}}(2n, j + u, t).  (55)

Obviously, 0 ≤ u + j ≤ n for 0 ≤ u ≤ n − j. By induction hypothesis, D_{S_{1}}(2n, j + u, t) is divisible by n\binom{2n}{n}. By Eq. (55), it follows that D_{S_{1}}(2n, j, t + 1) is divisible by n\binom{2n}{n}. By induction, Theorem 6 follows.

7.5 Proof of Corollary 7

Proof. By Eq. (28), it follows that S_{1}(2n, 1) is divisible by n\binom{2n}{n}.

Setting j = 0 in Lemma 4, we obtain Eq. (29). By Eq. (29), it follows that S_{1}(2n, 2) is divisible by n\binom{2n}{n}.

Let m ≥ 3. By Eq. (3), we know that S_{1}(2n, m) = D_{S_{1}}(2n, 0, m − 2). Since m − 2 ≥ 1, we can apply Theorem 6. By Theorem 6, D_{S_{1}}(2n, 0, m − 2) is divisible by n\binom{2n}{n}. By Eq. (3), S_{1}(2n, m) is divisible by n\binom{2n}{n} for m ≥ 3. This completes the proof of Corollary 7.

Remark 12. Note that

S_{1}(2n, 2) = \frac{n}{2}\binom{2n}{n}^{2}.  (56)

Setting j = 0 in Lemma 5 and using Eq. (3), we obtain Eq. (30).

8 The third application for the alternating sum

We give a sketch of the proof of Calkin’s result [9, Thm. 1] by using our method of D sums. We use the well-known identity [16, Eq. (1.25), p. 4]

∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k} = \begin{cases}0, & if n > 0; \\ 1, & if n = 0, \end{cases}  (57)

where n is a non-negative integer. Eq. (57) plays the same role as Eq. (28) in the proof of Theorem 6.

Let n be a non-negative integer and let m be a positive integer. Let S_{3}(2n, m) denote the sum ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{m}. Obviously, the sum S_{3}(2n, m) is an instance of the sum (1), where F_{3}(2n, k) = (−1)^{k}. By Eq. (57), we conclude that S_{3}(2n, 1) is divisible by \binom{2n}{n}.

Furthermore, it is known

S_{3}(2n, 2) = (−1)^{n}\binom{2n}{n},  (Kummer’s formula)
S_{3}(2n, 3) = (−1)^{n}\binom{2n}{n}\binom{3n}{2n}.  (Dixon’s formula (4))

Therefore, it follows that S_{3}(2n, m) is divisible by \binom{2n}{n} for 1 ≤ m ≤ 3.

By Eq. (57) and Theorem 3, it can be proved that

D_{S_{3}}(2n, j, 0) = (−1)^{n}\binom{2n − j}{n} for 0 ≤ j ≤ n.  (58)

By Theorem 2 and Eq. (58), it can be shown that

D_{S_{3}}(2n, j, 1) = (−1)^{n}\binom{2n}{n}\binom{3n − j}{2n} for 0 ≤ j ≤ n.  (59)

Setting j = 0 in Eq. (59) and using Eq. (3), we obtain Eq. (4). Hence, the method of D sums gives a proof of Eq. (4).

Furthermore, Eq. (59) suggests setting q_{3}(2n) = \binom{2n}{n}.

By Theorem 2, it can be shown that D_{S_{3}}(2n, j, t) is divisible by \binom{2n}{n} for all positive integers t and all integers j such that 0 ≤ j ≤ n.

Let m ≥ 4. By Eq. (3), we know that S_{3}(2n, m) = D_{S_{3}}(2n, 0, m − 2). Since m − 2 ≥ 2, the sum D_{S_{3}}(2n, 0, m − 2) is divisible by \binom{2n}{n}. By Eq. (3), S_{3}(2n, m) is divisible by \binom{2n}{n} for m ≥ 4.

Finally, we can conclude that S_{3}(2n, m) is divisible by \binom{2n}{n} for all non-negative integers n and all positive integers m. This proves Calkin’s result.

Remark 13. By using asymptotic methods, Bruijn [8] has proved that no closed form exists for S_{3}(n, m) when m ≥ 4. However, there are formulas for S_{3}(2n, 4) and S_{3}(2n, 5) [19, Eq. (5.13), Eq. (5.12)]. Both formulas can be derived by using the method of D sums.

9 Acknowledgments

I would like to thank Professor Duško Jojić. Also I would like to thank the referee for a very careful reading of this manuscript and useful suggestions.

References

[1] N. Alon and J. H. Spencer, The Probabilistic Method, 3rd edn. , Wiley 2008.

[2] Anonymous, Putnam Competition, 1974, available at https://mks.mff.cuni.cz/

    kalva/putnam/putn74.html.

[3] M. R. Best, The excess of a Hadamard matrix, Indag. Math. (N.S.) 39 (1977), 357–361.

[4] R. P. Brent, Generalising Tuenter’s binomial sums, J. Integer Sequences 18 (2015), Article 15.3.2.

[5] R. P. Brent, H. Ohtsuka, J. H. Osborn, and H. Prodinger, Some binomial sums involving absolute values, J. Integer Sequences 19 (2016), Article 16.3.7.

[6] R. P. Brent and J. H. Osborn, Note on a double binomial sum relevant to the Hadamard maximal determinant problem, preprint, 2013. Available at https://arxiv.org/abs/

    1309.2795.

[7] T. A. Brown and J. H. Spencer, Minimization of ±1 matrices under line shifts, Colloq. Math. 23 (1971), 165-171. Erratum, p. 177.

[8] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover Publications, 1981.

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

[10] H. Q. Cao and H. Pan, Factors of alternating binomial sums, Adv. in Appl. Math. 45 (2010), 96–107.

[11] A. C. Dixon, On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem, Messenger of Mathematics 20 (1891), 79–80.

[12] A. C. Dixon, Summation of a certain series, Proc. London Math. Soc. 35 (1) (1903), 285–289.

[13] S. B. Ekhad, A very short proof of Dixon’s theorem, J. Combin. Theory Ser. A 54 (1990), 141–142.

[14] P. Erdős and J. Spencer, Probabilistic Methods In Combinatorics, Academic Press, 1974.

[15] I. Gessel and D. Stanton, Short proofs of Saalschütz’s and Dixon’s theorems, J. Combin. Theory Ser. A 38 (1985), 87–90.

[16] H. W. Gould, Combinatorial Identities, published by the author, revised edition, 1972.

[17] V. J. W. Guo, A simple proof of Dixon’s identity, Discrete Math. 268 (2003), 309–310.

[18] V. J. W. Guo, F. Jouhet, and J. Zeng, Factors of alternating sums of products of binomial and q-binomial coefficients, Acta Arith. 127 (2007), 17-31.

[19] V. J. W. Guo, F. Jouhet, and J. Zeng, New finite Rogers-Ramanujan identities, Ramanujan J. 19 (2009), 247–266.

[20] A. P. Hillman, The William Lowell Putnam mathematical competition, Amer. Math. Monthly 82 (1975), 905–912.

[21] J. Mikić, A Proof of Dixon’s Identity, J. Integer Sequences 19 (2016), Article 16.5.3.

[22] H. J. H. Tuenter, Walking into an absolute sum, Fibonacci Quart. 40 (2002), 175–180.

2010 Mathematics Subject Classification: Primary 05A10 ; Secondary 05A19. Keywords: Method of D sums, binomial sum with absolute values, alternating binomial sum, recurrence equation, Dixon’s formula, Hadamard maximal determinant problem.

(Concerned with sequence \underline{A006480}.)

Received May 30 2018; revised versions received July 5 2018; September 29 2018; October 1 2018; October 7 2018. Published in Journal of Integer Sequences, November 25 2018.

Return to Journal of Integer Sequences home page.