\documentclass[12pt]{article}

\textwidth= 6.25in

\textheight= 9.0in

\topmargin = -10pt

\evensidemargin=10pt

\oddsidemargin=10pt

\headsep=25pt

\parskip=10pt

\font\smallit=cmti10

\font\smalltt=cmtt10

\font\smallrm=cmr9

\usepackage{amsmath,amsthm,amsfonts,amssymb}





\begin{document}


\begin{center}
{\bf A WZ PROOF OF A ``CURIOUS" IDENTITY}


\vskip 20pt

{\bf Shalosh B. Ekhad}\\  
 {\smallit Department of Mathematics, 
Rutgers University, 110 Frelinghuysen, Piscataway, NJ, 08854}

\vskip 10pt

{\bf Mohamud Mohammed}\\ 
 {\smallit Department of Mathematics, 
Rutgers University, 110 Frelinghuysen, Piscataway, NJ, 08854} 






\end{center}

\vskip 20pt

\centerline{\smallit Received:4/3/03, Revised:5/27/03, Accepted:
5/28/03, Published: 6/2/03 }

\vskip 30pt


\centerline{\bf Abstract}
\noindent 
{We give a short WZ-proof of a binomial coefficient identity
due to Zhi-Wei Sun.}\\

\pagestyle{myheadings}

\markright{\smalltt INTEGERS:
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3
(2003), \#A06\hfill}



\thispagestyle{empty}

\baselineskip=15pt

\vskip 30pt


\noindent
In [3], [2], and [1] the identity 
\begin{equation}
 \sum_{i=0}^{m}(x+m+1) {(-1)^i {{x+y+i} \choose {m-i}} {{y+2i} \choose
{i}}}
 -\sum_{i=0}^{m} {{{x+i} \choose {m-i}}(-4)^i}=(x-m) {{x} \choose {m}}
\label{eqno1}
\end{equation}
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 \textit{zeillim} and can be run
by
 the command:
$ \mathit{zeillim}(\mathit{SUMMAND},i,m,M,0,0)$. But we include here the mathematics
behind
\textit{zeillim} for the sake of
clarity. Consider the indefinite sum
$$h(m):=\sum_{i=0}^{m} {{{{x+i} \choose {m-i}}(-4)^i} \over
{(-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)} \over {2(m+1-i)(x+m+2)}}
 {{{{x+i} \choose {m-i}}(-4)^i} \over {(-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). $$
Replacing 
$m$ by $i$  and summing the result from $i=0$ to $i=m-1 $ we have
$ \sum_{i=0}^{m}{F(m,i)}=F(0,0) + \sum_{i=1}^{m-1}\big({-G(i,0)}\big) $ 
as 
required. Hence
$$
\sum_{i=0}^{m} {{{x+i}\choose {m-i}}} (-4)^i=(-2)^{m}(x+m+1)
 \bigg ( {{1} \over {x+1}}+ \sum_{i=0}^{m-1}g(i) \bigg )
 $$ 
where 
$$ g(i)={{-{{x}\choose{i}}(x^2-2ix-x+i+i^2)}\over 
{2(1+i)(x+i+2)(x+i+1)(-2)^i}}.
$$

 



 Now the identity we need to prove is equivalent to  
\begin{equation}
\sum_{i=0}^{m}{(-1)^i {{x+y+i} \choose {m-i}} {{y+2i} \choose
 {i}}}=\frac{(-2)^{m}}{x+1} +
(-2)^m \sum_{i=0}^{m-1}g(i) 
 + {(x-m) {{x} \choose {m}} \over {(x+m+1)}}.
\label{eqno2}
\end{equation}



 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 
\begin{align*}
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). 
\end{align*}


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 $.  
\hfill{$\mathcal{Q.E.D.}$}





\begin{thebibliography}{10}

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

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

\bibitem {[3]} Zhi-Wei Sun. A curious identity involving binomial
coefficients, {\it Integers} {\bf 2} (2002), A4, 8 pp.

\end{thebibliography}



\end{document}