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

I need to prove $$\sum_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m}$$

using: $$(1-x)^{-m-1} (1-x)^{-q-1} = (1-x)^{-m-q-2} .$$

ok, generating function :$\frac1{(1-x)^{m+1}} = \sum\limits_{s=0}^\infty{m+s \choose m}x^s$;

lefthand part of the identity: $$\left(\sum_{l=0}^\infty{m+l \choose m}x^l\right)\left(\sum_{s=0}^\infty{q+k \choose q}x^s\right)$$ The coefficient at $x^{p-m}$ is $\sum\limits_{l+s = p-m}{m+l \choose m}{q+s \choose q} = \sum\limits_{s \geq 0} {p-s \choose m} {q+s \choose q}$

And on right side: ${m+q+1 \choose p-m}$

//I am not a native english-speaker, and I understand that my english leaves much to be desired. I will certainly appriciate your help in fixing mistakes in my texts.

-
Dear discobot: What I find weird is that there is no $p$ in what you're supposed to use. –  Pierre-Yves Gaillard Oct 29 '11 at 15:58
See also this similar problem. –  Mike Spivey Oct 29 '11 at 16:00

HINT: Use the generating function $$\frac1{(1-x)^{m+1}}=\sum_{k\ge 0}\binom{m+k}kx^k$$ and convolution.

Added: This is not an efficient write-up: I’ve tried to show how you might have arrived at the argument in the first place, though I have summarized it at the end. Note also that using generating functions and the equation $$(1-x)^{-m-1} (1-x)^{-q-1} = (1-x)^{-m-q-2}$$ is by no means the only way to prove the desired result; as Yuval has pointed out, there is a fairly simple combinatorial argument. In general I prefer combinatorial arguments, as they tend to be more informative, but it’s also important to be able to work with generating functions, and the statement of the problem directly suggests that approach.

You want to prove that $$\sum_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m}.\tag{1}$$ Notice first that this is really a finite sum, since $\binom{p-s}m=0$ when $p-s<m$, i.e., when $s>p-m$. Thus, $(1)$ can be written $$\sum_{s=0}^{p-m} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m}.\tag{2}$$

Now in general we have $$\sum_{k\ge 0}a_kx^k\sum_{k\ge 0}b_kx^k = \sum_{k\ge 0}\sum_{s=0}^k a_sb_{k-s}x^k,$$ where the coefficient of $x^k$ in the product is $\sum\limits_{s=0}^ka_sb_{k-s}$; how can we make the sum on the lefthand side of $(2)$ look like this? First match up $p-m$ with $k$. Since $s$ appears positively in $\binom{q+s}q$, it makes sense to match this up with $a_s$; this would mean that one of our generating functions is $$\sum_{k\ge 0}\binom{q+k}qx^k = \sum_{k\ge 0}\binom{q+k}k = \frac1{(1-x)^{q+1}} = (1-x)^{-q-1}.\tag{3}$$

This means that $\binom{p-s}m$ must be $b_{p-m-s}$. To get $b_s$, ‘replace’ $p-m-s$ by $s$ in $\binom{p-s}m$: $$b_{p-m-s} = \binom{p-s}m = \binom{m+(p-m-s)}{m},$$ so $$b_s = \binom{m+s}m,$$ and the other generating function in our product is $$\sum_{k\ge 0}\binom{m+k}mx^k = \sum_{k\ge 0}\binom{m+k}kx^k = \frac1{(1-x)^{m+1}} = (1-x)^{-1-m}.\tag{4}$$

From $(3)$ and $(4)$ we then have \begin{align*} (1-x)^{-1-q}(1-x)^{-1-m} &= \left(\sum_{k\ge 0}\binom{q+k}{k}x^k\right)\left(\sum_{k\ge 0}\binom{m+k}{k}x^k\right)\\ &= \sum_{k\ge 0}\left(\sum_{s=0}^k\binom{q+s}{s}\binom{m+k-s}{k-s}\right)x^k, \end{align*} where we’d like to equate the coefficient $$\sum_{s=0}^k\binom{q+s}{s}\binom{m+k-s}{k-s}$$ with the lefthand side of $(2)$. But this is easy: just let $k=p-m$, so that $p=m+k$, and we get \begin{align*} \sum_{s=0}^k\binom{q+s}{s}\binom{m+k-s}{k-s} &= \sum_{s=0}^{p-m}\binom{q+s}{s}\binom{p-s}{p-m-s}\\ &= \sum_{s=0}^{p-m}\binom{q+s}s\binom{p-s}m. \end{align*}

Now what about the righthand side of $(2)$? Go back to the generating functions: \begin{align*} (1-x)^{-1-q}(1-x)^{-1-m} &= (1-x)^{-2-q-m}\\ &= \frac1{(1-x)^{(q+m+1)+1}}\\ &= \sum_{k\ge 0}\binom{(q+m+1)+k}kx^k, \end{align*} where the coefficient of $x^k$ is $$\binom{q+(p-k)+1+k}{p-m} = \binom{q+p+1}{p-m}$$ when $k=p-m$ (and hence $m=p-k$).

Go back and summarize: \begin{align*} \sum_{k\ge 0}\left(\sum_{s=0}^k\binom{q+s}{s}\binom{m+k-s}{k-s}\right)x^k &= (1-x)^{-1-q}(1-x)^{-1-m}\\ &= (1-x)^{-2-q-m}\\ &= \sum_{k\ge 0}\binom{(q+m+1)+k}kx^k, \end{align*} so equating coefficients yields $$\sum_{s=0}^k\binom{q+s}{s}\binom{m+k-s}{k-s} = \binom{(q+m+1)+k}k,$$ which becomes $$\sum_{s=0}^{p-m}\binom{q+s}s\binom{p-s}m = \binom{q+p+1}{p-m}$$ when we set $k=p-m$. This is the identity that we set out to prove.

-
How should i apply convolution here? –  Philipp G. Sinicyn Oct 29 '11 at 15:13
@discobot: The lefthand side of $(1-x)^{-m-1}(1-x)^{-q-1}=(1-x)^{-m-q-2}$ is a product; the product of the generating functions of two sequences is the generating function of the convolution of the sequences. Equivalently, replace the generating functions by the corresponding formal power series, perform the multiplication on the lefthand side, and equate coefficients. –  Brian M. Scott Oct 29 '11 at 15:21
@discobot: I wrote that last comment before I saw your edit. I see now that you’ve gone part of the way: you’ve replaced the gen. funcs. by power series. Now do the multiplication on the lefthand side to get a single series; its coefficients will themselves be summations. You may find this helpful. –  Brian M. Scott Oct 29 '11 at 15:25
Dear @Brian: I suggest that you write a full answer. Thank you very much in advance. –  Pierre-Yves Gaillard Oct 29 '11 at 15:54
@Pierre-Yves: I will, but I’d like to give discobot a bit more time to think about the problem first. –  Brian M. Scott Oct 29 '11 at 16:20

There's also a simple combinatorial proof.

Given a choice of $m + 1 + q$ elements out of $p + q + 1$, the middle one breaks the range into parts of size $p-s$ and $q+s$ for some $s$; moreover, $m$ elements are selected out of the first part, and $q$ out of the second part. The procedure is reversible, and the identity follows.

-