On Certain Sums Divisible by the Central Binomial Coefficient

Jovan Mikić J.U. SŠC “Jovan Cvijić” 74480 Modriča Republic of Srpska

                   jnmikic@gmail.com

Abstract

We prove that some sums, which arise as generalizations of known binomial coefficient identities, are divisible by the central binomial coefficient. A new method is used. In particular, we show that an alternating sum concerning the product of a power of a binomial coefficient with two Catalan numbers is always divisible by the central binomial coefficient.

1 Introduction

Let n be a non-negative integer and let m be a positive integer. Let C_{n} = \frac{1}{n+1} \binom{2n}{n} denote the nth Catalan number.

In this paper, we consider the following four binomial sums:

P (n, m) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}^{m}\binom{2k}{k}\binom{2n − 2k}{n − k},  (1)
Q(n, m) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}^{m}\binom{2k}{k}\binom{2n − 2k}{n − k}(n − k),  (2)
R(n, m) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}^{m}C_{k} \binom{2n − 2k}{n − k},  (3)
T (n, m) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}^{m}C_{k} C_{n−k}.  (4)

For m = 1, all four sums (1), (2), (3), and (4) reduce to interesting combinatorial identities. For example, it is well-known that [9, Example 3.6.2, p. 45]

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

By Eq. (5), it follows that P (2n, 1) = \binom{2n}{n}^{2}.

Recently, the following two binomial coefficient identities involving the Catalan numbers were discovered [8]:

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}C_{k} \binom{2n − 2k}{n − k} = \binom{n}{⌊\frac{n}{2}⌋}^{2},  (6)

∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}C_{k} C_{2n−k} = C_{n}\binom{2n}{n}.  (7)

In this paper we present, among other results, two generalizations of Eqns. (6) and (7). See Remark 23. By Eqns. (6) and (7), it follows that R(n, 1) = \binom{n}{⌊ \frac{n}{2} ⌋}^{2} and T (2n, 1) = C_{n}\binom{2n}{n}. Our main results are as follows:

Theorem 1. The sum P (2n, m) is divisible by \binom{2n}{n} for all non-negative integers n and for all positive integers m.

Theorem 2. The sum Q(2n − 1, m) is divisible by 2(2n − 1)\binom{2(n−1)}{n−1} for all positive integers n and m.

Theorem 3. The sum R(2n, m) is divisible by (n + 1)\binom{2n}{n} for all non-negative integers n and for all positive integers m.

Corollary 4. The sum T (2n, m) is divisible by \binom{2n}{n} for all non-negative integers n and for all positive integers m.

Theorem 5. The sum R(2n − 1, m) is divisible by \binom{2n−1}{n} for all positive integers n and m.

For proving our main results, we use a method we call the “method of D sums”.

Definition 6. Let n, j, and t be non-negative integers such that j ≤ ⌊\frac{n}{2}⌋, and let m be a positive integer. Let S(n, m) = ∑_{k=0}^{n} \binom{n}{k}^{m}F (n, k), where F (n, k) is an integer-valued function that depends only on n and k. Then the D sums for S(n, m) are

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).  (8)

First, note that all four sums (1), (2), (3), and (4) are instances of S(n, m). For m ≥ 2, by Eq. (8), it follows that

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

Furthermore, D sums satisfy the following two recurrence relations [6, Thm. 2, Thm. 3, p. 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),  (10)

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). (11)

The idea is to calculate the D sums for (1), (2), (3), and (4) by using Relations 10 and 11. We show that their D sums have interesting divisibility properties. For example, we show that D_{P} (2n, j, 0) is divisible by \binom{2n}{n} for all non-negative integers j and n such that j ≤ n. Surprisingly, this result is sufficient to prove Theorem 1 for m ≥ 2. Namely, then by Relation 10 and induction, it can be shown that all D_{P} (2n, j, t) are divisible by \binom{2n}{n}. By Relation 9, it follows that P (2n, m) is divisible by \binom{2n}{n} for all m ≥ 2. See [6, Section 5].

To calculate the sum D_{P} (2n, j, 0), we derive the following binomial coefficient identity:

∑_{k=t}^{2n−t}(−1)^{k}\binom{2n − 2t}{k − t}\binom{2k}{k}\binom{4n − 2k}{2n − k} = (−1)^{t} \begin{matrix}\binom{2n}{n} & \binom{2t}{t} & \binom{2(n−t)}{n−t} \\ ( & {2n−t \atop t} & ) \end{matrix},  (12)

where n and t are non-negative integers such that t ≤ n. For t = 0, Eq. (12) becomes Eq. (5). Therefore, we can see Eq. (12) as a generalization of Eq. (5).

2 Motivation

The first application of D sums [6, Section 8] was for proving Calkin’s result [1, Thm. 1]. In 1998, Calkin 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.

In 2007, Guo, Jouhet, and Zeng proved, among other things, two generalizations of Calkin’s result [4, Thm. 1.2, Thm. 1.3, p. 2]. As a special case of [4, Thm. 1.2, p. 2], they gave a direct generalization of Calkin’s result [4, Thm. 4.1, p. 8]. Moreover, this generalization implies that the sum D_{S_{3}} [6, Section 8] is divisible by \binom{2n}{n} and \binom{2n−j}{n} for t ≥ 1. Take m = t + 2, n_{1} = n_{2} = ⋯ = n_{t+1} = n, and n_{t+2} = n − j in [4, Thm. 4.1, p. 8].

Since the sum in [4, Thm. 4.1, p. 8] is not instance of S(n, m) from our Definition 6, it is clear that D sums cannot prove this direct generalization by Guo, Jouhet, and Zeng. Therefore, method of D sums proves the smallest generalization of Calkin’s result.

In this paper, we show how the method of D sums works on harder sums, such as our four sums (1), (2), (3), and (4). Note that our main results are not consequences of [4, Thm. 1.2, Thm. 1.3, Thm. 4.1.].

Let S, F, and D_{S} be sums according to Definition 6. The main obstacle is to calculate the sum D_{S}(n, j, 0). In order to make Relation 11 more readable, we introduce the following definition.

Definition 7. Let n and t be non-negative integers such that t ≤ ⌊\frac{n}{2}⌋. Then S_{t}(n) denotes

∑_{k=t}^{n−t} \binom{n − 2t}{k − t}F (n, k).  (13)

Obviously, for t = 0, it follows that S_{0}(n) = S(n, 1). Therefore, a sum S_{t}(n) can be viewed as a generalization of a sum S(n, 1). Furthermore, by substitution k = u + j + v, the inner sum of the right-side of (11) becomes

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

It is readily verified [5, Eq. (1.4), p. 5] that \binom{n−j}{j+u}\binom{n−2j−u}{u} = \binom{n−j}{u}\binom{n−j−u}{j+u}. By using this fact and Eq. (14), Relation 11 becomes

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

From now on, for calculating D_{S}(n, j, 0) sum, we use Eq. (15) instead of Relation 11.

To find a sum D_{S}(n, j, 0), we first need to find the appropriate S_{t}(n). For example, let us consider our first sum P (2n, m). We want to find D_{P} (2n, j, 0) sum, where j is a non-negative integer such that j ≤ n. Let t be a non-negative integer such that t ≤ n. Then what is P_{t}(2n)? By Definitions (6) and (7), P_{t}(2n) is equal to the left side of Eq. (12). If Eq. (12) holds, then it follows that

P_{t}(2n) = (−1)^{t} \begin{matrix}\binom{2n}{n} & \binom{2t}{t} & \binom{2(n−t)}{n−t} \\ ( & {2n−t \atop t} & ) \end{matrix}.

Note that formula above is our Lemma 10. Therefore, Lemma 10 is a restatement of Eq. (12). Also we want to find the sums Q_{t}(2n − 1), R_{t}(2n), R_{t}(2n − 1), and T_{t}(2n).

This paper consists of two main parts. In the first part, we derive formulas for P_{t}(2n), Q_{t}(2n − 1), R_{t}(2n), R_{t}(2n − 1) and T_{t}(2n) sums. We use recurrences and telescoping. Interestingly, Q_{t}(2n), R_{t}(n), and T_{t}(n) are auxiliary sums for the sum P_{t}(2n). See [7]. Therefore, if we find the first sum P_{t}(2n), then the others follow by using recurrence relations. Note that we use telescoping only for the first sum P_{t}(2n).

In the second part, we apply the method of D sums by using Relations 10, 15, and 9. The rest of the paper is structured as follows: In Section 3, we begin with some prelim-

inary results for Eqs. (1), (2), (3), and (4). Also, we give some preliminary results for the sums P_{t}(n), Q_{t}(n), R_{t}(n) and T_{t}(n). In Section 4, we present formulas for the sums P_{t}(2n), Q_{t}(2n − 1), R_{t}(2n), R_{t}(2n − 1), and T_{t}(2n). Also we give recurrence relations between these sums. In Section 5, we prove most of the results from Section 4. In Section 6, we start with the proof of Theorem (1) by using the method of D sums and Lemma 10. Then we prove Theorem 3 and Corollary 4. For brevity and clarity, we omit proofs of Theorems 2 and 5. Namely, the proofs of Theorems 2 and 5 are similar to proofs of Theorems 1 and 3, respectively.

3 Some preliminary results

We start with some preliminary results for Eqs. (1), (2), (3), and (4) sums.

Lemma 8. Let n be a non-negative integer, and let m be a positive integer. Then we have

P (2n + 1, m) = 0,  (16)
Q(2n, m) = nP (2n, m),  (17)
T (2n + 1, m) = 0,  (18)
T (2n, m) = \frac{1}{n + 1}R(2n, m).  (19)

Furthermore, we give similar results for the sums P_{t}(n), Q_{t}(n), R_{t}(n) and T_{t}(n).

Lemma 9. Let n be a non-negative integer, and let t be a non-negative integer such that t ≤ ⌊\frac{n}{2}⌋. Then we have

P_{t}(2n + 1) = 0,  (20)
Q_{t}(2n) = nP_{t}(2n),  (21)
T_{t}(2n + 1) = 0,  (22)
T_{t}(2n) = \frac{1}{n + 1}R_{t}(2n).  (23)

We prove only Lemma 8. The proof of Lemma 9 is similar to the proof of Lemma 8. Therefore, the proof of Lemma 9 is omitted.

3.1 Proof of Lemma 8

Proof. Changing k to n − k in Eq. (1), it follows that P (n, m) = (−1)^{n}P (n, m). If n is odd, then it must be P (n, m) = −P (n, m). This is equivalent to P (n, m) = 0 for an odd n. The Eq. (16) follows, as desired.

Similarly, changing k to n − k in Eq. (4), it follows that T (n, m) = (−1)^{n}T (n, m). If n is odd, then it must be T (n, m) = −T (n, m) which is equivalent to T (n, m) = 0. This proves Eq. (18).

By Eq. (2), we know that

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

Changing k to 2n − k, the last equation above becomes

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

By adding these two equations, Eq. (17) follows.

Let us now prove Eq. (19). By Eq. (3), we know that

R(2n, m) = ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{m}C_{k}\binom{4n − 2k}{2n − k}.

Changing k to 2n − k, the last equation above becomes

R(2n, m) = ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}^{m}C_{2n−k}\binom{2k}{k}.

By adding the last two equations above and using the fact [8, Eq. (18), p. 8] C_{k}\binom{4n−2k}{2n−k} + C_{2n−k}\binom{2k}{k} = 2(n + 1)C_{k} C_{2n−k} , Eq. (19) follows.

4 Main lemmas, propositions and corollaries

Let n and t be non-negative integers such that t ≤ ⌊\frac{n}{2}⌋. By Eqns. (1),(2), (3), (4), and Definition 7, we know that

P_{t}(n) = ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}\binom{2k}{k}\binom{2n − 2k}{n − k},  (24)

Q_{t}(n) = ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}(n − k)\binom{2k}{k}\binom{2n − 2k}{n − k},  (25)

R_{t}(n) = ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}C_{k}\binom{2n − 2k}{n − k},  (26)

T_{t}(n) = ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}C_{k}C_{n−k}.  (27)

We present the following five main lemmas for calculating the sums P_{t}(2n), Q_{t}(2n − 1), R_{t}(2n), R_{t}(2n − 1), and T_{t}(2n).

Lemma 10. Let n and t be non-negative integers such that t ≤ n. Then

P_{t}(2n) = (−1)^{t} \begin{matrix}\binom{2n}{n} & \binom{2t}{t} & \binom{2n−2t}{n−t} \\ ( & {2n−t \atop t} & ) \end{matrix}.

Lemma 11. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n−1. Then

Q_{t}(2n − 1) = (−1)^{t} \frac{2(2n − 1)\binom{2(n−1)}{n−1}\binom{2t}{t}\binom{2(n−1−t)}{n−1−t}}{\binom{2n−1−t}{t}}.

Lemma 12. Let n and t be non-negative integers such that t ≤ n. Then

R_{t}(2n) = (−1)^{t} \begin{matrix}\binom{2n}{n} & \binom{2t}{t} & \binom{2n−2t}{n−t} \\ ( & {2n+1−t \atop t} & ) \end{matrix}.

Lemma 13. Let n and t be non-negative integers such that t ≤ n. Then

T_{t}(2n) = (−1)^{t} \frac{C_{n}\binom{2t}{t}\binom{2n−2t}{n−t}}{\binom{2n+1−t}{t}}.

Lemma 14. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n−1. Then

R_{t}(2n − 1) = (−1)^{t} \begin{matrix}\binom{2n−1}{n} & \binom{2t}{t} & \binom{2n−2t−1}{n−t} \\ ( & {2n−t \atop t} & ) \end{matrix}.

Sums Q_{t}(n), R_{t}(n), and T_{t}(n) are auxiliary sums for the sum P_{t}(n). We give recurrences between these sums. We start with two propositions.

Proposition 15. Let n be a positive integer, and let t be a non-negative integer such that t < \frac{n}{2}. Then

Q_{t}(n) = 4(n − 2t)P_{t}(n − 1) + 2(n − 2t)(−1)^{n}R_{t}(n − 1) + tP_{t}(n).

Proposition 16. Let n be a positive integer, and let t be a non-negative integer such that t < \frac{n}{2}. Then

(n − t + 1)R_{t}(n) = P_{t}(n) + 4(n − 2t)R_{t}(n − 1) − 2(n − 2t)T_{t}(n − 1).

Proposition 15 has the following two consequences.

Corollary 17. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n − 1. Then

R_{t}(2n − 1) = \frac{1}{4}P_{t}(2n).

Corollary 18. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n − 1. Then

Q_{t}(2n − 1) = 2(2n − 1 − 2t)(2P_{t}(2n − 2) − R_{t}(2n − 2)).

Proposition 16 also has two consequences.

Corollary 19. Let n and t be non-negative integers such that t ≤ n. Then

R_{t}(2n) = \frac{2n − 2t + 1}{2n − t + 1}P_{t}(2n).

Corollary 20. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n − 1. Then

R_{t}(2n − 1) = \frac{2(2n − 2t − 1)(2n − 1)}{n(2n − t)}R_{t}(2n − 2).

Furthermore, by Corollaries 18 and 19, it follows that

Corollary 21. Let n be a positive integer, and let t be a non-negative integer such that t ≤ n − 1. Then

Q_{t}(2n − 1) = \frac{2(2n − 1)(2n − 1 − 2t)}{2n − 1 − t}P_{t}(2n − 2).

Finally, by Corollaries 17, 19, and 20, we give the following recurrence for P_{t}(2n).

Corollary 22. Let n be a positive integer, and let t be a non-negative integer such that t < n. Then

P_{t}(2n) = \frac{8(2n − 1)(2n − 2t − 1)^{2}}{n(2n − t)(2n − t − 1)} P_{t}(2n − 2).

We prove Lemma 10 by telescoping the recurrence from Corollary 22. Once we obtain Lemma 10, proofs of Lemmas 11, 12, and 14 follow from Corollaries 21, 19, and 17, respectively. Note that Lemma 13 follows from Eq. (23) and Lemma 12. Therefore, proofs of Lemmas 11, 12, 13, and 14 are omitted. Since we do not use the sum Q_{t}(2n − 1) for calculating the sum P_{t}(2n), proofs of Corollaries 18 and 21 are omitted too. The other corollaries are proved.

5 Proofs of main lemmas, propositions and corollaries

First, we prove Propositions 15 and 16. To do this, we use two known binomial identities. The first is [5, Eq. (1.2), p. 5]

(n − k)\binom{n}{k} = n\binom{n − 1}{k},  (28)

where k is an arbitrary integer. The second identity is

\binom{2k}{k} = 4\binom{2(k − 1)}{k − 1} − 2C_{k−1},  (29)

where k is a positive integer. Eq. (29) follows from the recurrence relation for the central binomial coefficients [5, p. 26] and the definition of the Catalan numbers.

5.1 Proof of Proposition 15

Proof. By Eqns. (24) and (25), we have

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

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

Note that the last term of the sum on the right-side of Eq. (30) equals zero. By using Eq. (28), it follows that \binom{n−2t}{k−t}(n − k − t) = (n − 2t)\binom{n−1−2t}{k−t}. Combining these two facts, it follows that

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

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

Since k ≤ n − 1 − t in Eq. (31), it follows that k < n. By using Eq. (29), we know that

\binom{2(n − k)}{n − k} = 4\binom{2(n − 1 − k)}{n − 1 − k} − 2C_{n−1−k}.  (32)

By using Eq. (32), we have

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

= 4 ∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t}\binom{2k}{k}\binom{2(n − 1 − k)}{n − 1 − k}  (34)

−2 ∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t}\binom{2k}{k}C_{n−1−k}.  (35)

By Eq. (24), Eq. (34) equals 4P_{t}(n − 1). Changing k to n − 1 − k and by using Eq. (26), Eq. (35) becomes −2(−1)^{n−1}R_{t}(n − 1). Therefore, combining these facts, Eq. (33) becomes

4P_{t}(n − 1) + 2(−1)^{n}R_{t}(n − 1).  (36)

By using Eqns. (33) and (36), Eq. (31) becomes

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

= 4(n − 2t)P_{t}(n − 1) + 2(−1)^{n}(n − 2t)R_{t}(n − 1).  (37)

Finally, Eqns. (30) and (37) complete the proof of Proposition 15.

5.2 Proof of Proposition 16

Proof. By Eq. (26), we have

R_{t}(n) = ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}C_{k}\binom{2n − 2k}{n − k}

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

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

By Eq. (24), Eq. (38) becomes

R_{t}(n) = P_{t}(n) + ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}(−k) C_{k}\binom{2n − 2k}{n − k}

= P_{t}(n) + ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}((n − t − k) + (t − n)) C_{k}\binom{2n − 2k}{n − k}.  (39)

By Eq. (26), Eq. (39) becomes

R_{t}(n) = P_{t}(n) + ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}(n − t − k) C_{k}\binom{2n − 2k}{n − k} + (t − n)R_{t}(n).  (40)

The Eq. (40) is equivalent to the following equation

(n − t + 1)R_{t}(n) = P_{t}(n) + ∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}(n − t − k) C_{k}\binom{2n − 2k}{n − k}.  (41)

Similarly as in Eq. (31), we have

∑_{k=t}^{n−t}(−1)^{k}\binom{n − 2t}{k − t}(n − t − k) C_{k}\binom{2n − 2k}{n − k}  (42)

= (n − 2t) ∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t} C_{k}\binom{2n − 2k}{n − k}.  (43)

By using Eq. (32), it follows that

∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t} C_{k}\binom{2n − 2k}{n − k}  (44)

= 4 ∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t} C_{k}\binom{2(n − 1 − k)}{n − 1 − k}  (45)

−2 ∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t}C_{k} C_{n−1−k}.  (46)

By Eq. (26), Eq. (45) is equal to 4R_{t}(n−1). By Eq. (27), Eq. (46) is equal to −2T_{t}(n−1). Therefore, by Eqns. (44), (45), and (46), it follows that

∑_{k=t}^{n−1−t}(−1)^{k}\binom{n − 1 − 2t}{k − t} C_{k}\binom{2n − 2k}{n − k} = 4R_{t}(n − 1) − 2T_{t}(n − 1).  (47)

By Eqns. (47), (42), and (43), Eq. (41) becomes

(n − t + 1)R_{t}(n) = P_{t}(n) + (n − 2t)(4R_{t}(n − 1) − 2T_{t}(n − 1))
= P_{t}(n) + 4(n − 2t)R_{t}(n − 1) − 2(n − 2t)T_{t}(n − 1).

This completes the proof of Proposition 16.

5.3 Proofs of Corollaries 17, 19, and 20

We begin with the proof of Corollary 17. Corollary 17 is a consequence of Proposition 15 and Lemma 9.

Proof. Let n be a positive integer. By setting n := 2n in Proposition 15, we obtain that

Q_{t}(2n) = 4(2n − 2t)P_{t}(2n − 1) + 2(2n − 2t)(−1)^{2n}R_{t}(2n − 1) + tP_{t}(2n),  (48)

where 0 ≤ t < \frac{2n}{2} = n.

By Eqns. (20) and (21) from Lemma 9, Eq. (48) is equivalent to

nP_{t}(2n) = 2(2n − 2t)R_{t}(2n − 1) + tP_{t}(2n),
4(n − t)R_{t}(2n − 1) = (n − t)P_{t}(2n).  (49)

Since t < n, we can divide both sides of Eq. (49) by 4(n − t). Therefore, Eq. (49) becomes

R_{t}(2n − 1) = \frac{1}{4}P_{t}(2n).

This completes the proof of Corollary 17.

Corollary 19 is a consequence of Proposition 16, Corollary 17, and Lemma 9. We now prove Corollary 19.

Proof. Let n be a positive integer. By setting n := 2n in Proposition 16, we obtain

(2n − t + 1)R_{t}(2n) = P_{t}(2n) + 4(2n − 2t)R_{t}(2n − 1) − 2(2n − 2t)T_{t}(2n − 1),  (50)

where 0 ≤ t < \frac{2n}{2} = n.

By Eq. (22) from the Lemma 9, the integer T_{t}(2n−1) vanishes. Then Eq. (50) is equivalent to

(2n − t + 1)R_{t}(2n) = P_{t}(2n) + 4(2n − 2t)R_{t}(2n − 1).  (51)

By Corollary 17, Eq. (51) becomes as follows:

(2n − t + 1)R_{t}(2n) = P_{t}(2n) + 4(2n − 2t)\frac{1}{4}P_{t}(2n),
(2n − t + 1)R_{t}(2n) = (2n − 2t + 1)P_{t}(2n).

Since t < n, we can divide both sides of the last equation above by 2n − t + 1. It follows that

R_{t}(2n) = \frac{2n − 2t + 1}{2n − t + 1}P_{t}(2n).  (52)

Therefore, we proved Corollary 19 for all positive integers n and for all non-negative integers t such that t < n.

By Eq. (24), we know that

P_{n}(2n) = (−1)^{n}\binom{2n}{n}^{2},  (53)

where n is a non-negative integer. By Eq. (26), it follows that

R_{n}(2n) = (−1)^{n}C_{n}\binom{2n}{n},  (54)

where n is a non-negative integer. Therefore, by using Eqns. (53) and (54), it follows that Eq. (52) holds for t = n. Also, this proves the case n = 0. Therefore, Corollary 19 follows, as desired.

Finally, let us prove Corollary 20. Corollary 19 is a consequence of Proposition 16 and Lemma 9.

Proof. Let n be a positive integer. By setting n := 2n − 1 in Proposition 16, we obtain that

(2n − t)R_{t}(2n − 1) = P_{t}(2n − 1) + 4(2n − 1 − 2t)R_{t}(2n − 2) − 2(2n − 1 − 2t)T_{t}(2n − 2); (55)

where 0 ≤ t < \frac{2n−1}{2}.

By Eq. (20) from Lemma 9, the integer P_{t}(2n−1) vanishes in Eq. (55). By Eq. (23) from Lemma 9, the integer T_{t}(2n − 2) is equal to \frac{1}{n}R_{t}(2n − 2). Therefore, Eq. (54) becomes as follows:

(2n − t)R_{t}(2n − 1) = 4(2n − 1 − 2t)R_{t}(2n − 2) − 2(2n − 1 − 2t)\frac{1}{n}R_{t}(2n − 2)
(2n − t)R_{t}(2n − 1) = 2(2n − 1 − 2t)R_{t}(2n − 2)(2 − \frac{1}{n})
(2n − t)R_{t}(2n − 1) = 2(2n − 1 − 2t)R_{t}(2n − 2) \frac{2n − 1}{n}.  (56)

Since t ≤ n − 1, we can divide the both sides of Eq. (56) by 2n − t. The Eq. (56) becomes

R_{t}(2n − 1) = \frac{2(2n − 1)(2n − 1 − 2t)}{n(2n − t)}R_{t}(2n − 2).

This completes the proof of Corollary 20.

5.4 Proof of Corollary 22

Corollary 22 is a consequence of Corollaries 17, 19, and 20.

Proof. Let n be a positive integer.

By setting n := n − 1 in Corollary 19, we obtain

R_{t}(2n − 2) = \frac{2n − 2t − 1}{2n − t − 1}P_{t}(2n − 2),  (57)

where t is a non-negative integer such that t ≤ n − 1.

By using Corollary 17 and Eq. (57), Corollary 20 becomes as follows:

\frac{1}{4}P_{t}(2n) = \frac{2(2n − 1)(2n − 1 − 2t)}{n(2n − t)} · \frac{2n − 2t − 1}{2n − t − 1}P_{t}(2n − 2),
P_{t}(2n) = \frac{8(2n − 1)}{n} · \frac{(2n − 2t − 1)^{2}}{(2n − t)(2n − 1 − t)}P_{t}(2n − 2).  (58)

This completes the proof of Corollary 22.

5.5 Proof of Lemma 10

Proof. By Eq. (53), we know that

P_{t}(2t) = (−1)^{t}\binom{2t}{t}^{2},  (59)

where t is a non-negative integer. Let n be a positive integer, and let t be a non-negative integer such that t < n. We telescope Eq. (58) from Corollary 22.

We have

P_{t}(2n) = \frac{8(2n − 1)}{n} · \frac{(2n − 2t − 1)^{2}}{(2n − t)(2n − 1 − t)}P_{t}(2n − 2)

= 8^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n(n − 1) ⋯ (t + 1)} · \frac{((2n − 2t − 1)!!)^{2}}{(2n − t) ⋯ (t + 1)}P_{t}(2t).

By using Eq. (59), the last equation above becomes

P_{t}(2n) = 8^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n(n − 1) ⋯ (t + 1)} · \frac{((2n − 2t − 1)!!)^{2}}{(2n − t) ⋯ (t + 1)}(−1)^{t} \frac{((2t)!)^{2}}{(t!)^{4}} .  (60)

Then Eq. (60) becomes as follows:

P_{t}(2n) = (−1)^{t}8^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n! (2n − t)!} · \frac{((2n − 2t − 1)!!)^{2}}{(t!)^{2}} ((2t)!)^{2},

= (−1)^{t}2^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n! (2n − t)!} · \frac{(2^{n−t}(2n − 2t − 1)!!)^{2}((2t)!)^{2}}{(t!)^{2}}

= (−1)^{t}2^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n! (2n − t)!} · \frac{(2^{n−t}(n − t)! (2n − 2t − 1)!!)^{2}((2t)!)^{2}}{((n − t)!)^{2} · (t!)^{2}}

= (−1)^{t}2^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n! (2n − t)!} · \frac{((2n − 2t)!! (2n − 2t − 1)!!)^{2}((2t)!)^{2}}{((n − t)!)^{2} · (t!)^{2}}

= (−1)^{t}2^{n−t} \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)}{n! (2n − t)!} · \frac{((2n − 2t)!)^{2}((2t)!)^{2}}{((n − t)!)^{2} · (t!)^{2}}

= (−1)^{t}2^{n−t} \frac{n(n − 1) ⋯ (t + 1)}{n(n − 1) ⋯ (t + 1)} · \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)((2n − 2t)!)^{2}((2t)!)^{2}}{n! · (2n − t)! · (t!)^{2} · ((n − t)!)^{2}}

= (−1)^{t} \frac{2n(2n − 2) ⋯ (2t + 2)}{n(n − 1) ⋯ (t + 1)} · \frac{(2n − 1)(2n − 3) ⋯ (2t + 1)((2n − 2t)!)^{2}((2t)!)^{2}}{n! · (2n − t)! · (t!)^{2} · ((n − t)!)^{2}}

= (−1)^{t} \frac{2n(2n − 1) ⋯ (2t + 1) · (2t)!}{n(n − 1) ⋯ (t + 1) · t!} · \frac{((2n − 2t)!)^{2}(2t)!}{n! · (2n − t)! · t! · ((n − t)!)^{2}} .

P_{t}(2n) = (−1)^{t} \frac{(2n)!}{n!} · \frac{((2n − 2t)!)^{2}(2t)!}{n! · (2n − t)! · t! · ((n − t)!)^{2}}

= (−1)^{t}\binom{2n}{n} · \frac{(2n − 2t)!}{((n − t)!)^{2}} · \frac{(2n − 2t)!(2t)!}{(2n − t)! · t!}

= (−1)^{t}\binom{2n}{n} · \binom{2n − 2t}{n − t} · \frac{(2n − 2t)! · t!}{(2n − t)!} · \frac{(2t)!}{(t!)^{2}}

= (−1)^{t}\binom{2n}{n} · \binom{2n − 2t}{n − t} · \frac{1}{\binom{2n−t}{t}} · \binom{2t}{t}.

Therefore, it follows that

P_{t}(2n) = (−1)^{t} \begin{matrix}\binom{2n}{n} & \binom{2t}{t} & \binom{2n−2t}{n−t} \\ ( & {2n−t \atop t} & ) \end{matrix},  (61)

where n > t. Eqns. (59) and (61) complete the proof of Lemma 10.

Now Eq. (12) directly follows from Lemma 10.

Remark 23. Note that Lemma 13 generalizes Eq. (7). By setting t = 0 in Lemma 13, we obtain Eq. (7). Similarly, Lemma 12 generalizes Eq. (6) for even n, and Lemma 14 generalizes Eq. (6) for odd n.

6 Proofs of main results

We begin with the proof of Theorem 1.

6.1 Proof of Theorem 1

Proof. By Eq. (5), we know that Theorem 1 is true for m = 1. Therefore, let us suppose m ≥ 2.

Let n be a fixed non-negative integer. Let j be a non-negative integer such that j ≤ n. We prove that D_{P} (2n, j, 0) is divisible by \binom{2n}{n} for all j such that j ≤ n.

By Relation 15, it follows that

D_{P} (2n, j, 0) = ∑_{u=0}^{⌊ \frac{2n−2j}{2} ⌋} \binom{2n − j}{u}\binom{2n − j − u}{j + u}P_{j+u}(2n)

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

Obviously, 0 ≤ j + u ≤ n in Eq. (62). By setting t := j + u in Lemma 10, it follows that

P_{j+u}(2n) = (−1)^{j+u} \begin{matrix}\binom{2n}{n} & \binom{2(j+u)}{j+u} & \binom{2n−2j−2u}{n−j−u} \\ ( & {2n−j−u \atop j+u} & ) \end{matrix}.  (63)

By using Eq. (63), Eq. (62) becomes as follows

D_{P} (2n, j, 0) = ∑_{u=0}^{n−j} \binom{2n − j}{u}\binom{2n − j − u}{j + u}(−1)^{j+u} \begin{matrix}\binom{2n}{n} & \binom{2(j+u)}{j+u} & \binom{2n−2j−2u}{n−j−u} \\ ( & {2n−j−u \atop j+u} & ) \end{matrix}

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

By Eq. (64), it follows that D_{P} (2n, j, 0) is divisible by \binom{2n}{n} for all j such that j ≤ n.

We assert that D_{P} (2n, j, t) is divisible by \binom{2n}{n} for all non-negative integers j and t such that j ≤ n.

We assume that n is a fixed non-negative integer. We use induction on t. For t = 0, we proved that D_{P} (2n, j, t) is divisible by \binom{2n}{n} for all non-negative j such that j ≤ n. Let s be a non-negative integer. Let us assume that D_{P} (2n, j, t) is divisible by \binom{2n}{n} for t = s and for all non-negative integers j such that j ≤ n. What happens with D_{P} (2n, j, s + 1) ? By Relation 10, it follows that

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

Obviously, 0 ≤ j + u ≤ n in Eq. (65). By the induction hypothesis, D_{P} (2n, j + u, s) is divisible by \binom{2n}{n}. By Eq. (65), it follows that D_{P} (2n, j, s + 1) is divisible by \binom{2n}{n}.

This proves the induction step. Therefore, D_{P} (2n, j, t) is divisible by \binom{2n}{n} for all nonnegative integers j and t such that j ≤ n.

By Relation 9, it follows that

P (2n, m) = D_{P} (2n, 0, m − 2),  (66)

where m is a positive integer such that m ≥ 2.

Since D_{P} (2n, 0, m−2) is divisible by \binom{2n}{n}, by Eq. (66), it follows that P (2n, m) is divisible by \binom{2n}{n} for all m ≥ 2. This completes the proof of Theorem 1.

Remark 24. By setting j = 0 in Eq. (64) and by using Eq. (9), it follows that

P (2n, 2) = \binom{2n}{n} ∑_{u=0}^{n}(−1)^{u}\binom{2n}{u}\binom{2u}{u}\binom{2n − 2u}{n − u}.  (67)

Remark 25. Let us suppose that n is a positive integer. Then, at least one of binomial coefficients \binom{2(j+u)}{j+u} and \binom{2n−2j−2u}{n−j−u} must be even in Eq. (64). By Eq. (64), we obtain D_{P} (2n, j, 0) is divisible by 2\binom{2n}{n} for all positive integers n and all non-negative integers j such that j ≤ n. By the method of D sums and Eq. (5), we can conclude that P (2n, m) is divisible by 2\binom{2n}{n} for all positive integers m and n.

Remark 26. The proof of Theorem 2 is similar to the proof of Theorem 1. We use Relation 15 and Lemma 11. If n is a positive integer greater than 1, it follows that Q(2n − 1, m) is divisible by 4(2n − 1)\binom{2(n−1)}{n−1} for all positive integers m.

6.2 Proof of Theorem 3

By Eqns. (3) and (6), we know that R(2n, 1) = \binom{2n}{n}^{2}. By definition of the Catalan numbers, it follows that n + 1 divides \binom{2n}{n}. Therefore, Theorem 3 is true for m = 1. Let us suppose that m is a positive integer greater than 2. Let n be a fixed non-negative integer. Let j be a non-negative integer such that j ≤ n. We use the method of D sums, Lemma 12, and one additional result. Namely, let a and b be positive integers. It is known [3, Corollary 1.5] that

\frac{a}{2(a + b)}\binom{2a}{a}\binom{2b}{b} is always an integer.  (68)

In other words, the integer a\binom{2a}{a}\binom{2b}{b} is divisible by 2(a + b). Gessel gave a combinatorial interpretation of Eq. (68). See [2, Section 7].

Our proof of Theorem 3 consists of two parts.

In the first part, we show Theorem 3 is true for m = 2 by using Eqns. (9), (15), (68), and Lemma 12.

In the second part, we show that D_{R}(2n, j, 1) is divisible by (n + 1)\binom{2n}{n} for all nonnegative integers j such that j ≤ n. By Relation 10, Eq. (68), and induction, it follows that D_{P} (2n, j, t) is divisible by (n + 1)\binom{2n}{n} for all positive integers t and for all non-negative integers j such that j ≤ n. By Relation 9, we obtain Theorem 3 is true for all m ≥ 3.

The first part:

Proof. By Relation 15, it follows that

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

Obviously, 0 ≤ j + u ≤ n in Eq. (69). By setting t := j + u in Lemma 12, it follows that

R_{j+u}(2n) = (−1)^{j+u} \begin{matrix}\binom{2n}{n} & \binom{2(j+u)}{j+u} & \binom{2n−2j−2u}{n−j−u} \\ ( & {2n+1−j−u \atop j+u} & ) \end{matrix}.  (70)

By using Eq. (70), Eq. (69) becomes as follows:

D_{R}(2n, j, 0) = ∑_{u=0}^{n−j} \binom{2n − j}{u}\binom{2n − j − u}{j + u}(−1)^{j+u} \begin{matrix}\binom{2n}{n} & \binom{2(j+u)}{j+u} & \binom{2n−2j−2u}{n−j−u} \\ ( & {2n+1−j−u \atop j+u} & ) \end{matrix}

= (−1)^{j}\binom{2n}{n} ∑_{u=0}^{n−j}(−1)^{u} \begin{matrix}\binom{2n−j}{u} & \binom{2n−j−u}{j+u} \\ ( & {2n+1−j−u \atop j+u} & ) \end{matrix}\binom{2(j + u)}{j + u}\binom{2n − 2j − 2u}{n − j − u}. (71)

By Eq. (28), it follows that

\begin{matrix}( & {2n−j−u \atop j+u} & ) \\ ( & {2n+1−j−u \atop j+u} & ) \end{matrix} = \frac{2n + 1 − 2j − 2u}{2n + 1 − j − u}.  (72)

By Eqns. (72) and (28), we have

\binom{2n − j}{u}\begin{matrix}( & {2n−j−u \atop j+u} & ) \\ ( & {2n+1−j−u \atop j+u} & ) \end{matrix} = \frac{2n + 1 − 2j − 2u}{2n + 1 − j}\binom{2n + 1 − j}{u}.  (73)

By using Eq. (72), Eq. (71) becomes

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

Let M(n, j) denote the sum

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

Then Eq. (74) can be written as

D_{R}(2n, j, 0) = \frac{(−1)^{j}\binom{2n}{n}}{2n + 1 − j} M(n, j).  (76)

Let us prove that M(n, j) is divisible by n + 1 for all non-negative integers j such that j ≤ n. It is readily verified that

(2n + 1 − 2j − 2u)\binom{2n − 2j − 2u}{n − j − u} = \frac{n + 1 − j − u}{2}\binom{2(n + 1 − j − u)}{n + 1 − j − u}.  (77)

By using Eq. (77), Eq. (75) becomes

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

By Eq. (68), it follows that \frac{n+1−j−u}{2} \binom{2(n+1−j−u)}{n+1−j−u}\binom{2(j+u)}{j+u} is divisible by n + 1. By Eqns. (68) and (78), the sum M(n, j) is divisible by n + 1. In particular, the sum M(n, 0) is divisible by n + 1.

Let us prove that the sum M(n, 0) is divisible by 2n + 1. By Eq. (75), we obtain

M(n, 0) = ∑_{u=0}^{n}(−1)^{u}(2n + 1 − 2u)\binom{2n + 1}{u}\binom{2u}{u}\binom{2n − 2u}{n − u}.  (79)

We have

(2n + 1 − 2u)\binom{2n + 1}{u} = (2n + 1)\binom{2n + 1}{u} − 2u\binom{2n + 1}{u}

= (2n + 1)\binom{2n + 1}{u} − 2(2n + 1)\binom{2n}{u − 1}

= (2n + 1)(\binom{2n + 1}{u} − 2\binom{2n}{u − 1}).  (80)

Note that we used the identity k\binom{n}{k} = n\binom{n−1}{k−1}. See [5, Eq. (1.1), p. 5].

By Eq. (80), it follows that (2n + 1 − 2u)\binom{2n+1}{u} is divisible by 2n + 1. By Eq. (79), it follows that M(n, 0) is divisible by 2n + 1. Note that numbers n + 1 and 2n + 1 are relatively prime. Therefore, we conclude that M(n, 0) is divisible by (n + 1)(2n + 1).

By Relation 9, we know that

R(2n, 2) = D_{R}(2n, 0, 0).  (81)

By setting j = 0 in Eq. (76), it follows that

D_{R}(2n, 0, 0) = \frac{\binom{2n}{n}}{2n + 1}M(n, 0).  (82)

We know that \frac{M(n,0)}{2n+1} is an integer divisible by n + 1.

Therefore, by using Eqns. (81) and (82), we conclude R(2n, 2) is divisible by (n + 1)\binom{2n}{n}. This proves the first part of Theorem 3.

We note that the integers \binom{2n}{n} and 2n + 1 are not relatively prime in general.

The second part:

Proof. By setting t = 0 and S = R, Relation 10 becomes

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

By setting j := j + u in Eq. (76), Eq. (76) becomes

D_{R}(2n, j + u, 0) = \frac{(−1)^{j+u}\binom{2n}{n}}{2n + 1 − j − u}M(n, j + u),  (84)

where 0 ≤ j + u ≤ n.

By using Eq. (84), Eq. (83) becomes

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

It is readily verified that

\frac{1}{2n + 1 − j − u}\binom{2n}{j + u} = \frac{1}{2n + 1}\binom{2n + 1}{j + u}.  (86)

By using Eq. (86), Eq. (85) becomes

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

Let N(n, j) denote the sum

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

By Eq. (88), Eq. (87) becomes

D_{R}(2n, j, 1) = \frac{(−1)^{j}\binom{2n}{n}}{2n + 1}N(n, j).  (89)

Recall that M(n, j) is divisible by n + 1 for all integers j such that 0 ≤ j ≤ n. Therefore, M(n, j + u) is divisible by n + 1 for all non-negative integers u such that u ≤ n − j. By Eq. (88), it follows that N(n, j) is divisible by n + 1 for all non-negative integers j such that j ≤ n. Let us prove that N(n, j) is divisible by 2n + 1.

By Eq. (88), it is sufficient to prove that \binom{2n+1}{j+u}M(n, j + u) is divisible by 2n + 1. By setting j := j + u in Eq. (75), it follows that

M(n, j + u) =

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

Let I(n, j, u, v) denote \binom{2(j+u+v)}{j+u+v}\binom{2n−2j−2u−2v}{n−j−u−v}. Then \binom{2n+1}{j+u}M(n, j + u) is equal to

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

Let us prove that (2n + 1 − 2j − 2u − 2v)\binom{2n+1}{j+u}\binom{2n+1−j−u}{v} is divisible by 2n + 1. It is readily verified that

\binom{2n + 1}{j + u}\binom{2n + 1 − j − u}{v} = \binom{2n + 1}{j + u + v}\binom{j + u + v}{v}.  (90)

By Eq. (90), it follows that

(2n + 1 − 2j − 2u − 2v)\binom{2n + 1}{j + u}\binom{2n + 1 − j − u}{v}

= (2n + 1 − 2j − 2u − 2v)\binom{2n + 1}{j + u + v}\binom{j + u + v}{v}.  (91)

Recall that, by Eq. (80), it follows that (2n+1−2u)\binom{2n+1}{u} is divisible by 2n+1. Therefore, (2n+1−2(j +u+v))\binom{2n+1}{j+u+v} is divisible by 2n+1. This means that the right-side of Eq. (91) is divisible by 2n + 1. Then the left-side of Eq. (91) is divisible by 2n + 1. This implies that \binom{2n+1}{j+u}M(n, j + u) is divisible by 2n + 1. By Eq. (88), it follows that N(n, j) is divisible by 2n + 1. Hence we have proved that N(n, j) is divisible by the integers n + 1 and 2n + 1. Since they are relatively prime, it follows that N(n, j) is divisible by (n + 1)(2n + 1).

Finally, by using Eq. (89), we obtain that D_{R}(2n, j, 1) is divisible by (n + 1)\binom{2n}{n} for all non-negative integers j such that j ≤ n. We assert that D_{R}(2n, j, t) is divisible by (n+1)\binom{2n}{n} for all non-negative integers j and for all positive integers t such that j ≤ n. We use Relation 10 and induction as in the proof of Theorem 1. See Eq. (65).

By Relation 9, we have

R(2n, t + 2) = D_{R}(2n, 0, t).  (92)

Since t ≥ 1, this implies that t + 2 ≥ 3. By Eq. (92), it follows that R(2n, m) is divisible by (n + 1)\binom{2n}{n} for all integers m such that m ≥ 2. This proves the second part of Theorem 3. Theorem 3 follows, as desired.

Remark 27. Corollary 4 follows from Theorem 3 and Eq. (19) from Lemma 8. Remark 28. The proof of Theorem 5 is similar to the proof of Theorem 3. We use Lemma 14 instead of Lemma 12. We do not use Eq. (68).

7 Acknowledgments

I would like to thank Professor Jeffrey Shallit for valuable comments which helped to improve the article. Thanks to my teacher Vanja Vujić for proofreading this paper. Also, I would like to thank the referee for useful suggestions.

References

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

[2] I. M. Gessel, Super ballot numbers, J. Symbolic Comput. 14 (1992), 179–194.

[3] V. J. W. Guo, Proof of two divisibility properties of binomial coefficients conjectured by Z. W. Sun, Electron. J. Combin. 21 (2014), # P54.

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

[5] T. Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

[6] J. Mikić, A method for examining divisibility properties of some binomial sums, J. Inteqer Sequences 21 (2018), Article 18.8.7.

[7] J. Mikić, A proof of a famous identity concerning the convolution of the central binomial coefficients, J. Integer Sequences 19 (2016), Article 16.6.6.

[8] J. Mikić, Two new identities involving the Catalan numbers and sign-reversing involutions, J. Integer Sequences 22 (2019), Article 19.7.7.

[9] M. Petkovšek, H. Wilf, and D. Zeilberger, A = B, A. K. Peters, 1996.

2010 Mathematics Subject Classification: Primary 05A10 ; Secondary 05A19. Keywords: method of D sums, central binomial coefficient, Catalan number, recurrence relation, induction, alternating binomial sum.

Received May 21 2019; revised version received June 5 2019; November 16 2019; November 17 2019. Published in Journal of Integer Sequences, December 30 2019.

Return to Journal of Integer Sequences home page.