A WZ PROOF OF A “CURIOUS” IDENTITY

Shalosh B. Ekhad

Department of Mathematics, Rutgers University, 110 Frelinghuysen, Piscataway, NJ, 08854

Mohamud Mohammed

Department of Mathematics, Rutgers University, 110 Frelinghuysen, Piscataway, NJ, 08854

Received: 4/3/03, Revised: 5/27/03, Accepted: 5/28/03, Published: 6/2/03

Abstract

We give a short WZ-proof of a binomial coefficient identity due to Zhi-Wei Sun.

In [3], [2], and [1] the identity

∑_{i=0}^{m}(x + m + 1)(−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} − ∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} = (x − m)\binom{x}{m} (1)

was proved using generating functions, double recursions and the concept of Riordan Arrays respectively. Here we use the WZ-method to give yet another proof.

First we divide both sides of (1) by (x + m + 1) and then try to write the second indefinite sum on the LHS of (1) without the running index m under the summation sign. This is automated in EKHAD in the procedure zeillim and can be run by the command: zeillim(SUMMAND, i, m, M, 0, 0). But we include here the mathematics behind zeillim for the sake of clarity. Consider the indefinite sum

h(m) := ∑_{i=0}^{m} \frac{\binom{x+i}{m−i}(−4)^{i}}{(−2)^{m}(x + m + 1)}.

Using the Maple package EKHAD (downloadable from Doron Zeilberger’s website), we find that the WZ-mate of the summand, call it F (m, i), is the function

G(m, i) := \frac{(x + 2i − m − 1)(x + 2i − m)}{2(m + 1 − i)(x + m + 2)} \frac{\binom{x+i}{m−i}(−4)^{i}}{(−2)^{m}(x + m + 1)}.

That means that F and G satisfy F (m + 1, i) − F (m, i) = G(m, i + 1) − G(m, i). If we sum both sides from i = 0 to i = m + 1, and simplify, we get

h(m + 1) − h(m) = F (m + 1, m + 1) + G(m, m + 2) − G(m, 0) = −G(m, 0).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A06 2

Replacing m by i and summing the result from i = 0 to i = m−1 we have ∑_{i=0}^{m} F (m, i) = F (0, 0) + ∑_{i=1}^{m−1} (−G(i, 0)) as required. Hence

∑_{i=0}^{m} \binom{x + i}{m − i}(−4)^{i} = (−2)^{m}(x + m + 1)(\frac{1}{x + 1} + ∑_{i=0}^{m−1} g(i))

where

g(i) = \frac{−\binom{x}{i}(x^{2} − 2ix − x + i + i^{2})}{2(1 + i)(x + i + 2)(x + i + 1)(−2)^{i}} .

Now the identity we need to prove is equivalent to

∑_{i=0}^{m} (−1)^{i}\binom{x + y + i}{m − i}\binom{y + 2i}{i} = \frac{(−2)^{m}}{x + 1} + (−2)^{m} ∑_{i=0}^{m−1} g(i) + \frac{(x − m)\binom{x}{m}}{(x + m + 1)}. (2)

Next we find a recurrence relation satisfied by the sum on the left hand side of (2) and check that the right hand side satisfies this recurrence with enough initial conditions. Calling the left side T (m), EKHAD automatically finds the following recurrence for T (m):

a_{0}(m)T (m) + a_{1}(m)T (m + 1) + a_{2}(m)T (m + 2) + a_{3}(m)T (m + 3) = 0,

where

a_{0}(m) = 2(x − m − 1)(x − m − 2),
a_{1}(m) = −(x − m − 2)(2 y − x + 5 m + 11),
a_{2}(m) = (−yx + 3 ym − 2 xm + 4 m^{2} + 8 y − 5 x + 21 m + 28),
a_{3}(m) = (m + 3)(y + m + 3).

It is readily checked that the right hand side also satisfies this same recurrence. Indeed the first and third terms satisfy the recurrence separately, while the second one (involving the indefinite sum) is easily shown to satisfy it by regrouping the four resulting sigmas (obtained by plugging the sum into the recurrence) into a sum from 0 to m−1 plus some “left-over” that turns out to vanish. Moreover, both sides agree for m = 0, 1, 2. Q.E.D.

References

[1] D. Merlini and R. Sprugnoli. A Riordan array proof of a curious identity, Integers 2 (2002), A8, 3 pp.

[2] A. Panholzer, and H. Prodinger. A generating functions proof of a curious identity, Integers 2 (2002), A6, 3 pp.

[3] Zhi-Wei Sun. A curious identity involving binomial coefficients, Integers 2 (2002), A4, 8 pp.