A Generalization of the Chu-Vandermonde Convolution and some Harmonic Number Identities 7 1 0 M.J. Kronenburg 2 r a M Abstract AgeneralizationoftheChu-Vandermondeconvolutionispresentedandproved 7 withtheintegralrepresentationmethod. Thisidentitycanbetransformedinto 2 anotheridentity,whichhasasspecialcasestwoknownidentities. Anotheriden- tity that is closely related to this identity is presented and proved. Some cor- ] O respondingharmonicnumberidentitiesarederived,whichhaveasspecialcases C someknownharmonicnumberidentities. Foronecombinatorialsumarecursion formula is derived and used to compute a few examples. . h t Keywords: binomial coefficient, combinatorial identities, harmonic number. a MSC 2010: 05A10, 05A19 m [ 1 A Generalization of the Chu-Vandermonde 2 v Convolution 8 6 The following theorem is a generalization of the Chu-Vandermonde convolution. 7 2 Theorem 1.1. 0 1. (cid:88)n (cid:18)a(cid:19)(cid:18) b (cid:19)(cid:18)k(cid:19)(cid:18)n−k(cid:19) (cid:18)a+b−c−d(cid:19)(cid:18)a(cid:19)(cid:18)b(cid:19) 0 = (1.1) k n−k c d n−c−d c d 7 k=0 1 : Proof. Applying the trinomial revision identity [10, 11, 13] to the summand twice, v the identity simplifies to: i X n (cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) r (cid:88) a−c b−d a+b−c−d a = (1.2) k−c n−d−k n−c−d k=0 Usingtheintegralrepresentationmethodforcombinatorialsums[4,5], thisbecomes: 1 (cid:88)∞ (1+x)a−c (1+y)b−d Res Res x xk−c+1 y yn−d−k+1 k=0 (1+x)a−c(1+y)b−d (cid:88)∞ (cid:16)y(cid:17)k =Res Res x y x−c+1yn−d+1 x k=0 (1+x)a−c(1+y)b−dxc−1 =Res Res x y yn−d+1(1−y/x) (1.3) (1+x)a−c(1+y)b−dxc =Res Res y x yn−d+1(x−y) (1+y)a+b−c−d =Res y yn−c−d+1 (cid:18) (cid:19) a+b−c−d = n−c−d Forthisidentity,thelowerlimitofthesummationmaybereplacedbymax(n−b,c) and the upper limit by min(a,n−d). The special case c=d=0 reduces to the Chu- Vandermonde convolution: n (cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:88) a b a+b = (1.4) k n−k n k=0 and the special case d = 0 was already known in literature [8]. The special case a=b=n reduces to: (cid:88)n (cid:18)n(cid:19)2(cid:18)k(cid:19)(cid:18)n−k(cid:19) (cid:18)2n−c−d(cid:19)(cid:18)n(cid:19)(cid:18)n(cid:19) = (1.5) k c d n c d k=0 The following identity replaces a binomial coefficient by its symmetry equivalent [10, 11, 13]: (cid:18) (cid:19) (cid:18) (cid:19) n −n+k−1 =(−1)k (1.6) k k Replacing a by a−p and b by b−q, and using (1.6), and then taking a = b = −1, the identity transforms to: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+k q+n−k k n−k n+p+q+1 p+c q+d = (1.7) p q c d n−c−d c d k=0 The special case c=d=0 reduces to [6, 8, 16]: n (cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:88) p+k q+n−k n+p+q+1 = (1.8) p q n k=0 2 and the special case p=q =0 reduces to [8, 10, 11, 15]: n (cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:88) k n−k n+1 = (1.9) c d c+d+1 k=0 Another theorem that is closely related to theorem 1.1 is the following. Theorem 1.2. min(a,b−m)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k m+k a+b−c−d a b = (1.10) k m+k c d m+a−d c d k=0 Proof. Applying the trinomial revision identity [10, 11, 13] to the summand twice, the identity simplifies to: min(a,b−m)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:88) a−c b−d a+b−c−d = (1.11) k−c k+m−d m+a−d k=0 Usingtheintegralrepresentationmethodforcombinatorialsums[4,5], thisbecomes: (cid:88)∞ (1+x)a−c (1+y)b−d Res Res x xk−c+1 yyk+m−d+1 k=0 (1+x)a−c(1+y)b−d (cid:88)∞ (cid:18) 1 (cid:19)k =Res Res x y x−c+1ym−d+1 xy k=0 (1+x)a−c(1+y)b−dxc−1 =Res Res x y ym−d+1(1−1/(xy)) (1+x)a−c(1+y)b−dxc (1.12) =Res Res y x ym−d+1(x−1/y) (1+1/y)a−c(1+y)b−d =Res y ym+c−d+1 (1+y)a+b−c−d =Res y ym+a−d+1 (cid:18) (cid:19) a+b−c−d = m+a−d For this identity, the lower limit of the summation may be replaced by max(c,d−m). The special case m=0 and c=d=0 reduces to: min(a,b)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:88) a b a+b = (1.13) k k a k=0 3 which is equivalent to the special case n = b of (1.4). The special case m = 0 and a=b=n reduces to: (cid:88)n (cid:18)n(cid:19)2(cid:18)k(cid:19)(cid:18)k(cid:19) (cid:18)2n−c−d(cid:19)(cid:18)n(cid:19)(cid:18)n(cid:19) = (1.14) k c d n−d c d k=0 The special cases c = d = 0, c = 1, d = 0 and c = d = 1 of this formula are well known [8]. 2 Harmonic Number Identities Thedefinitionofthegeneralizedharmonicnumberswithnonnegativeintegern,com- plex order m and complex offset c, is [12, 14]: n (cid:88) 1 H(m) = (2.1) c,n (c+k)m k=1 from which follows that H(m) =0, and for notation H(m) =H(m). From this defini- c,0 n 0,n tion follows for nonnegative integer c: H(m) =H(m) −H(m) (2.2) c,n c+n c The classical harmonic numbers are: H =H(1) (2.3) n 0,n Using d/dxΓ(x) = Γ(x)ψ(x) where ψ(x) is the digamma function, and using ψ(x+n+1)−ψ(x+1) = H(1) [1], these harmonic numbers are linked to bino- x,n mial coefficients: (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) d x+y x+y x+y = H(1) = (H −H ) (2.4) dx n n x+y−n,n n x+y x+y−n (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) d n n n = H(1) = (H −H ) (2.5) dx x+y x+y x+y,n−2(x+y) x+y n−(x+y) x+y For the generalized harmonic numbers (2.1): d H(m) =−mH(m+1) (2.6) dx x+y,n x+y,n When differentiating finite summation terms, care must be taken that the differen- tiated symbol is not present in the summation limits. Because the argument of a classical harmonic number cannot be negative, these harmonic numbers impose con- straints on the parameters. When there are additional constraints on the parameters 4 they are mentioned. Differentiating (1.1) to a, the following identity for a≥n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k n−k H k n−k c d a−k k=0 (2.7) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) n−c−d c d a+b−n a+b−c−d a−c Differentiating to b, the following identity for b≥n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k n−k H k n−k c d b−n+k k=0 (2.8) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) n−c−d c d a+b−n a+b−c−d b−d Replacing k by n−k and interchanging a with b and c with d, these two identities are equivalent. Differentiating to a and b, the following identity for a≥n and b≥n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k n−k H H k n−k c d a−k b−n+k k=0 (cid:18)a+b−c−d(cid:19)(cid:18)a(cid:19)(cid:18)b(cid:19) (2.9) = [H(2) −H(2) n−c−d c d a+b−n a+b−c−d +(H −H +H )(H −H +H )] a+b−n a+b−c−d a−c a+b−n a+b−c−d b−d The special case a=b=n and c=d=0 reduces to the known identities [2, 3, 8, 14, 16]: (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19) H = (2H −H ) (2.10) k k n n 2n k=0 (cid:88)n (cid:18)n(cid:19)2H H =(cid:18)2n(cid:19)[H(2)−H(2)+(2H −H )2] (2.11) k k n−k n n 2n n 2n k=0 Differentiating (1.1) to c, the following identity for b≤n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b n−k a+b−d b H = (H −H +H ) (2.12) k n−k d k n−d d n−d a+b−d a k=0 Differentiating to d, the following identity for a≤n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k a+b−c a H = (H −H +H ) (2.13) k n−k c n−k n−c c n−c a+b−c b k=0 Replacing k by n−k and interchanging a with b and c with d, these two identities are equivalent. Differentiating to c and d, the following identity for a≤n and b≤n 5 results: n (cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b H H k n−k k n−k k=0 (2.14) (cid:18) (cid:19) a+b = [H(2)−H(2) +(H −H +H )(H −H +H )] n n a+b n a+b a n a+b b In (1.1) replacing k by c+k and n by n+c, and differentiating to c, the following identity for a−c≥n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b c+k n−k H c+k n−k c d a−c−k k=0 (2.15) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) n−d c d a+b−n−c a+b−c−d a−c Replacing n with n+d and differentiating to d, the following identity for b−d ≥ n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k n+d−k H k n+d−k c d b−d−n+k k=0 (2.16) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) n−c c d a+b−n−d a+b−c−d b−d Replacing k by n−k and interchanging a with b and c with d, these two identities are equivalent. Differentiating to c and d, the following identity for a−c ≥ n and b−d≥n results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b c+k n+d−k H H c+k n+d−k c d a−c−k b−d−n+k k=0 (cid:18)a+b−c−d(cid:19)(cid:18)a(cid:19)(cid:18)b(cid:19) (2.17) = [H(2) −H(2) n c d a+b−n−c−d a+b−c−d +(H −H +H )(H −H +H )] a+b−n−c−d a+b−c−d a−c a+b−n−c−d a+b−c−d b−d Differentiating (1.7) to p, the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+k q+n−k k n−k H p q c d p+k k=0 (2.18) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) n+p+q+1 p+c q+d = (H −H +H ) n−c−d c d n+p+q+1 p+q+c+d+1 p+c The special case p=q =0 is found in [15], and the special case c=d=0 is found in [16]. Differentiating to q, the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+k q+n−k k n−k H p q c d q+n−k k=0 (2.19) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) n+p+q+1 p+c q+d = (H −H +H ) n−c−d c d n+p+q+1 p+q+c+d+1 q+d 6 Replacing k by n−k and interchanging p with q and c with d, these two identities are equivalent. Differentiating to p and q the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+k q+n−k k n−k H H p q c d p+k q+n−k k=0 (cid:18)n+p+q+1(cid:19)(cid:18)p+c(cid:19)(cid:18)q+d(cid:19) (2.20) = [H(2) −H(2) n−c−d c d p+q+c+d+1 n+p+q+1 +(H −H +H )(H −H +H )] n+p+q+1 p+q+c+d+1 p+c n+p+q+1 p+q+c+d+1 q+d The special case p = q = 0 is found in [15], and the special case c = d = 0 is found in [16]. In (1.7) replacing k by c+k and n by n+c, and differentiating to c, the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+c+k q+n−k c+k n−k H p q c d p+c+k k=0 (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) n+p+q+c+1 p+c q+d = (H −H +H ) n−d c d n+p+q+c+1 p+q+c+d+1 p+c (2.21) Replacing n with n+d and differentiating to d, the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+k q+n+d−k k n+d−k H p q c d q+n+d−k k=0 (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) n+p+q+d+1 p+c q+d = (H −H +H ) n−c c d n+p+q+d+1 p+q+c+d+1 q+d (2.22) Replacing k by n−k and interchanging p with q and c with d, these two identities are equivalent. Differentiating to c and d the following identity results: n (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) p+c+k q+n+d−k c+k n+d−k H H p q c d p+c+k q+n+d−k k=0 (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) n+p+q+c+d+1 p+c q+d = [H(2) −H(2) n c d p+q+c+d+1 n+p+q+c+d+1 +(H −H +H )(H −H +H )] n+p+q+c+d+1 p+q+c+d+1 p+c n+p+q+c+d+1 p+q+c+d+1 q+d (2.23) Differentiating (1.10) to a, the following identity for a≥b−m results: b−m(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k m+k H k m+k c d a−k k=0 (2.24) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) m+a−d c d m+a−d a+b−c−d a−c 7 Differentiating to b, the following identity for b≥a+m results: a (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k m+k H k m+k c d b−m−k k=0 (2.25) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) m+a−d c d b−m−c a+b−c−d b−d Differentiating to c, the following identity for d≥m results: min(a,b−m)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b m+k H k m+k d k k=0 (2.26) (cid:18) (cid:19)(cid:18) (cid:19) a+b−d b = (H −H +H ) m+a−d d a a+b−d b−m Differentiating to d, the following identity with m=d results: min(a,b−d)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k d+k H k d+k c d k k=0 (2.27) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) a+b−c−d a b = (H −H +H ) a c d a a+b−c−d b−d Differentiating to a and c, the following identity for a≥b−m and d≥m results: b−m(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b m+k H H k m+k d k a−k k=0 (cid:18)a+b−d(cid:19)(cid:18)b(cid:19) (2.28) = [H(2)−H(2) m+a−d d a a+b−d +(H −H +H )(H −H +H )] a a+b−d m+a−d a a+b−d b−m Differentiating to a and d, the following identity for a≥b−d and m=d results: b−d(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k d+k H H k d+k c d k a−k k=0 (cid:18)a+b−c−d(cid:19)(cid:18)a(cid:19)(cid:18)b(cid:19) (2.29) = [H(2)−H(2) a c d a a+b−c−d +(H −H +H )(H −H +H )] a a+b−c−d a−c a a+b−c−d b−d Differentiating to b and c, the following identity for b≥a+m and d≥m results: a (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b m+k H H k m+k d k b−m−k k=0 (cid:18)a+b−d(cid:19)(cid:18)b(cid:19) (2.30) = [H(2) −H(2) m+a−d d b−m a+b−d +(H −H +H )(H −H +H )] b−m a+b−d b−d b−m a+b−d a 8 Differentiating to b and d, the following identity for b≥a+d and m=d results: a (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) (cid:88) a b k d+k H H k d+k c d k b−d−k k=0 (cid:18)a+b−c−d(cid:19)(cid:18)a(cid:19)(cid:18)b(cid:19) (2.31) = [H(2) −H(2) a c d b−d a+b−c−d +(H −H +H )(H −H +H )] b−d a+b−c−d b−d−c b−d a+b−c−d a 3 A Recursion Formula for a Combinatorial Sum Using a recursion formula, a rational function P (n) is found such that: m (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19) km = P (n) (3.1) k n m k=0 From (1.5) or (1.14) with d=0 we have: (cid:88)n (cid:18)n(cid:19)2(cid:18)k(cid:19) (cid:18)2n−m(cid:19)(cid:18)n(cid:19) = (3.2) k m n m k=0 This formula is rewritten as: (cid:88)n (cid:18)n(cid:19)2m(cid:89)−1 (cid:18)2n(cid:19)m(cid:89)−1(n−j)2 (k−j)= (3.3) k n 2n−j k=0 j=0 j=0 Now the following is used: m−1 m (cid:20) (cid:21) (cid:89) (cid:88) m (k−j)= (−1)m−j kj (3.4) j j=0 j=0 where(cid:2)a(cid:3)istheStirlingnumberofthefirstkind[10]. ThenitisclearthatP (n)has b m the following recursion formula: m(cid:89)−1(n−k)2 m(cid:88)−1 (cid:20)m(cid:21) P (n)= − (−1)m−k P (n) (3.5) m 2n−k k k k=0 k=0 The following are a few examples: (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19) = (3.6) k n k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n k = (3.7) k n 2 k=0 9 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19) n3 k2 = (3.8) k n 2(2n−1) k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n3(n+1) k3 = (3.9) k n 4(2n−1) k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n3(n3+n2−3n−1) k4 = (3.10) k n 4(2n−1)(2n−3) k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n4(n+1)(n2+2n−5) k5 = (3.11) k n 8(2n−1)(2n−3) k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n3(n6+3n5−13n4−15n3+30n2+8n−2) k6 = (3.12) k n 8(2n−1)(2n−3)(2n−5) k=0 (cid:88)n (cid:18)n(cid:19)2 (cid:18)2n(cid:19)n4(n+1)(n5+5n4−15n3−35n2+70n−14) k7 = (3.13) k n 16(2n−1)(2n−3)(2n−5) k=0 TheMathematica(cid:13)R [17]programusedtocomputetheexpressionsisgivenbelow: P[0]=1; P[m_]:=P[m]=Factor[Simplify[Product[(n-k)^2/(2n-k),{k,0,m-1}] -Sum[StirlingS1[m,k]P[k],{k,0,m-1}]]] References [1] G.E.Andrews,R.Askey,R.Roy,SpecialFunctions,CambridgeUniversityPress, 1999. [2] X. Chen, W. Chu, The Gauss F (1)-summation theorem and harmonic number 2 1 identities, Integral Transforms Spec. Funct. 20 (2009) 925-935. [3] W. Chu, L. De Donno, Hypergeometric series and harmonic number identities, Adv. in Appl. Math. 34 (2005) 123-137. [4] R.V.Churchill, J.W.Brown, Complex Variables and Applications, McGraw-Hill, 1984. [5] G.P. Egorychev, Integral Representation and the Computation of Combinatorial Sums, Translations of Mathematical Monographs, 59, Amer. Math. Soc., 1984. [6] H.W.Gould,SomeGeneralizationsofVandermonde’sConvolution,Amer. Math. Monthly 63 (1956) 84-91. [7] H.W. Gould, Final Analysis of Vandermonde’s Convolution, Amer. Math. Monthly 64 (1957) 409-451. 10