<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Note on the Convolution of \\
\vskip .12in
Binomial Coefficients
}
\vskip 1cm
\large
Rui Duarte \\
Center for Research and Development in Mathematics and Applications\\
Department of Mathematics\\
University of Aveiro \\
Portugal \\
\href{mailto:rduarte@ua.pt}{\tt rduarte@ua.pt} \\
\ \\
Ant\'onio Guedes de Oliveira \\
CMUP and Department of Mathematics\\
Faculty of Sciences\\
University of Porto\\
Portugal\\
\href{mailto:agoliv@fc.up.pt}{\tt agoliv@fc.up.pt}
\end{center}

\vskip .2 in

\newcommand\N{\mathbb{N}}
\newcommand\R{\mathbb{R}}


\begin{abstract}
  We prove that, for every integer $a$, real numbers $k$ and $\ell$,
  and nonnegative integers $n$, $i$ and $j$,
$$ 
\sum_{i+j=n} {a\,i+k-\ell\choose i} {a\,j+\ell\choose j} =
\sum_{i+j=n} {a\,i+k\choose i} {a\,j\choose j},
$$ 
by presenting explicit expressions for its value. We use the identity
to generalize a recent result of Chang and Xu, and end the paper by
presenting, in explicit form, the ordinary generating function of the
sequence $\left\{{2n+k\choose n}\right\}_{n=0}^\infty$, where
$k\in\R$.
\end{abstract}

\section{Introduction}\label{int}

We consider the sequence $\big\{{a\,n+k\choose n}\big\}_{n=0}^\infty$,
where, following the notation of \cite{RS}, for every real $\ell$ and
every nonnegative integer $i$, $\big(\ell\big)_i=\ell(\ell-1)\cdots
(\ell-i+1)$ is the falling factorial and ${\ell\choose
  i}=\frac{(\ell)_i}{ i!}$. Temporarily, we consider $k=0$ and take
the convolution of this sequence with itself, defined by
$C_a(n)=\sum_{i+j=n}{a\,i\choose i} {a\,j\choose j}$.

When $a=2$, the former is sequence \seqnum{A000984} of \cite{oeis}, of the
central binomial coefficients, and the latter is sequence \seqnum{A000302}, of
the powers of $4$. In other words,
\begin{equation}\label{mainId}
C_2(n) \; = \; \sum_{i+j=n}{2\,i\choose i} {2\,j\choose j} \; = \; 4^n \, .
\end{equation}
In fact, we can prove directly \eqref{mainId} using, similarly to what
we do here (see \cite{part} for details), the inclusion-exclusion
principle after using identity \eqref{eqnova} for $a=2$, that is, the fact that
$$\sum_{i+j=n} {2i\choose i} {2j\choose j}
=\sum_{i+j=n} {2i-\ell\choose i} {2j+\ell\choose j}\,.$$

% In fact, we can prove directly \eqref{mainId} using \eqref{eqnova}
% for $a=2$, and then the inclusion-exclusion principle, similarly to
% what we do here (see \cite{part} for details).
Note that
\begin{equation}
  2 \, C_2(n) = 2^{2n+1} = \sum_{i=0}^{2n+1} {2n+1\choose i} = 2 \sum_{i=0}^n {2n+1\choose i} \, . \label{eq3}
\end{equation}
For another identity, define as usual $[n]=\{1,\ldots,n\}$ for any
natural number $n$ and consider the collection of the subsets of
$[2n]$ with more than $n$ elements and with the same $(n+1)$-th
element, $p$, say. Note that $p=n+1+i$ for some $i=0,\ldots,n-1$ and
that there are ${n+i\choose n}\,2^{n-i-1}$ subsets in the
collection. It follows that the number of all subsets of $[2n]$ is
\begin{equation}
  C_2(n) = 2^{2n} = 2 \sum_{i=0}^{n-1} 2^{n-i-1} {n+i\choose i} + {2n\choose n} = 
  \sum_{i=0}^n 2^{n-i} {n+i\choose i} \, . \label{eq4}
\end{equation}

We generalize these identities, namely \eqref{eq3} and
\eqref{eq4}. When $a=3$ and $a=4$, we have sequences \seqnum{A006256} and
\seqnum{A078995} of \cite{oeis}, and no such simple formulas for $C_3(n)$ and
$C_4(n)$ are known as in case $a=2$. For these sequences, we obtain,
for every real $\ell$,
\begin{align*}
  \sum_{i+j=n} {3i\choose i} {3j\choose j}
  &amp; = \sum_{i+j=n} 2^i {3n+1\choose j} 
= \sum_{i+j=n} 3^i {2n+j\choose j} = \sum_{i+j=n} {3i-\ell\choose i} {3j+\ell\choose j} \, , \\
  \sum_{i+j=n} {4i\choose i} {4j\choose j} &amp; = \sum_{i+j=n} 3^i
  {4n+1\choose j} = \sum_{i+j=n} 4^i {3n+j\choose j} = \sum_{i+j=n}
  {4i-\ell\choose i} {4j+\ell\choose j} \, .
\end{align*}

More generally, we obtain the following theorem.

\begin{theorem}\label{thm}
  For every nonnegative integers $i$, $j$ and $n$, and for
  every real numbers $k$ and $\ell$,
\begin{align}
  \sum_{i+j=n} {a\,i+k-\ell\choose i} {a\,j+\ell\choose j}
  &amp; = \sum_{i+j=n} {a\,i+k\choose i} {a\,j\choose j} \label{eqnova} \\
  &amp; = \sum_{i=0}^n (a-1)^{n-i} \, {a\,n+k+1\choose i} \label{eq6} \\
  &amp; = \sum_{i=0}^n a^{n-i} \, {(a-1)n+k+i\choose i} \label{eq7}
\end{align}
where we take $0^0=1$.
\end{theorem}
Gould \cite{gould} proves \eqref{eqnova} (together with the
Rothe-Hagen identity) using generating functions, and asks for proofs
``using finite series, the method of finite differences, or
otherwise''. So, part of this paper can be seen as an extension of a
recent paper by Chu \cite{chu}.

Coming back to the case where $a=2$, we consider the convolution of
more than two copies of the sequence of central binomial coefficients:
given integers $n\geq0$ and $t&gt;0$, define
$$P_t(n) = \sum_{i_1 + \cdots + i_t = n} {2i_1\choose i_1}{2i_2\choose i_2} \cdots {2i_t\choose i_t}.$$
where $i_1,\ldots,i_t$ are nonnegative integers. Recently, Chang and
Xu showed \cite{ChX}, with a probabilistic proof, that $P_t(n)$
depends only on $n$ and $t$. We give here a proof of combinatorial
nature of this fact and obtain a generalization that also includes
\eqref{mainId} as a special case. Namely, we prove the following
theorem, that is based on the results of Chang and Xu \cite{ChX}.
\begin{theorem}\label{newgen}
Let %$i_1,\ldots,i_n$ be any nonnegative integers and let 
$\ell_1, \ldots, \ell_t$ be any real numbers such that $\ell_1 + \cdots + \ell_t = 0$. 
Then
\begin{equation}\label{neq1}
  \sum_{i_1 + \cdots + i_t = n} {2i_1 + \ell_1\choose i_1}{2i_2 + \ell_2\choose i_2} \cdots {2i_t + \ell_t\choose i_t} = 4^n {n+\frac{t}{2}-1\choose n}\,,
\end{equation}
where $i_1,\ldots,i_t$ are nonnegative integers.
\end{theorem}

Finally, in Section~\ref{sec3} we obtain formulas for the generating
functions of the sequences involved in these identities.

\section{General case}

For the proof of Theorem~\ref{thm} we need some technical results.
\begin{lemma}\label{lemma1}
  Let, for any real $\ell$ and integers $a$ and $n$ such that
  $n\geq0$,
\begin{align*}
&amp; S_{a,\ell}(n) \; = \; \sum_{i=0}^n (-1)^i {\ell-(a-1)i\choose i} {\ell-a\,i\choose n-i} \, . \\
\intertext{Then} \\
&amp; \sum_{p=0}^n {n\choose p} \, S_{a,\ell}(p) \; = \; S_{a+1,\ell+n}(n) \, .
\end{align*}
\end{lemma}
\begin{proof}
\begin{align*}
\sum_{p=0}^n{n\choose p}\,S_{a,\ell}(p) &amp; = \sum_{i=0}^n \left[ (-1)^i {\ell-(a-1)i\choose i} \sum_{p=i}^n {\ell-a\,i\choose p-i} {n\choose p} \right] \\
&amp; = \sum_{i=0}^n \left[ (-1)^i {\ell-(a-1)i\choose i} \sum_{p=i}^n {\ell-a\,i\choose \ell-(a-1)i-p} {n\choose p} \right] \\
&amp; = \sum_{i=0}^n (-1)^i {\ell-(a-1)i\choose i} {\ell+n-a\,i\choose \ell-(a-1)\,i} \\
&amp; = \sum_{i=0}^n (-1)^i {(\ell+n)-a\,i\choose i \ , \ n-i \ , \ \ell-ai} \\
&amp; = \sum_{i=0}^n (-1)^i {(\ell+n)-a\,i\choose i} {(\ell+n)-(a+1)\,i\choose n-\,i} \, ,
\end{align*}
where we use Vandermonde's convolution in the third equality.
\end{proof}

\begin{lemma}\label{lemma2}
With the notation of the previous lemma,
$$S_{a,\ell}(n)\;=\;(a-1)^n.$$
\end{lemma}
\begin{proof}[First proof]
  First note that we may assume that $\ell$ is a natural number, since
  $S_{a,\ell}(n)$ is a polynomial in $\ell$, and thus is
  constant. Now, suppose that fixed $a$, there exist $x$ such that for
  all $\ell$ and $p$, $S_{a,\ell}(p)=x^p$. Then, from
  Lemma~\ref{lemma1} it follows that
  $S_{a+1,\ell+n}(n)=(1+x)^n$. Hence, all we must prove is that
  $S_{a,\ell}(n)=0$ when $a=1$ and $\ell\in\N$.

  For this purpose, define $\mathcal{A}$ as the set of $n$-subsets of
  the set $[\ell]=\{1,2,\ldots,\ell\}$ and let $\mathcal{A}_i$ be the
  set of elements of $\mathcal{A}$ that do not contain $i$, for
  $i\in[\ell]$. Then, on the one hand, $|\mathcal{A}_1 \cup \cdots
  \cup \mathcal{A}_\ell| = {\ell\choose p}$ and on the other hand, by
  the inclusion-exclusion principle,
$$
|\mathcal{A}_1 \cup \cdots \cup \mathcal{A}_\ell| = \sum_{i=1}^\ell
(-1)^{i+1} \bigg( \sum_{1 \leq j_1 &lt; \cdots &lt; j_i \leq \ell}
|\mathcal{A}_{j_1} \cap \cdots \cap \mathcal{A}_{j_i}| \bigg) \, .
$$
The proof is completed by noting that, for every integers 
$j_1,\ldots, j_i$ such that $1 \leq j_1 &lt; \cdots &lt; j_i \leq p$,
$|\mathcal{A}_{j_1} \cap \cdots \cap \mathcal{A}_{j_i}| =
{\ell-i\choose n-i}$.
\end{proof}

\begin{proof}[Second proof]
Notice first that, for any function $f$, we have by induction that
\begin{equation} \label{formula1}
(\Delta^n f)(x) = \sum_{i=0}^n (-1)^i {n\choose i} f(x+n-i)
\end{equation}
where $\Delta$ is the forward-difference operator defined by $(\Delta
f)(x)=f(x+1)-f(x)$, and $\Delta^n$ denotes the operator $\Delta$
applied successively $n$ times. In addition, if $f$ is a polynomial,
the degree reduces each time we apply $\Delta$ and, if the degree of
$f$ is $n$, the left-hand side of \eqref{formula1} must be a constant
which equals $(n!)a_n$, where $a_n$ is the coefficient of $x^n$ in
$f$. In particular,
$$\sum_{i=0}^n (-1)^i {n\choose i} f(n-i) = n!$$
if $f$ is a monic polynomial of degree $n$.

Now, $S_{a,\ell}(n)$ can be rewritten as $\sum_{i=0}^n (-1)^i
{n\choose i} {\ell-(a-1)i\choose n}$. If $a=1$, the identity is
clearly satisfied. When $a \neq 1$, the identity can be written as
$$
\sum_{i=0}^n (-1)^i {n\choose i} \left( \frac{\ell}{a-1} -i \right) \left( \frac{\ell-1}{a-1} -i \right) \cdots \left( \frac{\ell - (n-1)}{a-1} -i \right) = n! \, .
$$
If $f$ is the monic polynomial of degree $n$ defined as
$$
f(x)=\left( \frac{\ell}{a-1} -n+x \right) \left( \frac{\ell-1}{a-1} -n+x \right) \cdots \left( \frac{\ell - (n-1)}{a-1} -n+x \right) \, ,
$$
then clearly
$$
\sum_{i=0}^n (-1)^i {n\choose i} f(n-i) \; = \; (\Delta^n f)(0) \; = \; n! \, ,
$$
which proves the identity.
\end{proof}

\begin{lemma}\label{lemma3}
  Let $n$ be a nonnegative integer and $s$ and $t$ be two real
  numbers. Then
$${s+t+1\choose n} = \sum_{i=0}^n {s-i\choose n-i} {t+i\choose i}.$$
\end{lemma}

\begin{proof}[First proof]
  Let $\ F(n,i) = {s-i\choose s-n} {t+i\choose i} \ $. By Zeilberger's
  algorithm \cite{npwz,aeqb}, as implemented by Paule and Schorn
  \cite{pp} and by Krattenthaler \cite{krat}, we know that $T(n) =
  \sum_{i=0}^n F(n,i)$ verifies
\begin{equation} \label{zeil}
(s+t+1-n)\,T(n) - (n+1)\,T(n+1) = 0,
\end{equation}
which is also verified by $T(n) = {s+t+1\choose n}$, and for both it
holds $T(0)=1$. In fact, we can see that for every $i$ with $0 \leq i
\leq n+1$,
\begin{equation*}
(s+t+1-n)\,F(n,i) - (n+1)\,F(n+1,i) = G(n,i+1)-G(n,i)
\end{equation*}
with $G(n,i) = i\,{s+1-i\choose s-n} {t+i\choose i}$. Hence,
\eqref{zeil} holds since $F(n,n+1)=G(n,n+2)=G(n,0)=0$.
\end{proof}

\begin{proof}[Second proof]
  Since ${t+i\choose i}=(-1)^i{-t-1\choose i}$ and by Vandermonde's
  convolution,
\begin{align*}
  \sum_{i=0}^n {s-i\choose n-i} {t+i\choose i} &amp; = (-1)^n \sum_{i=0}^n {-t-1\choose i} {-s-1+n\choose n-i} \\
  &amp; = (-1)^n {-t-s+n-2\choose n} \\
  &amp; = {t+s+1\choose n} \, . \qedhere
\end{align*}
\end{proof}

\begin{lemma}\label{lemma4}
  For all nonnegative integers $i$ and $n$, and for all
  real numbers $a$ and $b$,
$$ \sum_{i=0}^n a^{n-i} \, {(b-1)n+k+i\choose i} = \sum_{i=0}^n (a-1)^{n-i} \, {b\,n+k+1\choose i}.$$
\end{lemma}

\begin{proof}
\begin{align*}
  \sum_{i=0}^n a^{n-i} \, {(b-1)n+k+i\choose i} &amp; = \sum_{i=0}^n \left[ \sum_{j=0}^{n-i} (a-1)^{n-j} {n-i\choose j} \right] {(b-1)n+k+i\choose i} \\
  &amp; = \sum_{j=0}^n (a-1)^{n-j} \left[ \sum_{i=0}^{n-j} {n-i\choose
      n-j-i} {\big((b-1)n+k\big)+i\choose i} \right] \, .
\end{align*}
The result now follows from Lemma~\ref{lemma3}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm}]
  Let $\mathfrak{S}=\sum_{i+j=n} {a\,i+k-\ell\choose i}
  {a\,j+\ell\choose j} = \sum_{i+j=n} (-1)^i {\ell-k'-(a-1)i\choose i}
  {a\,n+\ell-a\,i\choose j}$, with $k'=k+1$. Then, by Vandermonde's
  convolution,
\begin{eqnarray*}
  \mathfrak{S} &amp; = &amp; \sum_{i+j=n} \left[ (-1)^i {\ell-k'-(a-1)i\choose i} \sum_{p+m=j} {a\,n+k'\choose p} {\ell-k'-a\,i\choose m} \right] \\
  &amp; = &amp; \sum_{p=0}^n \left[ {a\,n+k'\choose p} \sum_{i+m=n-p} (-1)^i {\ell-k'-(a-1)i\choose i} {\ell-k'-a\,i\choose m} \right] \, .
\end{eqnarray*}
Now, \eqref{eq6} follows immediately from Lemma~\ref{lemma2} and
\eqref{eq7} follows from \eqref{eq6} and Lemma~\ref{lemma4}.
\end{proof}

We end this section with a problem based on a new result that, when we
represent by $\left(\!\!{n\choose k}\!\!\right)$ the number
${n+k-1\choose k}$ of $k$-multisets of elements of an $n$-set, can be
formulated in the following elegant terms.

\begin{theorem}\label{thm2}
  For every real $\ell$ and every nonnegative integer $n$,
$$\sum_{i=0}^n (-1)^i \left(\!\!\!{\ell-a\,i\choose i}\!\!\!\right) {\ell-a\,i\choose n-i}= a(a-1)^{n-1}.$$
\end{theorem}
\begin{proof}
By Pascal's rule,
\begin{align*}
\sum_{i=0}^n (-1)^i {\ell-1-(a-1)i\choose i} {\ell-a\,i\choose n-i} = &amp; \sum_{i=0}^n (-1)^i {\ell-(a-1)i\choose i} {\ell-a\,i\choose n-i} \\
&amp; - \sum_{i=1}^n (-1)^i {\ell-(a-1)i-1\choose i-1} {\ell-a\,i\choose n-i} \\
= &amp; S_{a, \ell}(n)+S_{a, \ell-a}(n-1) \, . \qedhere
\end{align*}
\end{proof}

\begin{problem}
Give a combinatorial proof of Theorem~\ref{thm2}.
\end{problem}

\section{The case $a=2$: on Chang \&amp; Xu generalization of the
  identity~\eqref{mainId}}
The main result of the article of Chang and Xu \cite{ChX} is a
generalization of \eqref{mainId} that we may write as
\begin{equation} \label{CXa}
\sum_{i_1 + \cdots + i_t=n} {2i_1\choose i_1} {2i_2\choose i_2} \cdots {2i_t\choose i_t} = 
4^n {n+\frac{t}{2}-1\choose n}.
\end{equation}
where $i_1,\ldots,i_n$ are (nonnegative) integers.

Let $P_t (n)$ be the left-hand side of \eqref{CXa}, as we defined
before. We remark that $P_1 (n) = {2n\choose n}$ and, by
\eqref{mainId}, $P_2(n) = 4^n$. Note also that \eqref{CXa} can be
obtained using induction and the following lemma. Finally, we observe
that $4^n {n+\frac{t}{2}-1\choose n}= \frac{{2n+2 k \choose 2n}}{{n+ k
    \choose n}} {2n\choose n}= \frac{{2n+2 k \choose n+ k}}{{2 k
    \choose k }} {n+ k \choose n}$ when $t = 2k+1$.

\begin{lemma} For every positive integer $t$ and every nonnegative
  integer $n$,
\begin{equation*}
P_{t+2} (n+1) = P_t (n+1) + 4\,P_{t+2} (n)
\end{equation*}
\end{lemma}
\begin{proof}
  In fact, $P_{t+2} (n+1) = \sum_{j=0}^{n+1} P_2 (n+1-j) P_t (j) = P_t
  (n+1) + 4 \sum_{j=0}^{n} 4^{n-j} P_t (j)$.
\end{proof}

Now, we consider again \eqref{eqnova}, the first identity in
Theorem~\ref{thm}. From this identity, as a clear consequence, we
obtain, for every integer $a$, for every nonnegative integers $t$, $n$
and $i_1, i_2, \ldots, i_t$ and for every real numbers $k, k_1, k_2,
\ldots, k_t$ such that $k = k_1+k_2+\cdots+k_t$, the following
identity, which is also a clear consequence of statement (2) of
Theorem~\ref{GenFun}:
$$
\sum_{i_1 + \cdots + i_t = n} {a\,i_1 + k\choose i_1} {a\,i_2\choose i_2} \cdots {a\,i_t\choose i_t} = \sum_{i_1 + \cdots + i_t = n} {a\,i_1+k_1\choose i_1}
{a\,i_2 + k_2\choose i_2} \cdots {a\,i_t+k_t\choose i_t} \, .
$$
Whence we obtain Theorem~\ref{newgen} as stated in Section~\ref{int}.

\section{Generating functions}\label{sec3}
In what follows, we denote by $f^{(n)}$ the $n$-th derivative of a
function $f$ of one real variable, $g(x) = \sum_{n \geq 0} {2n\choose
  n} \, x^n$ is the generating function of the central binomial
coefficients and $C(x) = \sum_{n \geq 0} \frac{1}{n+1} {2n\choose n}
\, x^n$ is the generating function of the Catalan numbers. We remember
that $g(x)=\frac{1}{\sqrt{1-4x}}$ and $C(x) = \frac{2}{1 +
  \sqrt{1-4x}}$. Note that $g' = 2g^3$ and $C' = g \, C^2$. The
following lemma can be easily proved by induction on $n$.

\begin{lemma} \label{deriv}
For every real numbers $t$ and $\ell$ and nonnegative integer $n$,
\begin{align*}
&amp;\frac{\left( g^t \right)^{(n)}}{n!} = 4^n {n + \frac{t}{2} -1\choose n} g^{t+2n}, \\
&amp;\frac{\left( g \, C^\ell \right)^{(n)}}{n!} = \sum_{i=0}^n {2n-i\choose n-i} {\ell+i-1\choose i} g^{1+2n-i} C^{\ell+i}, \\
&amp;\left( C^\ell \right)^{(n+1)} = \left( \ell \, g \, C^{\ell+1} \right)^{(n)} \, .
\end{align*}
\end{lemma}

Now, by Lemma~\ref{lemma3}, we obtain immediately the following
theorem. Note that the second statement is a particular case, but in
explicit form, of an identity of Gould \cite[p.\ 86 (9)]{gould}, and
that the third statement was proved by Catalan in 1876 
\cite[p.\ 62 and Errata]{cat}.

\begin{theorem}
For every real numbers $t$ and $\ell$, \label{GenFun} \hfill
\begin{align*}
&amp; g(x)^t = \sum_{n \geq 0} 4^n {n + \frac{t}{2} -1\choose n} x^n, \\
&amp; g(x)\, C(x)^\ell = \sum_{n \geq 0} {2n+\ell\choose n} x^n, \\
&amp; C(x)^\ell = 1 + \sum_{n \geq 1} \frac{\ell}{2n+\ell} {2n+\ell\choose n} x^n \, .
\end{align*}
\end{theorem}

\section{Acknowledgments}
We warmly thank the referee for his careful reading of the text, and
specially for offering us the second proof of Lemma \ref{lemma2} and
of Lemma \ref{lemma3}. We also thank Christian Krattenthaler for
drawing our attention to an article of Gould \cite{gould}, and the
\emph{On-Line Encyclopedia of Integer Sequences} \cite{oeis}, that was
very useful throughout all work. The work of both authors was
supported in part by the European Regional Development Fund through
the program COMPETE - Operational Program Factors of Competitiveness
(``Programa Operacional Factores de Competitividade'') and by the
Portuguese government through FCT - Funda\c{c}\~ao para a Ci\^encia e
a Tecnologia, under the projects PEst-C/MAT/UI0144/2011 and
PEst-C/MAT/UI4106/2011.

\begin{thebibliography}{99}
\bibitem{cat} E. C. Catalan, \textit{M\'elanges Math\'ematiques},
Vol.\ 2, F. Hayez,  Bruxelles, 1887.  Available  at
  \url{http://archive.org/details/mlangesmathm02catauoft} .
\bibitem{ChX} G. Chang and C. Xu, Generalization and probabilistic
  proof of a combinatorial identity. \textit{Amer. Math. Monthly}
  \textbf{118} (2011), 175--177.
\bibitem{chu} W. Chu, Elementary proofs for convolution identities of
  Abel and Hagen-Rothe. \textit{Electron. J. Combin.} \textbf{17}
  (2010), Note 24.
\bibitem{part} R. Duarte and A. Guedes de Oliveira, A short proof of a
  famous combinatorial identity, preprint,
  \url{http://arxiv.org/abs/1307.6693}.
\bibitem{gould} H. W. Gould, Some generalizations of Vandermonde's
  convolution. \textit{Amer. Math. Monthly} \textbf{63} (1956),
  84--91.
\bibitem{krat} C. Krattenthaler, HYP/HYPQ, available at
  \url{http://tinyurl.com/ld8dre8} .
\bibitem{npwz} I. Nemes, M. Petkov\v{s}ek, H. S. Wilf, and
  D. Zeilberger, How to do Monthly problems with your
  computer. \textit{Amer. Math. Monthly} \textbf{104} (1997),
  505--519.
\bibitem{pp} P. Paule and M. Schorn, The Paule/Schorn implementation
  of Gosper's and Zeilberger's algorithms, available at 
  \url{http://tinyurl.com/kbluqo4} .
\bibitem{aeqb} M. Petkov\v{s}ek, H. S. Wilf, and D. Zeilberger,
  {$\mathit{A=B}$}, A K Peters, 1996.
\bibitem{oeis} N. J. A. Sloane, \textit{The On-Line Encyclopedia of
    Integer Sequences}, published electronically at
  \url{http://oeis.org}, 2011.
\bibitem{RS} R. Stanley, \textit{Enumerative Combinatorics}, Volume 1,
  Cambridge University Press, 1997.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19;
Secondary 05A10,05A15.

\noindent \emph{Keywords: } combinatorial identity, binomial coefficient,
Vandermonde's convolution, WZ-method.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000302},
\seqnum{A000984},
\seqnum{A006256}, and
\seqnum{A078995}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 8 2013;
revised version received March 8 2013; July 26 2013; August 21 2013. 
Published in {\it Journal of Integer Sequences}, August 22 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>