\documentclass[reqno,12pt,a4paper]{amsart}
\allowdisplaybreaks
\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{euscript}

\def\B{\EuScript{B}}

\begin{document}

\begin{center}
{\bf A GENERATING FUNCTIONS PROOF OF A CURIOUS IDENTITY}
\vskip 20pt
{\bf Alois Panholzer}\\
{\smallit Department of Algebra and Computer Mathematics, 
Technical  University Vienna, Wiedner Hauptstrasse 8--10, 
A--1040 Vienna, Austria}\\
{\tt Alois.Panholzer@tuwien.ac.at}\\ 
\vskip 10pt
{\bf Helmut Prodinger\footnote{supported by
The John Knopfmacher Centre for Applicable Analysis and Number Theory}}\\
{\smallit School of Mathematics, University of the  Witwatersrand,
P.\,O.~Wits,
2050 Johannesburg, 
South Africa}\\
{\tt helmut@staff.ms.wits.ac.za}\\
{\tt http://www.wits.ac.za/helmut/index.htm}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: , Accepted: , Published: }
\vskip 30pt 
\centerline{\bf Abstract}
\noindent
We give an alternative proof of an identity that appeared
recently in \emph{Integers}. It is shorter than the original
one and uses generating functions.
\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt x (200x), \#Axx\hfill} 
\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt 


In the paper \cite{Sun02} that appeared a few days ago the identity
\begin{equation*}
S_m:=(x+m+1)\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}{i}
-\sum_{i=0}^m\binom{x+i}{m-i}(-4)^i=(x-m)\binom{x}{m}
\end{equation*}
(the main result) was proved using double recursions.
Here we show this result using generating functions.
This proof is perhaps more pleasant and shorter than the
original one. 
The relevant functions can be found in
\cite[p.~201ff.]{GrKnPa94}.
We need
\begin{align*}
\big(\B_t(z)\big)^r&=\sum_{k\ge0}\binom{tk+r}{k}\frac{r}{tk+r}z^k,\\
\frac{\big(\B_t(z)\big)^r}
{1-t+t\big(\B_t(z)\big)^{-1}}&=\sum_{k\ge0}\binom{tk+r}{k}z^k,\\
\end{align*}
and in particular
\begin{align*}
\B_{-1}(z)=\frac{1+\sqrt{1+4z}}{2}\qquad\text{and}\qquad
\B_{2}(z)=\frac{1-\sqrt{1-4z}}{2z}.
\end{align*}
Now
\begin{align*}
\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}{i}&=
[z^m]\sum_{i\ge0}\binom{x+y+m-i}{i}z^i\cdot
\sum_{i\ge0}\binom{y+2i}{i}(-z)^i\\ &=[z^m]
\frac{\big(\B_{-1}(z)\big)^{x+y+m}}{2-\big(\B_{-1}(z)\big)^{-1}} \cdot
\frac{\big(\B_{2}(-z)\big)^{y}}{-1+2\big(\B_{2}(-z)\big)^{-1}}\\
&=[z^m]\frac1{1+4z}\big(\B_{-1}(z)\big)^{x+m+1}.
\end{align*}
Further,
\begin{align*} \sum_{i=0}^m\binom{x+i}{m-i}(-4)^i
&=(-4)^m\sum_{i=0}^m\binom{x+m-i}{i}(-\tfrac14)^i\\
&=(-4)^m[z^m]\frac1{1-z}\sum_{i\ge0}\binom{x+m-i}{i}(-\tfrac z4)^i\\
&=[z^m]\frac1{1+4z}\sum_{i\ge0}\binom{x+m-i}{i}z^i\\
&=[z^m]\frac1{(1+4z)^{3/2}}\big(\B_{-1}(z)\big)^{x+m+1}.\\
\end{align*}
%
We use the substitution $z={u}/{(1-u)^{2}}$ and get:
\begin{align*}
S_{m} & = [z^{m}]\left(\frac{x+m+1}{1+4z}-\frac{1}{(1+4z)^{3/2}}\right)
\big(\B_{-1}(z)\big)^{x+m+1} \\
& = \frac{1}{2 \pi i} \oint
\frac{1}{z^{m+1}}\left(\frac{x+m+1}{1+4z}-\frac{1}{(1+4z)^{3/2}}\right)
\big(\B_{-1}(z)\big)^{x+m+1}\, dz \\
& = \frac{1}{2 \pi i} \oint \frac{(1-u)^{2m+2}}{u^{m+1}}
\frac{(1+u)(2+x+m)-2}{(1+u)^{3} (1-u)^{x+m-1}} \frac{1+u}{(1-u)^{3}}\, du \\
& = [u^{m}] \frac{(1-u)^{m-x}((1+u)(2+x+m)-2)}{(1+u)^{2}} \\
& = (2+x+m) [u^{m}] \frac{(1-u)^{m-x}}{1+u} - 2 [u^{m}]
\frac{(1-u)^{m-x}}{(1+u)^{2}}.
\end{align*}
%
%
Expanding the terms leads now to
\begin{equation*}
[u^{m}] \frac{(1-u)^{m-x}}{1+u} = \sum_{k=0}^{m} \binom{x-k-1}{m-k}
(-1)^{k}
\end{equation*}
and
\begin{equation*}
[u^{m}] \frac{(1-u)^{m-x}}{(1+u)^2} = \sum_{k=0}^{m} (k+1) \binom{x-k-1}{m-k}
(-1)^{k}.
\end{equation*}
%
This gives
\begin{align*}
S_{m} &= \sum_{k=0}^{m} \big[(x-k)+(m-k)\big] \binom{x-k-1}{m-k} (-1)^{k}\\*
&= (x-m)\sum_{k=0}^{m} \bigg[ \binom{x-k}{m-k}+ \binom{x-k-1}{m-k-1}
\bigg](-1)^{k}\\*
&=(x-m) \binom{x}{m},
\end{align*}
as desired (the last sum is telescoping).



\bibliographystyle{plain} %\bibliography{C:/texfiles2001/pro_bib}
\begin{thebibliography}{1}

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.

\bibitem{Sun02}
Z.-W. Sun.
\newblock A curious identity involving binomial coefficients.
\newblock {\em Integers}, pages A4, 8 pp. (electronic), 2002.

\end{thebibliography}


\end{document}


