SOME NICE SUMS ARE ALMOST AS NICE IF YOU TURN THEM UPSIDE DOWN

Moa Apagodu Department of Mathematics, Virginia Commonwealth University, Richmond, VA 08854, USA

Doron Zeilberger

Department of Mathematics, Rutgers University, Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Abstract. We represent the sums ∑_{k=0}^{n−1} \binom{n}{k}^{−2} , ∑_{k=0}^{m} \binom{m}{k}^{−1}\binom{a}{n−k}^{−1}, ∑_{k=0}^{n−1} _{\frac{q^{−k(k−1)}}{\left[{n \atop k}\right]q}},

and the sum of the reciprocal of the summand in Dixon’s identity, each as a product of an indefinite hypergeometric sum times a (closed form) hypergeometric sequence .

In [3], Rocket proved the formula

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

for all nonnegative integers n. Since then, several authors (e.g. [1][4][5]) used different techniques to re-derive (Rockett) and considered analogous, more complicated, sums.

As we all know,

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

is the simplest example of a definite binomial coefficient sum that evaluates in closed-form. Such sums have the form

∑_{k=0}^{n} F (n, k) = A(n) ,

where A(n) is hypergeometric (i.e. A(n + 1)/A(n) equals P (n)/Q(n) for some polynomials P (n), Q(n) of n, in other words, is a rational function of n), and F (n, k) is bi-hypergeometric (i.e F (n+1, k)/F (n, k) and F (n, k +1)/F (n, k) are both rational functions of R(n, k)). Other famous examples, are

∑_{k=0}^{n} \binom{n}{k}\binom{a}{k} = \binom{n + a}{a} ,  (Chu − V andermonde)

and

∑_{k=−n}^{n}(−1)^{k}\binom{a + n}{n + k}\binom{b + n}{b + k}\binom{a + b}{a + k} = \frac{(a + b + n)!}{a!b!n!} ,  (Dixon)

The best thing that can happen to a binomial coefficients sum is to he evaluable in closed form, i.e. as a hypergeometric sequence. The next best thing is to be “almost closed-form”, i.e. of the form

ClosedF orm(n) · (∑_{j=1}^{n} h(j)) ,

where h(j) is hypergeometric in the single variable j.

Inspired by (Rocket), that has this “almost perfect” form, and that came out from considering the sum of the reciprocal of the simplest binomial coefficient sum known, we searched for other cases where one starts from a well-known binomial coefficients sum that evaluates in closed form, and looks at what happens if one considers the sum of the reciprocal of the summand. To our great surprise and delight, it worked for the Chu-Vandermonde summand and for the Dixon summand (see below). To our disappointment, it didn’t work for the so-called Pfaff-Saalschutz identity (see, e.g. [2]). We use the WZ method([2]), and the reader is assumed to be familiar with it. In particular we used Zeilberger’s Maple package EKHAD (procedure zeillim) accompanying [2]. EKHAD is available from

  http://www.math.rutgers.edu/~zeilberg/tokhniot/EKHAD .

In most applications, the summation limits are natural, i.e. the summand is welldefined vanishes at k = −1 and k = n + 1 (or in the case of (Dixon), at k = −n − 1 and k = n + 1) so one can get a homogeneous first-order linear recurrence for the definite sum, that leads to a closed-form solution. In the present cases, this is no longer the case, and we only get inhomogeneous first-order linear recurrences, that leads to the “almost-perfect” kind of solutions. Consider the sum

f(n) := ∑_{k=α}^{n−β} F (n, k) ,

where α and β are constants and [α, n − β] is properly contained in [0, n], the support of F (n, k). Assume also that there exists a function G(n, k), (the so-called certificate) such that

a(n)F (n + 1, k) + b(n)F (n, k) = G(n, k + 1) − G(n, k) .  (W Zeqn)

Take α = 0 and β = 1. Then, if we add both sides of (WZeqn) from k = 0 to k = n and rewrite the result we get a nonhomogeneous recurrence relation satisfied by f(n):

a(n)f(n + 1) + b(n)f(n) = G(n, n) − G(n, 0) + a(n)F (n + 1, n) (nonhomorec)

Finally, we solve (nonhomorec) and get the following representation of f(n) as an indefinite sum:

f(n) = g(n) ∑_{i=0}^{n−1} \frac{C(i)}{g(i)a(i)} ,

where C(i) is the right-hand side of (nonhomorec) and g(n) is the solution to the associated homogeneous equation a(n)f(n + 1) + b(n)f(n) = 0.

We note that in cases where α ≠ 0 and β ≠ 1, the left-hand side of (nonhomrec) remains the same. The only change is on the right-hand side.

Theorem 1:

∑_{k=0}^{n−1} \binom{n}{k}^{−2} = \frac{(n + 1)!(n + 1)^{2}}{(n + \frac{3}{2})!4^{n}} ∑_{j=0}^{n−1} \frac{(3j^{3} + 12j^{2} + 18j + 10)4^{j}(j + 3/2)!}{(j + 1)^{2}(j + 1)!(j + 2)^{3}} .

Proof: We construct the function

G(n, k) = \frac{(2k − 3n − 6)(k − n − 1)^{2}}{\binom{n}{k}2}

such that (4n + 10)(n + 1)^{2}F (n + 1, k) − (n + 2)^{2}F (n, k) = G(n, k + 1) − G(n, k), where F (n, k) is the summand on the left-hand side sum.

Next add both sides from k = 0 to k = n and rearrange to get the nonhomogeneous recurrence relation satisfied by the sum on the left-hand side, S_{n} :

(4n + 10)(n + 1)^{2}S_{n+1} − (n + 2)^{2}S_{n} = 3n^{3} + 12n^{2} + 18n + 10 .

Finally the theorem follows by solving this recurrence with the initial condition S_{1} = 1.

Next we give q-analog of (Rokett). Let (a, q, n) = (1 − aq)(1 − aq^{2}) … (1 − aq^{n−1}).

Theorem 2 [q-binomial]:

∑_{k=0}^{n−1} \frac{q^{−k(k−1)/2}}{\left[{n \atop k}\right]q} = \frac{(q^{2}, q, n)}{(q^{2}, q^{2}, n)} ∑_{i=0}^{n−1} \frac{C(i)(q^{2}, q^{2}, i)}{(q^{2}, q, i)(q^{i+1} − 1)(q^{i+2} − 1)} ,

where

C(i) = (q^{3(i+2−i^{2})/2}+2q^{2i+2}−q^{−(i+1)(i−2)/2}−q^{−(i+1)(i−4)}−q^{i+1}−q^{3i+3}−q^{−i(i−1)/2}) .

Proof: We construct the function

G(n, k) = \frac{q^{n+1}(q^{n−k+1} − 1)q^{−k(k−1)/2}}{\left[{n \atop k}\right]q}

such that (q^{n+2} −1)F (n, k)−(q^{n+} −1)(q^{n+1} +1)F (n+1, k) = G(n, k +1)−G(n, k), where F (n, k) is the summand on the left-hand side.

Add both sides from k = 0 to k = n and rearrange to get the nonhomogeneous recurrence relation satisfied by the sum on the left-hand side, S_{n} :

(q^{n+2} − 1)S_{n} − (q^{n+} − 1)(q^{n+1} + 1)S_{n+1} = \frac{C(n)}{q^{n+1} − 1} .

Finally the theorem follows by solving this recurrence with the initial condition S_{1} = 1.

∑_{k=0}^{n} \frac{q^{−k(k−1)/2}}{\left[{n \atop k}\right]q} = q^{−n(n−1)/2} + \frac{(q^{2}, q, n)}{(q^{2}, q^{2}, n)} ∑_{i=0}^{n−1} \frac{C(i)(q^{2}, q^{2}, i)}{(q^{2}, q, i)(q^{i+1} − 1)(q^{i+2} − 1)} .

Next we consider the reciprocal of the summand in Chu-Vandermonde and Dixon’s classical identities.

Theorem 3 [Chu-Vandermonde]

∑_{k=0}^{m−1} \binom{m}{k}^{−1}\binom{a}{n − k}^{−1} = g(m) ∑_{i=0}^{m−1} \frac{C(i)}{g(i)(i + 2)(a + i − n + 2)}

where

g(m) = \frac{(a + m − n + 1)!(a + 4)!(m + 1)}{2(a + m + 3)!(a − n + 2)!}

and

C(m) = (n + m + mn + 1)\binom{a}{n}^{−1} + (2m + a − n + 3)\binom{a}{n − m}^{−1} .

Proof: The proof follows similarly from the recurrence relation

(m + 2)(a + m − n + 2)S_{m} − (a + m + 4)(m + 1)S_{m+1} = C(m) .

where S_{m} is the sum on left-hand side.

Theorem 4 [Dixon]

∑_{k=0}^{n−1}(−1)^{k}\binom{n + b}{n + k}^{−1}\binom{n + c}{c + k}^{−1}\binom{b + c}{b + k}^{−1} = g(n) ∑_{i=0}^{m−1} \frac{−C(i)}{g(i)(2i + 2)(c + i + 2)(b + i + 2)}

where

g(n) = \frac{(c + n + 1)(b + n + 1)}{(c + 1)(b + 1)} \frac{(c + b + 2)!n!}{(b + c + n + 2)!}

and

C(n) = (−1)^{n}(bc + 3bn + 3b + 3nc + 5n^{2} + 2n + 3c + 7)\binom{n+b}{2n}^{−1}\binom{b+c}{b+n}^{−1} − (n +

bn + nc + bc + b + c + 1)\binom{n+b}{n}^{−1}\binom{n+c}{c}^{−1}\binom{b+c}{b}^{−1} .

SOME NICE SUMS ARE ALMOST AS NICE IF YOU TURN THEM UPSIDE DOWN 5

Proof: The proof follows similarly from the recurrence relation 2(n + 1)(c + n + 2)(b + n + 2)S_{n} − 2(c + n + 1)(b + n + 1)(b + c + n + 3)S_{n+1} = C(n) . where S_{n} is the sum on left-hand side. Remarks a) From the recurrence in the proof of theorem 1,

2S_{n} = \frac{(n + 1)^{3}}{2n^{3} + 3n^{2}} S_{n−1} + \frac{3n^{3} + 3n^{2} + 3n + 1}{2n^{3} + 3n^{2}}

that implies

lim_{n→∞} ∑_{k=0}^{n} \binom{n}{k}^{−2} = 2 .

b) Identity (Rockett) is a special case of the following identity with x = y = 1 in

∑_{k=0}^{n} \binom{n}{k}^{−1}x^{k}y^{n−k} = x^{n} + (\frac{xy}{x + y} )^{n} (n + 1) ∑_{j=0}^{n−1} \frac{((j + 1)y^{j+2} + yx^{j+1})(x + y)^{j}}{(xy)^{j+1}(j + 1)(j + 2)}

which follows from the recurrence [S_{n} the left-hand side sum]:

(x + y)(n + 1)S_{n+1} − (n + 2)xyS_{n} = (n + 1)y^{n+2} + yx^{n+1} .

c) T. Mansour [1] derived the following representation for the reciprocals of binomial coefficients to any power m as:

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

References

[1] T. Mansour,”Combinatorial Identities and Inverse Binomial Coefficients”, Advances in Applied Mathematics, 28, 196-202(2002).

[2] M. Petkovsek, H.S. Wilf, D. Zeilberger, ”A=B”, A.K. Peters Ltd., 1996.

[3] A.M. Rokett, ”Sum of the inverse of binomial coefficients”, Fibonacci Quart., 19, 433-437(1981).

[4] R. Sprugnoli, ”Sums of Reciprocals of the Central Binomial Coefficients”, E. J. of Combinatorial Number Theory 6, #A27(2006).

[5] B. Sury, ” Sum of the Reciprocals of the Binomial Coefficients”, Europ. J. Combinatorics, 14, 351-353 (1993).