11
$\begingroup$

$$ \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.

  • 0
    looks like a combinatorial argument might be easier than doing just algebra.2011-11-01
  • 2
    The sum is in fact from $0$ to $m/2$ since for $s>m/2$ you have ${2p+m \choose 2p+2s} =0$.2011-11-01
  • 1
    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.2011-11-01
  • 0
    @BeniBogosel Who said that $m$ was an integer?2011-11-01
  • 1
    Who said that it isn't?2011-11-01
  • 0
    Hm... I recall that or a similar identity from *Concrete Mathematics*... maybe I find it again.2011-11-01
  • 0
    $m$ is integer definetly.2011-11-01

4 Answers 4

0

Here is a slightly different proof that is simpler than the other one I posted earlier.

Suppose we seek to verify that

$$\sum_{q\ge 0} {p+q\choose q} {m+2p\choose m-2q} = 2^{m-1} \frac{2p+m}{m} {m+p-1\choose p}.$$

This is

$$\sum_{q\ge 0} {p+q\choose q} {m+2p\choose 2p+2q}.$$

We introduce

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

This integral controls the range, being zero when $2q\gt m$ and we may extend the range of $q$ to infinity. We get for the sum

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

Extracting coefficients we get

$$2^m {m+p\choose p} - 2^{m-1} {m-1+p\choose p} \\ = 2^{m-1} {m-1+p\choose p} \left(2\frac{m+p}{m} - 1 \right) \\ = 2^{m-1} {m-1+p\choose p} \frac{m+2p}{m}.$$

This is the claim.

9

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} $$

  • 0
    Thank you, but i think i need to prove it using only generating functions and formal power series.2011-11-01
  • 0
    @PhilippG.Sinicyn I have posted another answer that uses generating functions2011-11-01
5

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} $$

  • 3
    Leave some scraps for the rest of us ;-) I was about to post a negative binomial solution, but now it is redundant.2011-11-01
  • 0
    @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.2011-11-03
  • 1
    @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}$.2011-11-03
2

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.