Note on the Convolution of Binomial Coefficients

23 11

Article 13.7.6

Journal of Integer Sequences, Vol. 16 (2013),

2 3 6 1

47

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

[email protected]

Ant´onio Guedes de Oliveira

CMUP and Department of Mathematics Faculty of Sciences

University of Porto Portugal [email protected]

Abstract

We prove that, for every integer a, real numbers kand ℓ, and nonnegative integers n,iandj,

X

i+j=n

a i+k−ℓ i

a j+ℓ j

= X

i+j=n

a i+k i

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 sequencen

2n+k n

o_∞

n=0, wherek∈R.

1 Introduction

We consider the sequence _{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

ℓ i

= ^(ℓ)_i!ⁱ. Temporarily, we consider k = 0 and take the convolution of this sequence with itself, defined by C_a(n) = P

i+j=n a i

i

_{a j}

j

.

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

C₂(n) = X

i+j=n

2i i

2j j

= 4ⁿ. (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

X

i+j=n

2i i

2j j

= X

i+j=n

2i−ℓ i

2j+ℓ j

. Note that

2C₂(n) = 2²ⁿ⁺¹ =

2n+1

X

i=0

2n+ 1 i

= 2

n

X

i=0

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 nelements 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

n+i n

2ⁿ⁻ⁱ⁻¹ subsets in the collection. It follows that the number of all subsets of [2n] is C₂(n) = 2²ⁿ= 2

n−1

X

i=0

2ⁿ⁻ⁱ⁻¹

n+i i

+

2n n

=

n

X

i=0

2ⁿ⁻ⁱ

n+i i

. (3)

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

X

i+j=n

3i i

3j j

= X

i+j=n

2ⁱ

3n+ 1 j

= X

i+j=n

3ⁱ

2n+j j

= X

i+j=n

3i−ℓ i

3j +ℓ j

, X

i+j=n

4i i

4j j

= X

i+j=n

3ⁱ

4n+ 1 j

= X

i+j=n

4ⁱ

3n+j j

= X

i+j=n

4i−ℓ i

4j +ℓ j

. More generally, we obtain the following theorem.

Theorem 1. For every nonnegative integersi, j andn, and for every real numbersk andℓ, X

i+j=n

a i+k−ℓ i

a j +ℓ j

= X

i+j=n

a i+k i

a j j

(4)

=

n

X

i=0

(a−1)ⁿ⁻ⁱ

a n+k+ 1 i

(5)

=

n

X

i=0

aⁿ⁻ⁱ

(a−1)n+k+i i

(6) where we take 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 integersn≥0 and t >0, define

Pt(n) = X

i1+···+i^t=n

2i₁ i₁

2i₂ i₂

· · · 2i_t

i_t

.

where i₁, . . . , i_t are nonnegative integers. Recently, Chang and Xu showed [2], with a prob- abilistic proof, that Pt(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 ℓ₁, . . . , ℓ_t be any real numbers such that ℓ₁+· · ·+ℓ_t= 0. Then X

i1+···+it=n

2i1+ℓ₁ i₁

2i2+ℓ₂ i₂

· · ·

2it+ℓ_t i_t

= 4ⁿ

n+₂^t −1 n

, (7)

where i₁, . . . , 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 Theorem1 we need some technical results.

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

n

X

i=0

(−1)ⁱ

ℓ−(a−1)i i

ℓ−a i n−i

.

Then

n

X

p=0

n p

S_a,ℓ(p) = S_a+1,ℓ+n(n). Proof.

n

X

p=0

n p

S_a,ℓ(p) =

n

X

i=0

"

(−1)ⁱ

ℓ−(a−1)i i

ⁿ X

p=i

ℓ−a i p−i

n p

#

=

n

X

i=0

"

(−1)ⁱ

ℓ−(a−1)i i

ⁿ X

p=i

ℓ−a i ℓ−(a−1)i−p

n p

#

=

n

X

i=0

(−1)ⁱ

ℓ−(a−1)i i

ℓ+n−a i ℓ−(a−1)i

=

n

X

i=0

(−1)ⁱ

(ℓ+n)−a i i , n−i , ℓ−ai

=

n

X

i=0

(−1)ⁱ

(ℓ+n)−a i i

(ℓ+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)ⁿ.

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 xsuch that for allℓand p, S_a,ℓ(p) = x^p. Then, from Lemma3it follows that S_a+1,ℓ+n(n) = (1 +x)ⁿ. Hence, all we must prove is that S_a,ℓ(n) = 0 when a= 1 andℓ ∈N.

For this purpose, define A as the set of n-subsets of the set [ℓ] = {1,2, . . . , ℓ} and let Ai be the set of elements of A that do not contain i, for i ∈ [ℓ]. Then, on the one hand,

|A1∪ · · · ∪ Aℓ|= _p^ℓ

and on the other hand, by the inclusion-exclusion principle,

|A₁∪ · · · ∪ Aℓ|=

ℓ

X

i=1

(−1)ⁱ⁺¹

X

1≤j1<···<ji≤ℓ

|Aj1∩ · · · ∩ Aji|

.

The proof is completed by noting that, for every integersj₁, . . . , j_i such that 1≤j₁ <· · ·<

j_i ≤p, |Aj1 ∩ · · · ∩ Aji|= _n^ℓ−₋ⁱ_i .

Second proof. Notice first that, for any function f, we have by induction that (∆ⁿf)(x) =

n

X

i=0

(−1)ⁱ n

i

f(x+n−i) (8)

where ∆ is the forward-difference operator defined by (∆f)(x) = f(x+ 1)−f(x), and ∆ⁿ 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, wherea_n is the coefficient ofxⁿ inf. In particular,

n

X

i=0

(−1)ⁱ n

i

f(n−i) =n!

if f is a monic polynomial of degree n. Now, S_a,ℓ(n) can be rewritten as Pn

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

n

. If a = 1, the identity is clearly satisfied. Whena 6= 1, the identity can be written as

n

X

i=0

(−1)ⁱ n

i

ℓ

a−1 −i ℓ−1 a−1 −i

· · ·

ℓ−(n−1) a−1 −i

=n!. Iff is the monic polynomial of degree n defined as

f(x) = ℓ

a−1−n+x ℓ−1

a−1 −n+x

· · ·

ℓ−(n−1)

a−1 −n+x

, then clearly

n

X

i=0

(−1)ⁱ n

i

f(n−i) = (∆ⁿf)(0) = n!, which proves the identity.

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

n

=

n

X

i=0

s−i n−i

t+i i

. First proof. Let F(n, i) = _s^s₋⁻_nⁱ _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) = Pn

i=0F(n, i) verifies (s+t+ 1−n)T(n)−(n+ 1)T(n+ 1) = 0, (9) which is also verified by T(n) = ^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 ^s+1_s ⁻ⁱ

−n

_t+i

i

. Hence, (9) holds since F(n, n+ 1) = G(n, n+ 2) = G(n,0) = 0.

Second proof. Since ^t+i_i

= (−1)^{i −t}_i⁻¹

and by Vandermonde’s convolution,

n

X

i=0

s−i n−i

t+i i

= (−1)ⁿ

n

X

i=0

−t−1 i

−s−1 +n n−i

= (−1)ⁿ

−t−s+n−2 n

=

t+s+ 1 n

.

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

n

X

i=0

aⁿ⁻ⁱ

(b−1)n+k+i i

=

n

X

i=0

(a−1)ⁿ⁻ⁱ

b n+k+ 1 i

. Proof.

n

X

i=0

aⁿ⁻ⁱ

(b−1)n+k+i i

=

n

X

i=0

"_n−i X

j=0

(a−1)^n−j

n−i j

#

(b−1)n+k+i i

=

n

X

j=0

(a−1)^n−j

"_n−j X

i=0

n−i n−j−i

(b−1)n+k +i i

# . The result now follows from Lemma 5.

Proof of Theorem 1. Let S = P

i+j=n

a i+k−ℓ i

_{a j+ℓ}

j

= P

i+j=n(−1)^{i ℓ−k′−}_i^(a−1)i _{a n+ℓ−a i}

j

, with k^′ =k+ 1. Then, by Vandermonde’s convolution,

S = X

i+j=n

"

(−1)ⁱ

ℓ−k^′−(a−1)i i

X

p+m=j

a n+k^′ p

ℓ−k^′−a i m

#

=

n

X

p=0

"

a n+k^′ p

X

i+m=n−p

(−1)ⁱ

ℓ−k^′−(a−1)i i

ℓ−k^′−a i m

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

We end this section with a problem based on a new result that, when we represent by

n k

the number ^n+k_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,

n

X

i=0

(−1)ⁱ

ℓ−a i i

ℓ−a i n−i

=a(a−1)ⁿ⁻¹.

Proof. By Pascal’s rule,

n

X

i=0

(−1)ⁱ

ℓ−1−(a−1)i i

ℓ−a i n−i

=

n

X

i=0

(−1)ⁱ

ℓ−(a−1)i i

ℓ−a i n−i

−

n

X

i=1

(−1)ⁱ

ℓ−(a−1)i−1 i−1

ℓ−a i n−i

=S_a,ℓ(n) +S_a,ℓ−a(n−1). Problem 8. Give a combinatorial proof of Theorem7.

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

X

i1+···+it=n

2i1

i₁

2i2

i₂

· · · 2it

i_t

= 4ⁿ

n+ ₂^t −1 n

. (10)

where i₁, . . . , i_n are (nonnegative) integers.

LetP_t(n) be the left-hand side of (10), as we defined before. We remark thatP₁(n) = ²ⁿ_n and, by (1), P₂(n) = 4ⁿ. Note also that (10) can be obtained using induction and the following lemma. Finally, we observe that 4^{n n+}_n^t2−1

= (^2n+2k2n ) (^n+kn )

2n n

= (^2n+2kn+k) (^2kk)

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) + 4P_t+2(n)

Proof. In fact,P_t+2(n+ 1) =Pn+1

j=0 P₂(n+ 1−j)Pt(j) =P_t(n+ 1) + 4Pn

j=04^n−jP_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₁, i₂, . . . , i_t and for every real numbers k, k₁, k₂, . . . , k_t such that k =k₁+k₂ +· · ·+k_t, the following identity, which is also a clear consequence of statement (2) of Theorem 11:

X

i1+···+it=n

a i₁+k i₁

a i₂ i₂

· · · a i_t

i_t

= X

i1+···+it=n

a i₁+k₁ i₁

a i₂+k₂ i₂

· · ·

a i_t+k_t i_t

. Whence we obtain Theorem2 as stated in Section 1.

4 Generating functions

In what follows, we denote by f⁽ⁿ⁾ the n-th derivative of a function f of one real variable, g(x) =P

n≥0 2n

n

xⁿis the generating function of the central binomial coefficients andC(x) = P

n≥0 1 n+1

2n n

xⁿ is the generating function of the Catalan numbers. We remember that g(x) = ^√₁¹_−4x andC(x) = ₁₊^√2_1−4x. Note thatg^′ = 2g³ and C^′ =g C². The following lemma can be easily proved by induction on n.

Lemma 10. For every real numbers t and ℓ and nonnegative integer n, (g^t)⁽ⁿ⁾

n! = 4ⁿ

n+₂^t −1 n

g^t+2n, g C^ℓ(n)

n! =

n

X

i=0

2n−i n−i

ℓ+i−1 i

g¹⁺²ⁿ⁻ⁱ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=X

n≥0

4ⁿ

n+₂^t −1 n

xⁿ, g(x)C(x)^ℓ =X

n≥0

2n+ℓ n

xⁿ, C(x)^ℓ = 1 +X

n≥1

ℓ 2n+ℓ

2n+ℓ n

xⁿ.

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 In- teger 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¸c˜ao para a Ciˆencia e a Tecnologia, under the projects PEst-C/MAT/UI0144/2011 and PEst- C/MAT/UI4106/2011.

References

[1] E. C. Catalan,M´elanges Math´ematiques, 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. Elec- tron. 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 athttp://tinyurl.com/ld8dre8 .

[7] I. Nemes, M. Petkovˇsek, 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 athttp://tinyurl.com/kbluqo4 .

[9] M. Petkovˇsek, 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 athttp://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, WZ- method.

(Concerned with sequences A000302, A000984,A006256, and A078995.)

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

Return to Journal of Integer Sequences home page.