Convolution of binomial coefficients As part of a (SE) problem I've been working on, I came up with this expression:
$$
\sum_{i=0}^M\binom{M-1+i}{i}\binom{M+i}{i}
$$
I'd like to get a closed form for this, but after a considerable amount of time searching my references and online sources (not to mention the time I've spent bashing this into other equally opaque equivalences), I've come up empty. Does anyone have a clue? I'll be happy to link to the original if asked, but the expression more or less tells the story.
 A: We have $$\sum_{i\leq M}\dbinom{M-1+i}{i}\dbinom{M+i}{i}=\frac{1}{\left(M-1\right)!M!}\sum_{i\leq M}\frac{\left(M-1+i\right)!\left(M+i\right)!}{i!}\frac{1}{i!}=$$ $$=\frac{1}{\left(M-1\right)!M!}\sum_{i\leq M}\frac{\left(M\right)_{i}\left(M+1\right)_{i}}{\left(1\right)_{i}}\frac{1}{i!}$$ so it is the partial sum of the hypergeometric function $$\frac{1}{\left(M-1\right)!M!}\,_{2}F_{1}\left(M,M+1;1;1\right).$$
A: Here is an alternate representation of the sum.
Suppose we seek to evaluate
$$S_M =
\sum_{q=0}^M {q+M-1\choose M-1} {q+M\choose M}.$$
Introduce
$${q+M\choose M} = \frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{q+M}}{w^{M+1}} \; dw.$$

and furthermore introduce
$$[[0\le q \le M]]
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1+z+z^2+\cdots+z^M}{z^{q+1}} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{M+1}-1}{(z-1)z^{q+1}} \; dz$$
which controls  the range so we may  let $q$ go to  infinity to obtain
for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{M+1}-1}{(z-1)z} 
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\sum_{q\ge 0} {q+M-1\choose M-1} \frac{(1+w)^q}{z^q}
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{M+1}-1}{(z-1)z} 
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(1-(1+w)/z)^M}
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{2M+1}-z^M}{(z-1)z} 
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(z-(1+w))^M}
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{2M}-z^{M-1}}{(z-1)^{M+1}} 
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(1-w/(z-1))^M}
\; dw\; dz.$$
Extracting the residue at $w=0$ we obtain
$$\sum_{q=0}^M {M\choose M-q} {q+M-1\choose M-1} \frac{1}{(z-1)^q}.$$
There are two contributions to the outer integral here, the first is
$$\mathrm{Res}_{z=1}
\sum_{q=0}^M {M\choose q} {q+M-1\choose M-1} 
\frac{1}{(z-1)^{q+M+1}} \sum_{p=0}^{2M} {2M\choose p} (z-1)^p
\\ = \sum_{q=0}^M {M\choose q} {q+M-1\choose M-1} 
{2M\choose M+q}.$$
The second is
$$\mathrm{Res}_{z=1}
\sum_{q=0}^M {M\choose q} {q+M-1\choose M-1} 
\frac{1}{(z-1)^{q+M+1}} \sum_{p=0}^{M-1} {M-1\choose p} (z-1)^p$$
and this is easily seen to be zero.
The product of the three binomials is
$$\frac{M!}{q!\times (M-q)!}
\frac{(q+M-1)!}{(M-1)! \times q!}
\frac{(2M)!}{(M+q)!\times (M-q)!}.$$
which yields
$$\frac{M}{M+q}
\frac{(2M)!}{q! \times (M-q)! \times q! \times (M-q)!}.$$
which finally gives for the sum
$$M {2M\choose M}
\sum_{q=0}^M \frac{1}{M+q} {M\choose q}^2.$$
A: If the “$-1$” were missing from the first binomial, we'd get OEIS A$112029$, which converges 
asymptotically to $\dfrac{4^{2n+1}}{3\pi~n}~,$ and –at the same time– we also have $\displaystyle\lim_{n\to\infty}\frac{A_{112029}(n)}{a_n}=2$, where 
$a_n$ is our sequence. So, in conclusion, $a_n\sim\dfrac{2^{4n+1}}{3\pi~n}$ . It does not appear to possess a meaningful 
closed form expression, and even the simpler afore-mentioned OEIS sequence seems to lack one.
A: Remark. The Iverson  bracket that was used in  the first answer is
not quite appropriate  as the infinite series it  was substituted into
does not converge in a neighborhood of zero.
The appropriate form of the Iverson bracket here is
$$[[0\le q\le M]] =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^{q}}{z^{M+1}}\frac{1}{1-z} \; dz.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M+1}}\frac{1}{1-z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\sum_{q\ge 0} {q+M-1\choose M-1} (1+w)^q z^q
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M+1}}\frac{1}{1-z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(1-z(1+w))^M}
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M+1}}\frac{1}{1-z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(1-z-zw)^M}
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M+1}}\frac{1}{(1-z)^{M+1}}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(1-zw/(1-z))^M}
\; dw\; dz.$$
Extracting the residue at $w=0$ we obtain
$$\sum_{q=0}^M {M\choose M-q} {M-1+q\choose q} \frac{z^q}{(1-z)^q}.$$
Substituting this into the integral in $z$ yields
$$\sum_{q=0}^M {M\choose M-q} {M-1+q\choose q}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M-q+1}}\frac{1}{(1-z)^{M+q+1}} \; dz$$
which is 
$$\sum_{q=0}^M {M\choose M-q} {M-1+q\choose q}
{M+q+M-q\choose M+q}
\\= \sum_{q=0}^M {M\choose q} {M-1+q\choose M-1}
{2M\choose M+q}.$$
This is the same  as what we obtained in the first  version and we may
continue as before.
Addendum.
We  can  also evaluate  this  using the  negative  of  the residue  at
$w=(1-z)/z$ of the inner integral. This requires the derivative
(use Leibniz' rule)
$$\frac{1}{(M-1)!}\left(\frac{(1+w)^M}{w^{M+1}}\right)^{(M-1)}
\\ = \frac{1}{(M-1)!}
\sum_{q=0}^{M-1}
{M-1\choose q} \frac{M! \times (1+w)^{M-q}}{(M-q)!}
(-1)^{M-1-q}
\frac{(M+M-1-q)!}{M! \times w^{M+1+M-1-q}}
\\= (-1)^{M-1} \sum_{q=0}^{M-1} {M\choose q} (1+w)^{M-q}
(-1)^q {2M-1-q\choose M} \frac{1}{w^{2M-q}}.$$
Evaluation yields
$$(-1)^{M-1} \sum_{q=0}^{M-1} {M\choose q} \frac{1}{z^{M-q}}
(-1)^q {2M-1-q\choose M} \frac{z^{2M-q}}{(1-z)^{2M-q}}.$$
Re-write the double integral as follows:
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{2M+1}}\frac{1}{1-z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{((1-z)/z-w)^M}
\; dw\; dz
\\ = \frac{(-1)^M}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{2M+1}}\frac{1}{1-z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{(1+w)^{M}}{w^{M+1}} 
\frac{1}{(w-(1-z)/z)^M}
\; dw\; dz.$$
Substitute the evaluated derivative  into this integral to get
$$- \sum_{q=0}^{M-1} {M\choose q} 
(-1)^q {2M-1-q\choose M} 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{M+1}}\frac{1}{(1-z)^{2M+1-q}} \; dz
\\ = - \sum_{q=0}^{M-1} {M\choose q} 
(-1)^q {2M-1-q\choose M}
{2M-q+M\choose M}
\\ = - \sum_{q=0}^{M-1} {M\choose q} 
(-1)^q {2M-1-q\choose M}
{3M-q\choose M}.$$
We still need the value of  the residue at infinity of the integral in
$w$ using the following formula:
$$\mathrm{Res}_{z=\infty} h(z)
= \mathrm{Res}_{z=0} 
\left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$
which in the present case yields
$$- \mathrm{Res}_{w=0}
\frac{1}{w^2} \frac{(1+1/w)^M}{1/w^{M+1}} 
\frac{1}{(1-z/(1-z)/w)^M}
\\ = - \mathrm{Res}_{w=0}
\frac{1}{w} (1+w)^M
\frac{w^M}{(w-z/(1-z))^M}
\\ = - \mathrm{Res}_{w=0}
(1+w)^M
\frac{w^{M-1}}{(w-z/(1-z))^M}.$$
This is zero  by inspection and since the residues sum  to zero we may
conclude that the sum has the alternate representation
$$\sum_{q=0}^{M} {M\choose q} 
(-1)^q {2M-1-q\choose M}
{3M-q\choose M}.$$
