# Prove the identity $\sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$

$$\sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$$

Class themes are: Generating functions and formal power series.

-
looks like a combinatorial argument might be easier than doing just algebra. – user17762 Nov 1 '11 at 20:11
The sum is in fact from $0$ to $m/2$ since for $s>m/2$ you have ${2p+m \choose 2p+2s} =0$. – Beni Bogosel Nov 1 '11 at 20:12
If you want to do homework, you have to know what you have learned in your course. This is something we cannot do for you. Please say what you learned or I will just remark that this sum is utterly trivial using Zeilberger's algorithm. – Phira Nov 1 '11 at 20:23
@BeniBogosel Who said that $m$ was an integer? – Phira Nov 1 '11 at 20:24
Who said that it isn't? – Beni Bogosel Nov 1 '11 at 20:27

Ok, here is an approach with generating functions. Let $$g_1(z) = \sum_{s=0}^\infty \binom{p+s}{s} z^s = \frac{1}{\left(1-z\right)^{p+1}}$$

$$g_2(z) = \sum_{s=0}^\infty \binom{2p+m}{s} z^s = \left(1+z\right)^{m+2p}$$ Now $$\begin{eqnarray} \sum_{s=0}^\infty \binom{p+s}{s} \binom{2p+m}{2p+2s} &=& \sum_{s=0}^\infty \binom{p+s}{s} \binom{2p+m}{m-2s} = [z]^m g_1(z^2) g_2(z) = [z]^m \frac{\left(1+z\right)^{m+2p}}{(1-z^2)^{p+1}} \\ &=& [z]^m \frac{\left(1+z\right)^{m+p-1}}{\left(1-z\right)^{p+1}} \end{eqnarray}$$

Here is a verification:

In[27]:= With[{p = 5,
m = 7}, {SeriesCoefficient[(1 + z)^(m + 2 p)/(1 - z^2)^(
p + 1), {z, 0, m}],
Sum[Binomial[p + s, s] Binomial[2 p + m, 2 p + 2 s], {s,
0, \[Infinity]}]}]

Out[27]= {71808, 71808}


Let's continue: $$\begin{eqnarray} [z]^m \frac{\left(1+z\right)^{m+p-1}}{\left(1-z\right)^{p+1}} &=& \sum_{s=0}^\infty \binom{p+m-1}{m-s} \binom{p+s}{s} = \sum_{s=0}^\infty \binom{p+m-1}{p+s-1} \binom{p+s}{s}\\ &=& \sum_{s=0}^\infty \frac{(p+s) (m+p-1)!}{p! s! (m-s)!} = \sum_{s=0}^\infty \frac{p (m+p-1)!}{p! s! (m-s)!} + \sum_{s=0}^\infty \frac{s (m+p-1)!}{p! s! (m-s)!} \\ &=& \binom{m+p-1}{m} \left( \sum_{s=0}^\infty \binom{m}{s} + \sum_{s=0}^\infty \frac{s}{p} \binom{m}{s} \right) \\ &=& \binom{m+p-1}{m} \left( 2^m + 2^{m-1} \frac{m}{p} \right) \end{eqnarray}$$

-
Leave some scraps for the rest of us ;-) I was about to post a negative binomial solution, but now it is redundant. – robjohn Nov 1 '11 at 23:29
@Sasha, in your last equation you got $(2^m + 2^{m-1} \frac{m}{p}) = 2^{m-1}(\frac{2p+m}{p})$. But i have $2^{m-1}\frac{2p+m}{m}$ in my identity. – Philipp G. Sinicyn Nov 3 '11 at 18:35
@PhilippG.Sinicyn Yes, but you also have a different binomial. Notice that $\frac{1}{m} \binom{m+p-1}{p} = \frac{1}{p} \binom{m+p-1}{m}$. – Sasha Nov 3 '11 at 18:39

Let $d_s = \binom{p+s}{s} \binom{2p+m}{2p+2s}$. Using the recurrence relations for binomial, the ratio of successive terms is: $$\frac{d_{s+1}}{d_s} = \frac{\left(s - m/2\right)\left(s -(m-1)/2\right)}{ (s+1)(s+p+1/2) } = \frac{(s+a)(s+b)}{(s+1)(s+c)}$$ The hypergeometric certificate above means that $$\sum_{s=0}^\infty d_s = d_0 \sum_{s=0}^\infty \frac{(a)_s (b)_s}{s! (c)_s} = \binom{2p+m}{2p} {}_2 F_1\left( -\frac{m}{2}, -\frac{m-1}{2} ; p+\frac{1}{2} ; 1\right)$$ where $a = -\frac{m}{2}$, $b=-\frac{m-1}{2}$ and $c=p+\frac{1}{2}$.

Using Gauss's theorem, valid for $c>a+b$: $${}_2 F_1\left( a, b; c; 1\right) = \frac{\Gamma(c) \Gamma(c-a-b)}{\Gamma(c-a) \Gamma(c-b)}$$ we obtain the required identity: $$\sum_{s=0}^\infty \binom{p+s}{s} \binom{2p+m}{2p+2s} = \binom{2p+m}{2p} \frac{\Gamma\left(p+\frac{1}{2}\right) \Gamma\left( p+m \right)}{ \Gamma\left( p+\frac{m+1}{2} \right) \Gamma\left( p+\frac{m}{2} \right) }$$ Applying the duplication formula for $\Gamma(2p+m+1)$ and $\Gamma(2p+1)$ arising from $\binom{2p+m}{2p}$ we arrive at the result: $$\sum_{s=0}^\infty \binom{p+s}{s} \binom{2p+m}{2p+2s} = 2^{m-1} (m+2p) \frac{\Gamma(m+p)}{\Gamma(m+1) \Gamma(p+1)} = 2^{m-1} \frac{m+2p}{m+p} \binom{m+p}{p}$$

-
Thank you, but i think i need to prove it using only generating functions and formal power series. – Philipp G. Sinicyn Nov 1 '11 at 21:41
@PhilippG.Sinicyn I have posted another answer that uses generating functions – Sasha Nov 1 '11 at 22:46

I will try to give an answer using basic complex variables here. This calculation is very simple in spite of some more complicated intermediate expressions that appear.

Suppose we are trying to show that $$\sum_{q=0}^\infty {p+q\choose q} {2p+m\choose m-2q} = 2^{m-1} \frac{2p+m}{m} {m+p-1\choose p}.$$

Introduce the integral representation $${2p+m\choose m-2q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2p+m}}{z^{m-2q+1}} \; dz.$$

This gives for the sum the integral (the second binomial coefficient enforces the range) $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2p+m}}{z^{m+1}} \sum_{q=0}^\infty {p+q\choose q} z^{2q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2p+m}}{z^{m+1}} \frac{1}{(1-z^2)^{p+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{p+m-1}}{z^{m+1}} \frac{1}{(1-z)^{p+1}} \; dz.$$

This is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(2+z-1)^{p+m-1}}{z^{m+1}} \frac{1}{(1-z)^{p+1}} \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+(z-1)/2)^{p+m-1}}{z^{m+1}} \frac{1}{(1-z)^{p+1}} \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^{p+1}} \sum_{q=0}^{p+m-1} {p+m-1\choose q} \frac{(z-1)^q}{2^q} \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^{p+1}} \sum_{q=0}^{p+m-1} {p+m-1\choose q} (-1)^q \frac{(1-z)^q}{2^q} \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=0}^{p+m-1} {p+m-1\choose q} (-1)^q \frac{(1-z)^{q-p-1}}{2^q} \; dz.$$

The only non-zero contribution is with $q$ ranging from $0$ to $p.$ This gives $$2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=0}^p {p+m-1\choose q} (-1)^q \frac{1}{2^q} \frac{1}{(1-z)^{p+1-q}} \; dz$$ which on extracting coefficients yields $$2^{p+m-1} \sum_{q=0}^p {p+m-1\choose q} (-1)^q \frac{1}{2^q} {m+p-q\choose p-q}.$$

Introduce the integral representation $${m+p-q\choose p-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+p-q}}{z^{p-q+1}} \; dz.$$

This gives for the sum the integral (the second binomial coefficient enforces the range) $$2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+p}}{z^{p+1}} \sum_{q=0}^\infty {p+m-1\choose q}\frac{(-1)^q}{2^q} \left(\frac{z}{1+z}\right)^q \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+p}}{z^{p+1}} \left(1-\frac{1}{2}\frac{z}{1+z}\right)^{p+m-1} \; dz \\ = 2^{p+m-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{p+1}} \left(1+z-1/2\times z\right)^{p+m-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{p+1}} \left(2+z\right)^{p+m-1} \; dz.$$

Extracting coefficients now yields $${p+m-1\choose p} \times 2^{m-1} + {p+m-1\choose p-1} \times 2^m.$$

This symmetric form may be re-written in an asymmetric form as follows, $${p+m-1\choose p} \times 2^{m-1} + \frac{p}{m} {p+m-1\choose p} \times 2^m \\ = 2^{m-1} \times \left(1 + \frac{2p}{m}\right) {p+m-1\choose p}$$ as claimed.

The bonus feature of this calculation is that we evaluated two binomial sums instead of one.

We have not made use of the properties of complex integrals here so this computation can also be presented using just algebra of generating functions.

Apparently this method is due to Egorychev although some of it is probably folklore.

-