Note on the Convolution of Binomial Coefficients

Rui Duarte

Center for Research and Development in Mathematics and Applications

Department of Mathematics University of Aveiro Portugal

                     rduarte@ua.pt

António Guedes de Oliveira CMUP and Department of Mathematics Faculty of Sciences University of Porto Portugal

                    agoliv@fc.up.pt

Abstract

We prove that, for every integer a, real numbers k and ℓ, and nonnegative integers n, i and j,

∑_{i+j=n} \binom{a i + k − ℓ}{i}\binom{a j + ℓ}{j} = ∑_{i+j=n} \binom{a i + k}{i}\binom{a j}{j},

by presenting explicit expressions for its value. We use the identity to generalize a recent result of Chang and Xu, and end the paper by presenting, in explicit form, the ordinary generating function of the sequence \{\binom{2n+k}{n}\}_{n=0}^{∞}, where k ∈ ℝ.

1 Introduction

We consider the sequence \{\binom{a n+k}{n}\}_{n=0}^{∞}, where, following the notation of [11], for every real ℓ and every nonnegative integer i, (ℓ)_{i} = ℓ(ℓ − 1) ⋯ (ℓ − i + 1) is the falling factorial and \binom{ℓ}{i} = \frac{(ℓ)_{i}}{i!} . Temporarily, we consider k = 0 and take the convolution of this sequence with itself, defined by C_{a}(n) = ∑_{i+j=n} \binom{a i}{i}\binom{a j}{j}.

When a = 2, the former is sequence \underline{A000984} of [10], of the central binomial coefficients, and the latter is sequence \underline{A000302}, of the powers of 4. In other words,

C_{2}(n) = ∑_{i+j=n} \binom{2 i}{i}\binom{2 j}{j} = 4^{n} .  (1)

In fact, we can prove directly (1) using, similarly to what we do here (see [4] for details), the inclusion-exclusion principle after using identity (4) for a = 2, that is, the fact that

∑_{i+j=n} \binom{2i}{i}\binom{2j}{j} = ∑_{i+j=n} \binom{2i − ℓ}{i}\binom{2j + ℓ}{j} .

Note that

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

For another identity, define as usual [n] = {1, …, n} for any natural number n and consider the collection of the subsets of [2n] with more than n elements and with the same (n + 1)-th element, p, say. Note that p = n + 1 + i for some i = 0, …, n − 1 and that there are \binom{n+i}{n} 2^{n−i−1} subsets in the collection. It follows that the number of all subsets of [2n] is

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

We generalize these identities, namely (2) and (3). When a = 3 and a = 4, we have sequences \underline{A006256} and \underline{A078995} of [10], and no such simple formulas for C_{3}(n) and C_{4}(n) are known as in case a = 2. For these sequences, we obtain, for every real ℓ,

∑_{i+j=n} \binom{3i}{i}\binom{3j}{j} = ∑_{i+j=n} 2^{i}\binom{3n + 1}{j} = ∑_{i+j=n} 3^{i}\binom{2n + j}{j} = ∑_{i+j=n} \binom{3i − ℓ}{i}\binom{3j + ℓ}{j} ,

∑_{i+j=n} \binom{4i}{i}\binom{4j}{j} = ∑_{i+j=n} 3^{i}\binom{4n + 1}{j} = ∑_{i+j=n} 4^{i}\binom{3n + j}{j} = ∑_{i+j=n} \binom{4i − ℓ}{i}\binom{4j + ℓ}{j} .

More generally, we obtain the following theorem.

Theorem 1. For every nonnegative integers i, j and n, and for every real numbers k and ℓ,

∑_{i+j=n} \binom{a i + k − ℓ}{i}\binom{a j + ℓ}{j} = ∑_{i+j=n} \binom{a i + k}{i}\binom{a j}{j}  (4)

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

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

where we take 0^{0} = 1.

Gould [5] proves (4) (together with the Rothe-Hagen identity) using generating functions, and asks for proofs “using finite series, the method of finite differences, or otherwise”. So, part of this paper can be seen as an extension of a recent paper by Chu [3].

Coming back to the case where a = 2, we consider the convolution of more than two copies of the sequence of central binomial coefficients: given integers n ≥ 0 and t > 0, define

P_{t}(n) = ∑_{i_{1}+···+i_{t}=n} \binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}}.

where i_{1}, …, i_{t} are nonnegative integers. Recently, Chang and Xu showed [2], with a probabilistic proof, that P_{t}(n) depends only on n and t. We give here a proof of combinatorial nature of this fact and obtain a generalization that also includes (1) as a special case. Namely, we prove the following theorem, that is based on the results of Chang and Xu [2].

Theorem 2. Let ℓ_{1}, …, ℓ_{t} be any real numbers such that ℓ_{1} + ⋯ + ℓ_{t} = 0. Then

∑_{i_{1}+···+i_{t}=n} \binom{2i_{1} + ℓ_{1}}{i_{1}}\binom{2i_{2} + ℓ_{2}}{i_{2}} ⋯ \binom{2i_{t} + ℓ_{t}}{i_{t}} = 4^{n}\binom{n + \frac{t}{2} − 1}{n} ,  (7)

where i_{1}, …, i_{t} are nonnegative integers.

Finally, in Section 4 we obtain formulas for the generating functions of the sequences involved in these identities.

2 General case

For the proof of Theorem 1 we need some technical results.

Lemma 3. Let, for any real ℓ and integers a and n such that n ≥ 0,

S_{a,ℓ}(n) = ∑_{i=0}^{n}(−1)^{i}\binom{ℓ − (a − 1)i}{i}\binom{ℓ − a i}{n − i} .

Then

∑_{p=0}^{n} \binom{n}{p} S_{a,ℓ}(p) = S_{a+1,ℓ+n}(n) .

Proof.

∑_{p=0}^{n} \binom{n}{p} S_{a,ℓ}(p) = ∑_{i=0}^{n} [(−1)^{i}\binom{ℓ − (a − 1)i}{i} ∑_{p=i}^{n} \binom{ℓ − a i}{p − i}\binom{n}{p}]

= ∑_{i=0}^{n} [(−1)^{i}\binom{ℓ − (a − 1)i}{i} ∑_{p=i}^{n} \binom{ℓ − a i}{ℓ − (a − 1)i − p}\binom{n}{p}]

= ∑_{i=0}^{n}(−1)^{i}\binom{ℓ − (a − 1)i}{i}\binom{ℓ + n − a i}{ℓ − (a − 1) i}

= ∑_{i=0}^{n}(−1)^{i}\binom{(ℓ + n) − a i}{i , n − i , ℓ − ai}

= ∑_{i=0}^{n}(−1)^{i}\binom{(ℓ + n) − a i}{i}\binom{(ℓ + n) − (a + 1) i}{n − i} ,

where we use Vandermonde’s convolution in the third equality.

Lemma 4. With the notation of the previous lemma,

S_{a,ℓ}(n) = (a − 1)^{n}.

First proof. First note that we may assume that ℓ is a natural number, since S_{a,ℓ}(n) is a polynomial in ℓ, and thus is constant. Now, suppose that fixed a, there exist x such that for all ℓ and p, S_{a,ℓ}(p) = x^{p}. Then, from Lemma 3 it follows that S_{a+1,ℓ+n}(n) = (1 + x)^{n}. Hence, all we must prove is that S_{a,ℓ}(n) = 0 when a = 1 and ℓ ∈ ℕ.

For this purpose, define A as the set of n-subsets of the set [ℓ] = {1, 2, …, ℓ} and let A_{i} be the set of elements of A that do not contain i, for i ∈ [ℓ]. Then, on the one hand, |A_{1} ∪ ⋯ ∪ A_{ℓ}| = \binom{ℓ}{p} and on the other hand, by the inclusion-exclusion principle,

|A_{1} ∪ ⋯ ∪ A_{ℓ}| = ∑_{i=1}^{ℓ}(−1)^{i+1}( ∑_{1≤j_{1}<···<j_{i}≤ℓ} |A_{j_{1}} ∩ ⋯ ∩ A_{j_{i}}|) .

The proof is completed by noting that, for every integers j_{1}, …, j_{i} such that 1 ≤ j_{1} < ⋯ < j_{i} ≤ p, |A_{j_{1}} ∩ ⋯ ∩ A_{j_{i}}| = \binom{ℓ−i}{n−i}.

Second proof. Notice first that, for any function f, we have by induction that

(Δ^{n}f)(x) = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}f(x + n − i)  (8)

where Δ is the forward-difference operator defined by (Δf)(x) = f(x + 1) − f(x), and Δ^{n} denotes the operator Δ applied successively n times. In addition, if f is a polynomial, the degree reduces each time we apply Δ and, if the degree of f is n, the left-hand side of (8) must be a constant which equals (n!)a_{n}, where a_{n} is the coefficient of x^{n} in f. In particular,

∑_{i=0}^{n}(−1)^{i}\binom{n}{i}f(n − i) = n!

if f is a monic polynomial of degree n.

Now, S_{a,ℓ}(n) can be rewritten as ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}\binom{ℓ−(a−1)i}{n}. If a = 1, the identity is clearly satisfied. When a ≠ 1, the identity can be written as

∑_{i=0}^{n}(−1)^{i}\binom{n}{i} (\frac{ℓ}{a − 1} − i) (\frac{ℓ − 1}{a − 1} − i) ⋯ (\frac{ℓ − (n − 1)}{a − 1} − i) = n! .

If f is the monic polynomial of degree n defined as

f(x) = (\frac{ℓ}{a − 1} − n + x) (\frac{ℓ − 1}{a − 1} − n + x) ⋯ (\frac{ℓ − (n − 1)}{a − 1} − n + x) ,

then clearly

∑_{i=0}^{n}(−1)^{i}\binom{n}{i}f(n − i) = (Δ^{n}f)(0) = n! ,

which proves the identity.

Lemma 5. Let n be a nonnegative integer and s and t be two real numbers. Then

\binom{s + t + 1}{n} = ∑_{i=0}^{n} \binom{s − i}{n − i}\binom{t + i}{i}.

First proof. Let F (n, i) = \binom{s−i}{s−n}\binom{t+i}{i} . By Zeilberger’s algorithm [7, 9], as implemented by Paule and Schorn [8] and by Krattenthaler [6], we know that T (n) = ∑_{i=0}^{n} F (n, i) verifies

(s + t + 1 − n) T (n) − (n + 1) T (n + 1) = 0,  (9)

which is also verified by T (n) = \binom{s+t+1}{n}, and for both it holds T (0) = 1. In fact, we can see that for every i with 0 ≤ i ≤ n + 1,

(s + t + 1 − n) F (n, i) − (n + 1) F (n + 1, i) = G(n, i + 1) − G(n, i)

with G(n, i) = i \binom{s+1−i}{s−n}\binom{t+i}{i}. Hence, (9) holds since F (n, n + 1) = G(n, n + 2) = G(n, 0) = 0.

Second proof. Since \binom{t+i}{i} = (−1)^{i}\binom{−t−1}{i} and by Vandermonde’s convolution,

∑_{i=0}^{n} \binom{s − i}{n − i}\binom{t + i}{i} = (−1)^{n} ∑_{i=0}^{n} \binom{−t − 1}{i}\binom{−s − 1 + n}{n − i}

= (−1)^{n}\binom{−t − s + n − 2}{n}

= \binom{t + s + 1}{n} .

Lemma 6. For all nonnegative integers i and n, and for all real numbers a and b,

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

Proof.

∑_{i=0}^{n} a^{n−i} \binom{(b − 1)n + k + i}{i} = ∑_{i=0}^{n} [∑_{j=0}^{n−i}(a − 1)^{n−j}\binom{n − i}{j}] \binom{(b − 1)n + k + i}{i}

= ∑_{j=0}^{n}(a − 1)^{n−j} [∑_{i=0}^{n−j} \binom{n − i}{n − j − i}\binom{((b − 1)n + k) + i}{i}] .

The result now follows from Lemma 5.

Proof of Theorem 1. Let 𝔖 = ∑_{i+j=n} \binom{a i+k−ℓ}{i}\binom{a j+ℓ}{j} = ∑_{i+j=n}(−1)^{i}\binom{ℓ−k′−(a−1)i}{i}\binom{a n+ℓ−a i}{j}, with k′ = k + 1. Then, by Vandermonde’s convolution,

𝔖 = ∑_{i+j=n} [(−1)^{i}\binom{ℓ − k′ − (a − 1)i}{i} ∑_{p+m=j} \binom{a n + k′}{p}\binom{ℓ − k′ − a i}{m}]

= ∑_{p=0}^{n} [\binom{a n + k′}{p} ∑_{i+m=n−p}(−1)^{i}\binom{ℓ − k′ − (a − 1)i}{i}\binom{ℓ − k′ − a i}{m}] .

Now, (5) follows immediately from Lemma 4 and (6) follows from (5) and Lemma 6.

We end this section with a problem based on a new result that, when we represent by \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix} the number \binom{n+k−1}{k} of k-multisets of elements of an n-set, can be formulated in the following elegant terms.

Theorem 7. For every real ℓ and every nonnegative integer n,

∑_{i=0}^{n}(−1)^{i} \begin{matrix}( \\ ( & {ℓ − a i \atop i} & ) \\ ) \end{matrix} \binom{ℓ − a i}{n − i} = a(a − 1)^{n−1}.

Proof. By Pascal’s rule,

∑_{i=0}^{n}(−1)^{i}\binom{ℓ − 1 − (a − 1)i}{i}\binom{ℓ − a i}{n − i} = ∑_{i=0}^{n}(−1)^{i}\binom{ℓ − (a − 1)i}{i}\binom{ℓ − a i}{n − i}

− ∑_{i=1}^{n}(−1)^{i}\binom{ℓ − (a − 1)i − 1}{i − 1}\binom{ℓ − a i}{n − i}

=S_{a,ℓ}(n) + S_{a,ℓ−a}(n − 1) .

Problem 8. Give a combinatorial proof of Theorem 7.

3 The case a = 2: on Chang & Xu generalization of the identity (1)

The main result of the article of Chang and Xu [2] is a generalization of (1) that we may write as

∑_{i_{1}+···+i_{t}=n} \binom{2i_{1}}{i_{1}}\binom{2i_{2}}{i_{2}} ⋯ \binom{2i_{t}}{i_{t}} = 4^{n}\binom{n + \frac{t}{2} − 1}{n}.  (10)

where i_{1}, …, i_{n} are (nonnegative) integers.

Let P_{t}(n) be the left-hand side of (10), as we defined before. We remark that P_{1}(n) = \binom{2n}{n} and, by (1), P_{2}(n) = 4^{n}. Note also that (10) can be obtained using induction and the

following lemma. Finally, we observe that 4^{n}\binom{n+ \frac{t}{2} −1}{n} = \begin{matrix}( & {2n+2k \atop 2n} & ) \\ ( & {n+k \atop n} & ) \end{matrix}\binom{2n}{n} = \begin{matrix}( & {2n+2k \atop n+k} & ) \\ ( & {2k \atop k} & ) \end{matrix}\binom{n+k}{n} when

t = 2k + 1.

Lemma 9. For every positive integer t and every nonnegative integer n,

P_{t+2}(n + 1) = P_{t}(n + 1) + 4 P_{t+2}(n)

Proof. In fact, P_{t+2}(n + 1) = ∑_{j=0}^{n+1} P_{2}(n + 1 − j)P_{t}(j) = P_{t}(n + 1) + 4 ∑_{j=0}^{n} 4^{n−j}P_{t}(j).

Now, we consider again (4), the first identity in Theorem 1. From this identity, as a clear consequence, we obtain, for every integer a, for every nonnegative integers t, n and i_{1}, i_{2}, …, i_{t} and for every real numbers k, k_{1}, k_{2}, …, k_{t} such that k = k_{1} + k_{2} + ⋯ + k_{t}, the following identity, which is also a clear consequence of statement (2) of Theorem 11:

∑_{i_{1}+···+i_{t}=n} \binom{a i_{1} + k}{i_{1}}\binom{a i_{2}}{i_{2}} ⋯ \binom{a i_{t}}{i_{t}} = ∑_{i_{1}+···+i_{t}=n} \binom{a i_{1} + k_{1}}{i_{1}}\binom{a i_{2} + k_{2}}{i_{2}} ⋯ \binom{a i_{t} + k_{t}}{i_{t}} .

Whence we obtain Theorem 2 as stated in Section 1.

4 Generating functions

In what follows, we denote by f^{(n)} the n-th derivative of a function f of one real variable, g(x) = ∑_{n≥0} \binom{2n}{n} x^{n} is the generating function of the central binomial coefficients and C(x) = ∑_{n≥0} \frac{1}{n+1} \binom{2n}{n} x^{n} is the generating function of the Catalan numbers. We remember that g(x) = \frac{1}{\sqrt{1−4x}} and C(x) = \frac{2}{1+\sqrt{1−4x}}. Note that g′ = 2g^{3} and C′ = g C^{2}. The following lemma can be easily proved by induction on n.

Lemma 10. For every real numbers t and ℓ and nonnegative integer n,

\frac{(g^{t})^{(n)}}{n!} = 4^{n}\binom{n + \frac{t}{2} − 1}{n}g^{t+2n},

\frac{(g C^{ℓ})^{(n)}}{n!} = ∑_{i=0}^{n} \binom{2n − i}{n − i}\binom{ℓ + i − 1}{i}g^{1+2n−i}C^{ℓ+i},

(C^{ℓ})^{(n+1)} = (ℓ g C^{ℓ+1})^{(n)} .

Now, by Lemma 5, we obtain immediately the following theorem. Note that the second statement is a particular case, but in explicit form, of an identity of Gould [5, p. 86 (9)], and that the third statement was proved by Catalan in 1876 [1, p. 62 and Errata].

Theorem 11. For every real numbers t and ℓ,

g(x)^{t} = ∑_{n≥0} 4^{n}\binom{n + \frac{t}{2} − 1}{n}x^{n},

g(x) C(x)^{ℓ} = ∑_{n≥0} \binom{2n + ℓ}{n}x^{n},

C(x)^{ℓ} = 1 + ∑_{n≥1} \frac{ℓ}{2n + ℓ}\binom{2n + ℓ}{n}x^{n} .

5 Acknowledgments

We warmly thank the referee for his careful reading of the text, and specially for offering us the second proof of Lemma 4 and of Lemma 5. We also thank Christian Krattenthaler for drawing our attention to an article of Gould [5], and the On-Line Encyclopedia of Integer Sequences [10], that was very useful throughout all work. The work of both authors was supported in part by the European Regional Development Fund through the program COMPETE - Operational Program Factors of Competitiveness (“Programa Operacional Factores de Competitividade”) and by the Portuguese government through FCT - Fundação para a Ciência e a Tecnologia, under the projects PEst-C/MAT/UI0144/2011 and PEst-C/MAT/UI4106/2011.

References

[1] E. C. Catalan, Mélanges Mathématiques, Vol. 2, F. Hayez, Bruxelles, 1887. Available at

   http://archive.org/details/mlangesmathm02catauoft .

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

[3] W. Chu, Elementary proofs for convolution identities of Abel and Hagen-Rothe. Electron. J. Combin. 17 (2010), Note 24.

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

   preprint, http://arxiv.org/abs/1307.6693.

[5] H. W. Gould, Some generalizations of Vandermonde’s convolution. Amer. Math. Monthly 63 (1956), 84–91.

[6] C. Krattenthaler, HYP/HYPQ, available at http://tinyurl.com/ld8dre8 .

[7] I. Nemes, M. Petkovšek, H. S. Wilf, and D. Zeilberger, How to do Monthly problems with your computer. Amer. Math. Monthly 104 (1997), 505–519.

[8] P. Paule and M. Schorn, The Paule/Schorn implementation of Gosper’s and Zeilberger’s

   algorithms, available at http://tinyurl.com/kbluqo4 .

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

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

   at http://oeis.org, 2011.

[11] R. Stanley, Enumerative Combinatorics, Volume 1, Cambridge University Press, 1997.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A10,05A15. Keywords: combinatorial identity, binomial coefficient, Vandermonde’s convolution, WZmethod.

(Concerned with sequences \underline{A000302}, \underline{A000984}, \underline{A006256}, and \underline{A078995}.)

Received February 8 2013; revised version received March 8 2013; July 26 2013; August 21 2013. Published in Journal of Integer Sequences, August 22 2013.

Return to Journal of Integer Sequences home page.