A Proof of a Famous Identity Concerning the Convolution of the Central Binomial Coefficients

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

                       jnmikic@gmail.com

Abstract

We give an elementary proof of a famous binomial identity by using recurrence relations and telescoping. We also prove the alternating version of that identity and one of its generalizations.

1 Introduction

We consider a famous identity concerning the convolution of the central binomial coefficients:

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

where n is a nonnegative integer.

The identity (1) can be easily proved with help of generating functions (see [9, Exercises 1.2.c, 1.4.a] and [6, Example 4.3]). Also, there are many combinatorial proofs of Eq. (1). For example, Sved [10] gave a proof using a path-counting argument, and De Angelis [1] gave another by considering signed permutations. Petkovšek, Wilf, and Zeilberger gave a proof using the WZ method [7]. Chang and Xu [2] gave a probabilistic proof of a generalization of Eq. (1). Duarte and Guedes de Oliveira [4] gave an elementary proof of a different generalization of Eq. (1); their proof relies on the inclusion-exclusion principle. The same authors [3] also gave a combinatorial proof.

In this paper we give an elementary proof of Eq. (1) by using recurrence relations and telescoping. We consider the main sum ∑_{k=0}^{n} \binom{2k}{k}\binom{2(n−k)}{n−k} (note that this sum is the left-hand side of (1)), the auxiliary sum ∑_{k=0}^{n}(n − k)\binom{2k}{k}\binom{2(n−k)}{n−k}, and we show that there is a close relationship between these two sums.

More precisely, we derive two simple recurrence relations for these two sums, and we obtain a recurrence relation for the main sums. We can evaluate the main sum by telescoping. In this construction, we only use two well-known identities; namely, \binom{2n}{n} = 2\binom{2n−1}{n} and k\binom{n}{k} = n\binom{n−1}{k−1}.

We also prove the alternating version of Eq. (1):

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

Finally, we will use this idea to prove a generalization by Chang and Xu [2]:

∑_{i_{1}+i_{2}+···+i_{t}=n_{i_{1}≥0,...,i_{t}≥0}} \binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}} = \begin{cases}4^{n}\binom{n+ \frac{t}{2} −1}{n}, & if t is even; \\ \begin{matrix}( & {2n+t−1 \atop 2n} & ) \\ ( & {n+ \frac{1}{2} (t−1) \atop n} & ) \end{matrix}\binom{2n}{n}, & if t is odd. \end{cases}  (3)

In the above identity, t is a positive integer.

The identities (2) and (3) can be proved by using generating functions (see [8] for a combinatorial proof of (2) and [5] for a proof of (3)).

We end this paper with some interesting identities which can be proved with our formulas for auxiliary sums.

Throughout the paper, ℕ denotes the set of positive integers, and ℕ_{0} denotes the set of nonnegative integers. For n ∈ ℕ we let [n] denote the set {1, 2, …, n}.

2 The proof of Eq. (1)

Proof. Let n ∈ ℕ_{0}. We let T (n) denote the left-hand side of Eq. (1), i.e.,

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

We introduce the auxiliary sum P (n) as follows

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

Obviously, we have that

P (n) = \frac{nT (n)}{2}.  (4)

Let n ∈ ℕ. Since we know that the last term of P (n) is equal to zero, we have

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

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

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

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

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

From the last equation above, we conclude that

P (n) = 4P (n − 1) + 2T (n − 1), n ∈ ℕ.  (5)

From Equations (4) and (5), it follows that

\frac{nT (n)}{2} = \frac{4(n − 1)T (n − 1)}{2} + 2T (n − 1) = 2nT (n − 1).

Therefore

T (n) = 4T (n − 1); n ∈ ℕ.  (6)

Using telescoping and the fact T (0) = 1, Equation (6) becomes T (n) = 4^{n}, n ∈ ℕ_{0}.

3 The proof of Eq. (2)

Proof. Let n ∈ ℕ_{0}. We let Q(n) denote the left-hand side of Eq. (2), i.e.,

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

It is easy to note that

Q(2n + 1) = 0.  (7)

We consider the auxiliary sum H(n) as follows

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

Obviously,

H(2n) = nQ(2n).  (8)

Let n ∈ ℕ. If we continue in a similar manner, as we do in the second part of the previous proof, then it follows that

H(n) = 4H(n − 1) + 2Q(n − 1), n ∈ ℕ.  (9)

From relations (7) and (9), it follows that

H(2n) = 4H(2n − 1) + 2Q(2n − 1) = 4H(2n − 1).  (10)

Also, from (9), we obtain that

H(2n − 1) = 4H(2n − 2) + 2Q(2n − 2);  (11)

and relations (10) and (11) give us that

H(2n) = 16H(2n − 2) + 8Q(2n − 2).  (12)

Finally, from (8) and (12), it follows that

nQ(2n) = 16(n − 1)Q(2n − 2) + 8Q(2n − 2) = 8(2n − 1)Q(2n − 2),

i.e.,

Q(2n) = \frac{8(2n − 1)}{n} · Q(2n − 2), n ∈ ℕ.  (13)

By using telescoping and the fact Q(0) = 1, from (13) we obtain that

Q(2n) = \frac{8^{n}(2n − 1)!!}{n!}.

The equation above can be transformed as follows:

Q(2n) = \frac{8^{n}(2n − 1)!!}{n!} = \frac{8^{n}(2n − 1)!!}{n!} · \frac{2^{n}n!}{2^{n}n!} = \frac{4^{n}(2n − 1)!!(2n)!!}{(n!)^{2}} = \frac{4^{n}(2n)!}{(n!)^{2}} = 4^{n}\binom{2n}{n}.

4 The proof of Eq. (3)

Proof. Let n ∈ ℕ_{0} and t ∈ ℕ. We let S(n, t) denote the left-hand side of (3), i.e.,

S(n, t) = ∑_{i_{1}+i_{2}+···+i_{t}=n_{i_{1}≥0,...,i_{t}≥0}} \binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}.

We introduce the auxiliary sum P (n, t) as follows:

P (n, t) = ∑_{i_{1}+i_{2}+···+i_{t}=n_{i_{1}≥0,...,i_{t}≥0}} i_{1}\binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}.

Because of symmetry, P (n, t) is also equal to

P (n, t) = ∑_{i_{1}+i_{2}+···+i_{t}=n_{i_{1}≥0,...,i_{t}≥0}} i_{k}\binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}, k ∈ [t].

It is easy to obtain that

P (n, t) = \frac{nS(n, t)}{t}.  (14)

For arbitrary n ∈ ℕ we have

P (n, t) = ∑_{i_{1}+i_{2}+···+i_{t}=n_{i_{1}>0,i_{2}≥0,...,i_{t}≥0}} i_{1}\binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}

= 2 · ∑_{(i_{1}−1)+i_{2}+···+i_{t}=n−1_{i_{1}−1≥0,i_{2}≥0,...,i_{t}≥0}} i_{1}\binom{2i_{1} − 1}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}

= 2 · ∑_{(i_{1}−1)+i_{2}+···+i_{t}=n−1_{i_{1}−1≥0,i_{2}≥0,...,i_{t}≥0}}(2i_{1} − 1)\binom{2(i_{1} − 1)}{i_{1} − 1}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}

= 2 · ∑_{(i_{1}−1)+i_{2}+···+i_{t}=n−1_{i_{1}−1≥0,i_{2}≥0,...,i_{t}≥0}}(2(i_{1} − 1) + 1)\binom{2(i_{1} − 1)}{i_{1} − 1}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}

= 4 · ∑_{(i_{1}−1)+i_{2}+···+i_{t}=n−1_{i_{1}−1≥0,i_{2}≥0,...,i_{t}≥0}}(i_{1} − 1)\binom{2(i_{1} − 1)}{i_{1} − 1}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}+

2 · ∑_{(i_{1}−1)+i_{2}+···+i_{t}=n−1_{i_{1}−1≥0,i_{2}≥0,...,i_{t}≥0}} \binom{2(i_{1} − 1)}{i_{1} − 1}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}.

We conclude that

P (n, t) = 4P (n − 1, t) + 2S(n − 1, t), n ∈ ℕ.  (15)

From relations (14) and (15), it follows that

\frac{nS(n, t)}{t} = 4 · \frac{(n − 1)S(n − 1, t)}{t} + 2S(n − 1, t)
= 4(n − 1)S(n − 1, t) + 2tS(n − 1, t)
= 2(2(n − 1) + t)S(n − 1, t),

and so

S(n, t) = \frac{2(2(n − 1) + t)}{n} · S(n − 1, t), n ∈ ℕ.  (16)

By using telescoping and the fact S(0, t) = 1, Equation (16) becomes

S(n, t) = 2^{n} · \frac{(2n − 2 + t) · (2n − 4 + t) ⋯ (2 + t) · t}{n!}, n ∈ ℕ.  (17)

Now we have two cases: Case (a) The number t is even: t = 2t_{1}, where t_{1} ∈ ℕ. In that case relation (17) becomes

S(n, 2t_{1}) = 4^{n} · \frac{(n − 1 + t_{1}) · (n − 2 + t_{1}) ⋯ (1 + t_{1}) · t_{1}}{n!} , n ∈ ℕ
S(n, 2t_{1}) = 4^{n} · \frac{(n − 1 + t_{1})!}{n! · (t_{1} − 1)!}.

So

S(n, 2t_{1}) = 4^{n} · \binom{n + t_{1} − 1}{n}.  (18)

This proves the first case of (3).

Case (b) The number t is odd: t = 2t_{1} + 1, where t_{1} ∈ ℕ_{0}. In this case, from (17) we obtain

S(n, 2t_{1} + 1) = 2^{n} · \frac{(2n − 1 + 2t_{1})(2n − 3 + 2t_{1}) ⋯ (1 + 2t_{1})}{n!}, n ∈ ℕ.  (19)

Equation (19) can be transformed as follows

S(n, 2t_{1} + 1) = 2^{n} · \frac{(2n + 2t_{1})(2n − 1 + 2t_{1}) ⋯ (1 + 2t_{1})}{n!(2n + 2t_{1})(2n − 2 + 2t_{1}) ⋯ (2 + 2t_{1})}

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

= \frac{(2n + 2t_{1})(2n − 1 + 2t_{1}) ⋯ (1 + 2t_{1}) · (2t_{1})! · t_{1}!}{n! · (n + t_{1})(n + t_{1} − 1) ⋯ (1 + t_{1}) · t_{1}! · (2t_{1})!}

= \frac{(2n + 2t_{1})! · t_{1}!}{n! · (n + t_{1})! · (2t_{1})!}

= \frac{(2n + 2t_{1})!}{(2n)! · (2t_{1})!} · \frac{(2n)! · t_{1}!}{n! · (n + t_{1})!}

= \binom{2n + 2t_{1}}{2n} · \frac{(2n)!}{(n!)^{2}} · \frac{t_{1}! · n!}{(n + t_{1})!}

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

This proves the second case of (3).

5 Conclusions

We notice that recurrences (9) and (15) are same as Equation (5). This is not a coincidence. Let f be a function of k, which is independent of n. We denote the main sum S(n) as

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

and the auxiliary sum P (n) as

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

Then, for any n ∈ ℕ, the equation

P (n) = 4P (n − 1) + 2S(n − 1)

holds.

By using auxiliary sums, we can prove the important identity

∑_{k=0}^{n} \binom{2k}{k}\binom{2(n − k)}{n − k}\frac{1}{k + r} = \frac{\binom{2n+2r}{n+r}}{\binom{2r}{r} · r} ; r ∈ ℕ.

Recall that C_{k} = \frac{1}{k+1} \binom{2k}{k} are the Catalan numbers. When r = 1, the last identity above becomes

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

It is easy to note that

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

From the last two above identities, we have

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

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

and so

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

From the last identity above, Segner’s recurrence relation [6] for C_{n+1} follows:

∑_{k=0}^{n} C_{k} · C_{n−k} = C_{n+1}.

Therefore, we can prove Segner’s recurrence relation by using auxiliary sums.

Using auxiliary sums, we can prove the companion binomial theorem

∑_{k=0}^{n} \binom{a + k}{k}\binom{b + n − k}{n − k} = \binom{a + b + n + 1}{n}.

We also can derive new formulas (to my knowledge), such as

∑_{k=0}^{n} k^{2}\binom{2k}{k}\binom{2(n − k)}{n − k} = \frac{4^{n−1} · n · (3n + 1)}{2};

or

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

Remark 1. Marko Petkovšek, Herbert Wilf, and Doron Zeilberger also give proofs of binomial identities via recurrence relations and telescoping (see [7]). However, the technique of auxiliary sums is different from their techniques.

We consider recurrence relations between auxiliary sums and main sums. We do not consider recurrence relations between summands of the main sum. This is the main difference from Sister Celine’s method.

Our telescoping is quite different, especially, from the telescoping in the WZ method. We use telescoping in order to calculate the main sum, not only to prove an identity.

6 Acknowledgments

I wish to thank to my parents. I am very grateful to my professor Duško Jojić. Also I thank the referee for valuable comments.

References

[1] V. De Angelis, Pairings and signed permutations, Amer. Math. Monthly 113 (2006), 642-644.

[2] G. Chang and C. Xu, Generalization and probabilistic proof of a combinatorial identity, Amer. Math. Monthly 118 (2011), 175-177.

[3] R. Duarte and A. G. de Oliveira, A famous identity of Hajós in terms of sets, J. Integer Seq. 17 (2014), Article 14.9.1.

[4] R. Duarte and A. G. de Oliveira, A short proof of a famous combinatorial identity,

   2013. Preprint available at http://arxiv.org/abs/1307.6693.

[5] R. Duarte and A. G. de Oliveira, New developments of an old identity, 2013. Preprint

   available at http://arxiv.org/abs/1203.5424.

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

[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. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 1997.

[10] M. Sved, Counting and recounting: the aftermath, Math. Intelligencer 6 (1984), 44–45.

2010 Mathematics Subject Classification: Primary 05A10 ; Secondary 05A19. Keywords: central binomial coefficient, recurrence equation, telescoping, auxiliary sum.

Received April 8 2016; revised version received June 18 2016. Published in Journal of Integer Sequences, July 6 2016.

Return to Journal of Integer Sequences home page.