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.
 A: 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.
A: 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.
