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 Xm
i=0
(x+m+ 1)(−1)i
µx+y+i m−i
¶µy+ 2i i
¶
− Xm
i=0
µx+i m−i
¶
(−4)i = (x−m) µ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 indexmunder the summation sign.
This is automated in EKHAD in the procedurezeillim 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) :=
Xm
i=0
¡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) := (x+ 2i−m−1)(x+ 2i−m) 2(m+ 1−i)(x+m+ 2)
¡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 THEORY3 (2003), #A06 2 Replacingmbyiand summing the result fromi= 0 toi=m−1 we havePm
i=0F(m, i) = F(0,0) +Pm−1
i=1
¡−G(i,0)¢
as required. Hence Xm
i=0
µx+i m−i
¶
(−4)i = (−2)m(x+m+ 1) µ 1
x+ 1 +
mX−1
i=0
g(i)
¶
where
g(i) = −¡x
i
¢(x2−2ix−x+i+i2) 2(1 +i)(x+i+ 2)(x+i+ 1)(−2)i. Now the identity we need to prove is equivalent to
Xm
i=0
(−1)i
µx+y+i m−i
¶µy+ 2i i
¶
= (−2)m
x+ 1 + (−2)m
mX−1
i=0
g(i) + (x−m)¡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 sideT(m), EKHAD automatically finds the following recurrence forT(m):
a0(m)T(m) +a1(m)T(m+ 1) +a2(m)T(m+ 2) +a3(m)T(m+ 3) = 0, where
a0(m) = 2(x−m−1)(x−m−2),
a1(m) = −(x−m−2)(2y−x+ 5m+ 11),
a2(m) = (−yx+ 3ym−2xm+ 4m2+ 8y−5x+ 21m+ 28), a3(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 tom−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.