Two New Identities Involving the Catalan Numbers and Sign-Reversing Involutions

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

                   jnmikic@gmail.com

Abstract

We give a combinatorial proof of a known sum concerning the product of a binomial coefficient with two central binomial coefficients. The method of description, involution, and exception is used. The same combinatorial argument also proves the “−1 shifted version” of this sum. As a consequence, two new binomial coefficient identities with the Catalan numbers are derived.

1 Introduction

Let n be a non-negative integer. The Catalan numbers are the famous sequence

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

In this paper, we derive two new (to our knowledge) binomial coefficient identities with the Catalan numbers. Theorem 1. For non-negative integers n, we have

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

In order to prove Theorem 1, we consider a known combinatorial sum

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k}\binom{2n − 2k}{n − k} = \begin{cases}0, & if n is odd; \\ \binom{n}{\frac{n}{2}}^{2}, & if n is even. \end{cases}  (3)

Eq. (3) appears several times in the literature; see, for example, [2, Eq. (6.12), p. 52], [3, Eq. (6.61), p. 29], and [7, Example 3.6.2, p. 45]. There are two binomial coefficient identities ([3, Eq. (6.10), p. 23; Eq. (7.3), p. 34]) similar to Eq. (3). They are proved combinatorially, for example, in [8]. See [6] and [5, Conclusions] for the connection between these identities and Shapiro’s formula [9, Ex. (6.C.18), p. 41] and Segner’s recurrence relation [4, Eq. (5.6), p. 117] respectively.

We give a proof of Eq. (3) by using the method of “description, involution, and exception” [1].

By using the same idea, we derive the “−1 shifted version” of Eq. (3). We assert that

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k − 1}\binom{2n − 2k}{n − k} = \begin{cases}−\binom{n}{⌊ \frac{n}{2} ⌋}^{2}, & if n is odd; \\ 0, & if n is even. \end{cases}  (4)

Clearly, subtracting Eq. (4) from Eq. (3) and by using the well-known relation C_{k} = \binom{2k}{k} − \binom{2k}{k−1}, we get Eq. (1). Furthermore, it can be shown that Eq. (2) is a consequence of Eq. (1).

Throughout the paper, [n] denotes the set {1, 2, …, n}, if n is a positive integer; and [0] denotes the empty set ∅.

Let A and B be sets. Then |A| denotes the cardinality of the set A, and A\B denotes the set difference: {x : x ∈ A, x ∉ B}.

We end this paper with the generalization of Eqns. (3) and (4).

2 Definitions

Let n be a fixed non-negative integer.

Definition 2. For A ⊂ [n], we define

A^{t} = \begin{cases}∅, & if A = ∅; \\ \{x + n : x ∈ A\}, & if A ≠ ∅. \end{cases}

Obviously, if A ⊂ [n], then A^{t} ⊂ [2n]\[n].

Definition 3. We define the function φ : [2n] → [2n], as follows:

φ(x) = \begin{cases}x + n, & if x ∈ [n]; \\ x − n, & if x ∈ [2n]\[n]. \end{cases}

Definition 4. Let S ⊂ [2n]. The set S is balanced if S = (S ∩ [n]) ∪ (S ∩ [n])^{t}. Otherwise, S is a unbalanced set.

In other words, set S is balanced if ∀x (x ∈ S ⇔ φ(x) ∈ S). Clearly, if set S is balanced, then |S| must be even.

The union of two balanced sets is a balanced set. Note that the converse does not hold even if two sets are disjoint. For example, unbalanced sets [n] and [2n]\[n] are disjoint, but their union is a balanced set [2n].

However, if S_{1} and S_{2} are disjoint sets such that S_{1} ∪ φ(S_{1}) and S_{2} ∪ φ(S_{2}) are disjoint sets, then S_{1} ∪ S_{2} is a balanced set if and only if both sets S_{1} and S_{2} are balanced.

3 Proof of Eq. (3)

Proof. Let n be a fixed non-negative integer. We use the method of description, involution, and exception, as discussed in [1].

Description:

Let X denote the set

{(A, B, C) : A ⊂ [n], B ⊂ A ∪ A^{t}, |A| = |B|, C ⊂ [2n]\(A ∪ A^{t}), |A| + |C| = n}.

For integers k, where 0 ≤ k ≤ n, we define the sets X_{k}, as follows:

X_{k} = {(A, B, C) ∈ X : |A| = k}.

Obviously, X = ⋃_{k=0}^{n} X_{k} and |X_{k}| = \binom{n}{k}\binom{2k}{k}\binom{2n−2k}{n−k}. We have

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k}\binom{2n − 2k}{n − k} = ∑_{k=0}^{n}(−1)^{k}|X_{k}| = |E| − |O|;  (5)

where

E = {(A, B, C) ∈ X : |A| is even} and O = {(A, B, C) ∈ X : |A| is odd}.

Involution:

Let us define sets D and E, as follows:

D = {(A, B, C) ∈ X : B ∪ C is an unbalanced set}  (6)
E = {(A, B, C) ∈ X : B ∪ C is balanced set}  (7)

Obviously, D and E are disjoint sets and X = D ∪ E.

Let (A, B, C) ∈ D. We let d_{B,C} denote min{x ∈ B ∪ C : φ(x) ∉ B ∪ C}. The integer d_{B,C} is well-defined because B ∪ C is an unbalanced set.

Let us define the function Ψ : D → D, as follows:

Ψ((A, B, C)) = \begin{cases}(A\\{d_{B,C}\}, B\\{d_{B,C}\}, C ∪ \{d_{B,C}\}), & if d_{B,C} ∈ B ∩ [n]; \\ (A\\{d_{B,C} − n\}, B\\{d_{B,C}\}, C ∪ \{d_{B,C}\}), & if d_{B,C} ∈ B ∩ [n]^{t}; \\ (A ∪ \{d_{B,C}\}, B ∪ \{d_{B,C}\}, C\\{d_{B,C}\}), & if d_{B,C} ∈ C ∩ [n]; \\ (A ∪ \{d_{B,C} − n\}, B ∪ \{d_{B,C}\}, C\\{d_{B,C}\}), & if d_{B,C} ∈ C ∩ [n]^{t}. \end{cases} (8)

The function Ψ is well-defined and an involution on D. Moreover, if (A, B, C) ∈ D ∩ E, then Ψ((A, B, C)) ∈ D ∩ O; and vice versa. Therefore, we may conclude that |D ∩ E| = |D ∩ O|.

We have

|E| − |O| = |E ∩ X| − |O ∩ X|
= |E ∩ D| + |E ∩ E| − (|O ∩ D| + |O ∩ E|) (X = D ∪ E)
= |E ∩ E| − |O ∩ E|  (because |E ∩ D| = |O ∩ D|).

Therefore, we obtain

|E| − |O| = |E ∩ E| − |O ∩ E|.  (9)

From Eqns. (5) and (9), it follows that

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k}\binom{2n − 2k}{n − k} = |E ∩ E| − |O ∩ E|..  (10)

Exception:

Let (A, B, C) ∈ E. By Eq. (7), the set B ∪ C is balanced. Sets B and C are disjoint. Moreover, B ∪ φ(B)

and C ∪φ(C) are disjoint sets too. Then it follows that both sets B and C must be balanced. Hence integers |B| and |C| are even. Since |A|=|B| (by the definition of X), |A| is even and (A, B, C) ∈ E. Therefore, E ⊂ E.

Eq. (10) simplifies to

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

We have two cases:

Case (a): n is odd.

Since |B ∪ C| = n, it follows that the set B ∪ C is unbalanced and E = ∅. By Eq. (11), it follows that

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

as desired. Case (b): n is even.

We use the Chu-Vandermonde convolution formula:

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

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

Let us count the number of elements of the set E. The set E is equal to the set

\{(A, B_{1} ∪ B_{1}^{t}, C_{1} ∪ C_{1}^{t}) : A ⊂ [n], |A| even, B_{1} ⊂ A, |B_{1}| = \frac{|A|}{2}, C_{1} ⊂ [n]\A, |C_{1}| + |B_{1}| = \frac{n}{2}\}.

Obviously, it follows that |E| is equal to

|\{(A, B_{1}, C_{1}) : A ⊂ [n], |A| even, B_{1} ⊂ A, |B_{1}| = \frac{|A|}{2}, C_{1} ⊂ [n]\A, |C_{1}| + |B_{1}| = \frac{n}{2}\}|.

Clearly, there is a one-to-one correspondence between (A, B_{1}, C_{1}) and (B_{1} ∪ C_{1}, B_{1}, A\B_{1}). Therefore, |E| is equal to

|\{(B_{2}, B_{1}, A_{1}) : B_{2} ⊂ [n], |B_{2}| = \frac{n}{2}, B_{1} ⊂ B_{2}, A_{1} ⊂ [n]\B_{2}, |A_{1}| = |B_{1}|\}|.  (13)

Let k = |B_{1}|. By Eq. (13), it follows that

|E| = \binom{n}{\frac{n}{2}} ∑_{k=0}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\binom{\frac{n}{2}}{k}
= \binom{n}{\frac{n}{2}} ∑_{k=0}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\binom{\frac{n}{2}}{\frac{n}{2} − k}  (by symmetry)
= \binom{n}{\frac{n}{2}}^{2}  (by Eq. (12)).

We obtain

|E| = \binom{n}{\frac{n}{2}}^{2}.

By Eq. (11), it follows that

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

as desired. This completes the proof of Eq. (3).

4 Proof of Eq. (4)

Proof. The proof of Eq. (4) is similar to the proof of Eq. (3). Description:

Let X denote the set

{(A, B, C) : A ⊂ [n], B ⊂ A ∪ A^{t}, |B| = |A| − 1, C ⊂ [2n]\(A ∪ A^{t}), |A| + |C| = n}. For integers k, where 0 ≤ k ≤ n, we define the following sets X_{k}, as follows:

X_{k} = {(A, B, C) ∈ X : |A| = k}.

Obviously, X = ⋃_{k=0}^{n} X_{k} and |X_{k}| = \binom{n}{k}\binom{2k}{k−1}\binom{2n−2k}{n−k}. We have

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k − 1}\binom{2n − 2k}{n − k} = ∑_{k=0}^{n}(−1)^{k}|X_{k}| = |E| − |O|;  (14)

where

E = {(A, B, C) ∈ X : |A| is even} and O = {(A, B, C) ∈ X : |A| is odd}.

Involution:

Same as in Eq. (3). Let D, E, and Ψ be same as in Eqns. (6),(7), and (8) respectively. It is readily verified that the function Ψ is well-defined and an involution on D. Hence the equation

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k − 1}\binom{2n − 2k}{n − k} = |E ∩ E| − |O ∩ E|  (15)

holds. Exception:

Let (A, B, C) ∈ E. By Eq. (7), the set B ∪ C is balanced. As before, both sets B and C must be balanced. Thus, integers |B| and |C| are even. Since |A|=|B| + 1 (by the new definition of X), |A| is odd and (A, B, C) ∈ O. Therefore, E ⊂ O. Eq. (15) simplifies to

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

We have two cases: Case (a): n is even.

Since |B ∪ C| = n − 1, |B ∪ C| is odd. It follows that the set B ∪ C is unbalanced and E = ∅. By Eq. (16), it follows that

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

as desired.

Case (b): n is odd.

Again, we use Eq. (12). Let us count the number of elements of the set E.

The set E is equal to the set

{(A, B_{1} ∪ B_{1}^{t}, C_{1} ∪ C_{1}^{t}) :

A ⊂ [n], |A| odd, B_{1} ⊂ A, |B_{1}| = \frac{|A| − 1}{2}, C_{1} ⊂ [n]\A, |C_{1}| + |B_{1}| = \frac{n − 1}{2}\}.

Obviously, |E| is equal to

|\{(A, B_{1}, C_{1}) : A ⊂ [n], |A| odd, B_{1} ⊂ A, |B_{1}| = \frac{|A| − 1}{2}, C_{1} ⊂ [n]\A, |C_{1}| + |B_{1}| = \frac{n − 1}{2}\}|.

Clearly, there is one-to-one correspondence between (A, B_{1}, C_{1}) and (B_{1} ∪ C_{1}, B_{1}, A\B_{1}). Therefore, |E| is equal to

|\{(B_{2}, B_{1}, A_{1}) : B_{2} ⊂ [n], |B_{2}| = \frac{n − 1}{2}, B_{1} ⊂ B_{2}, A_{1} ⊂ [n]\B_{2}, |A_{1}| = |B_{1}| + 1\}|. (17)

Let k = |B_{1}|. By Eq. (17), it follows that

|E| = \binom{n}{\frac{n−1}{2}} ∑_{k=0}^{\frac{n−1}{2}} \binom{\frac{n−1}{2}}{k}\binom{\frac{n+1}{2}}{k + 1}

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

= \binom{n}{\frac{n−1}{2}}^{2}  (by Eq. (12)).

Thus we have shown

|E| = \binom{n}{\frac{n−1}{2}}^{2}.

By Eq. (16), it follows that

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

as desired. This completes the proof of Eq. (4).

5 Proof of Theorem 1

Proof. Eq. (1) directly follows from Eqns. (3),(4), and from the relation [4, p. 106] C_{k} = \binom{2k}{k} − \binom{2k}{k−1}.

Let us prove Eq. (2). By Eq. (1), it follows that

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

Changing k to 2n − k, we obtain that

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

Now we use a lesser known identity on the Catalan numbers:

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

Eq. (18) is a special case [5, p. 8] of the following identity:

C_{k}\binom{2n − 2k}{n − k} + \binom{2k}{k}C_{n−k} = (n + 2)C_{k}C_{n−k}.

We have

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

2(n + 1) ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}C_{k}C_{2n−k} = 2\binom{2n}{n}^{2} (by Eq. (18))

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

The last equation above proves Eq. (2). This completes the proof of Theorem 1.

6 Conclusion

Let n, α, β be non-negative integers. By using the same idea from proofs of Eqns. (3) and (4), we can conclude that

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{2k}{k − α}\binom{2n − 2k}{n − k − β} = \begin{cases}0, if n and α + β are of opposite parity; \\ (−1)^{α}\binom{n}{\frac{n−α−β}{2}}\binom{n}{\frac{n−α+β}{2}}, otherwise. \end{cases} (19)

7 Acknowledgments

I would like to thank my teachers Vanja Vujić and Ivana Božičković for proofreading this paper. Also I would like to thank the referee for useful suggestions.

References

[1] A. T. Benjamin and J. J. Quinn, An alternate approach to alternating sums: a method to DIE for, College Math. J. 39 (2008), 191–201.

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

[3] H. W. Gould and J. Quaintance, Combinatorial identities: Table I: intermediate techniques for summing finite series, preprint, 2010. Available at https://www.math.wvu.

   edu/~gould/Vol.4.PDF,

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

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

[6] G. V. Nagy, A combinatorial proof of Shapiro’s Catalan convolution, Adv. in Appl. Math. 50 (2012) 391–396.

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

[8] M. Z. Spivey, A combinatorial proof for the alternating convolution of the central binomial coefficients, Amer. Math. Monthly 121 (2014), 537–540.

[9] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2010 Mathematics Subject Classification: Primary 05A19 ; Secondary 05A10. Keywords: Catalan number, central binomial coefficient, combinatorial proof, method of involution, binomial coefficient identity.

Received May 5 2019; revised versions received May 13 2019; May 26 2019; November 9 2019. Published in Journal of Integer Sequences, November 11 2019.

Return to Journal of Integer Sequences home page.