Proving this infinite sum of a product of three binomials: $\sum\limits_{s}\binom{n+s}{k+l}\binom ks\binom ls=\binom nk\binom nl$ 
Question: How do you prove$$\sum\limits_{s}\binom{n+s}{k+l}\binom ks\binom ls=\binom nk\binom nl$$

I'm just not sure where to begin. I tried writing both sides as the coefficient of $x^n$ of the expansion of a binomial. But obviously, that doesn't fit the right-hand side because it's the product of two binomials.
I'm guessing that we'll need the multinomial theorem. Is that correct? Do you have any other ideas?
 A: $$
\eqalign{
  & \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\left( \matrix{
  n + s \cr 
  k + l \cr}  \right)\left( \matrix{
  k \cr 
  s \cr}  \right)\left( \matrix{
  l \cr 
  s \cr}  \right)}  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{
  n \cr 
  k + l - j \cr}  \right)\left( \matrix{
  s \cr 
  j \cr}  \right)} \left( \matrix{
  k \cr 
  s \cr}  \right)\left( \matrix{
  l \cr 
  s \cr}  \right)}  =  \;(1) \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{
  n \cr 
  k + l - j \cr}  \right)} \left( \matrix{
  k \cr 
  j \cr}  \right)\left( \matrix{
  k - j \cr 
  s - j \cr}  \right)\left( \matrix{
  l \cr 
  s \cr}  \right)}  = \; (2)  \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{
  n \cr 
  k + l - j \cr}  \right)} \left( \matrix{
  k \cr 
  j \cr}  \right)\left( \matrix{
  k - j \cr 
  k - s \cr}  \right)\left( \matrix{
  l \cr 
  s \cr}  \right)}  =  \; (3) \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{
  n \cr 
  k + l - j \cr}  \right)\left( \matrix{
  k \cr 
  j \cr}  \right)\left( \matrix{
  k + l - j \cr 
  k \cr}  \right)}  =  \; (4)\cr 
  &  = \left( \matrix{
  n \cr 
  k \cr}  \right)\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{
  n - k \cr 
  l - j \cr}  \right)\left( \matrix{
  k \cr 
  j \cr}  \right)}  =  \;(5) \cr 
  &  = \left( \matrix{
  n \cr 
  k \cr}  \right)\left( \matrix{
  n \cr 
  l \cr}  \right) \; (6) 
\quad \left| \matrix{  \;l,k \in \mathbb{N_0}  \hfill \cr   \;n \in \mathbb{C} \hfill \cr}  \right.
\cr} 
$$
where:
 - (1) inverse convolution
 - (2) Trinomial revision on 2nd and 3rd binomial
 - (3) Symmetry on 3rd ($k-j$ is non-negative because of the 2nd)
 - (4) convolution in $s$
 - (5) Trinomial revision on 1st and 3rd binomial
 - (6) convolution in $j$
A: We seek to simplify
$$\sum_s {n+s\choose k+l} {k\choose s} {l\choose s}.$$
The substitution $s = t + k+l-n$ yields
$$\sum_t {t+k+l\choose k+l} {k\choose t + k+l-n} {l\choose t+k+l-n}.$$
Working with the assumption that  the parameters are positive integers
we find that from the first binomial coefficient we get that for it to
be non-zero we must have $t\ge  0$ or $t\lt -(k+l).$ Note however that
in the latter case the two remaining coefficients vanish, which leaves
$t\ge 0.$ Re-writing we find
$$\sum_{t\ge 0} {t+k+l\choose k+l} {k\choose n-l-t} {l\choose n-k-t}.$$
We introduce  integral represenations  for the two  right coefficients
that also enforce the  fact that $t\le n-l$ and $t\le  n-k$ so that we
may then let $t$ range to infinity. We use
$${k\choose n-l-t} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon_1}
\frac{1}{z^{n-l-t+1}} (1+z)^k
\; dz$$
as well as
$${l\choose n-k-t} = 
\frac{1}{2\pi i}
\int_{|v|=\epsilon_2}
\frac{1}{v^{n-k-t+1}} (1+v)^l
\; dv.$$
We then get for the sum (no convergence issues here)
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon_1}
\frac{1}{z^{n-l+1}} (1+z)^k
\frac{1}{2\pi i}
\int_{|v|=\epsilon_2}
\frac{1}{v^{n-k+1}} (1+v)^l
\sum_{t\ge 0} {k+l+t\choose k+l} v^t z^t
\; dv\; dz.
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon_1}
\frac{1}{z^{n-l+1}} (1+z)^k
\frac{1}{2\pi i}
\int_{|v|=\epsilon_2}
\frac{1}{v^{n-k+1}} (1+v)^l
\frac{1}{(1-vz)^{k+l+1}}
\; dv\; dz.$$
We see that  this vanishes when $n\lt  k$ or $n\lt l$,  which we label
case A.  Case B  is that  $n\ge k,l.$ We  evaluate the  inner integral
using the fact that residues sum to zero. With this in mind we write
$$\frac{(-1)^{k+l+1}}{2\pi i}
\int_{|z|=\epsilon_1}
\frac{1}{z^{n+k+2}} (1+z)^k
\frac{1}{2\pi i}
\int_{|v|=\epsilon_2}
\frac{1}{v^{n-k+1}} (1+v)^l
\frac{1}{(v-1/z)^{k+l+1}}
\; dv\; dz.$$
We thus require for the pole at $v=1/z$
$$\frac{1}{(k+l)!}
\left(\frac{1}{v^{n-k+1}} (1+v)^l\right)^{(k+l)}$$
which is (apply Leibniz)
$$\frac{1}{(k+l)!}
\sum_{q=0}^{k+l} {k+l\choose q} 
(-1)^q {n-k+q\choose q} \frac{q!}{v^{n-k+1+q}}
\\ \times {l\choose k+l-q} (k+l-q)! (1+v)^{l-(k+l-q)}
\\ = \sum_{q=0}^{k+l}
(-1)^q {n-k+q\choose q} \frac{1}{v^{n-k+1+q}}
{l\choose k+l-q} (1+v)^{q-k}.$$
Evaluate at $v=1/z$ to get
$$\sum_{q=0}^{k+l}
(-1)^q {n-k+q\choose q} z^{n-k+1+q}
{l\choose k+l-q} \frac{(1+z)^{q-k}}{z^{q-k}}.$$
Substituting  this into  the integral  in  $z$ and  flipping the  sign
yields
$$(-1)^{k+l} \sum_{q=0}^{k+l}
(-1)^q {n-k+q\choose q}
{l\choose k+l-q} {q\choose k}.$$
Now we have
$${q\choose k} {n-k+q\choose q} =
\frac{(n-k+q)!}{k! \times (q-k)! \times (n-k)!}
= {n\choose k} {n-k+q\choose n}$$
and we obtain
$$(-1)^{k+l} {n\choose k} \sum_{q=0}^{k+l}
(-1)^q {l\choose k+l-q} {n-k+q\choose n}
\\ = {n\choose k} \sum_{q=0}^{k+l}
(-1)^q {l\choose q} {n+l-q\choose n}
\\ = {n\choose k} [w^n] \sum_{q=0}^{k+l}
(-1)^q {l\choose q} (1+w)^{n+l-q}
\\ = {n\choose k} [w^n] (1+w)^{n+l} \sum_{q=0}^{k+l}
(-1)^q {l\choose q} \frac{1}{(1+w)^q}
\\ = {n\choose k} [w^n] (1+w)^{n+l}
\left(1-\frac{1}{1+w}\right)^l
\\ = {n\choose k} [w^n] w^l (1+w)^{n}
= {n\choose k} {n\choose n-l} = {n\choose k} {n\choose l}.$$
This is the claim, which we proved for case B.
Remark. To  be perfectly rigorous  we also  need to show  that the
contribution from the residue at infinity is zero. We find
$$\mathrm{Res}_{v=\infty} \frac{1}{v^{n-k+1}} (1+v)^l
\frac{1}{(1-vz)^{k+l+1}}
\\ = - \mathrm{Res}_{v=0} \frac{1}{v^2} v^{n-k+1} \frac{(1+v)^l}{v^l}
\frac{1}{(1-z/v)^{k+l+1}}
\\ = - \mathrm{Res}_{v=0} \frac{1}{v^2} v^{n-k-l+1} (1+v)^l
\frac{v^{k+l+1}}{(v-z)^{k+l+1}}
\\ = - \mathrm{Res}_{v=0} v^{n} (1+v)^l
\frac{1}{(v-z)^{k+l+1}} = 0$$
and the check goes through.
A: $$\begin{align}
\sum_s \color{blue}{\binom {n+s}{k+l}}\binom ks\binom ls
&=\sum_s\color{blue}{\sum_j\binom n{k+j}} \color{green}{\binom ks}
\underbrace{\binom ls\color{blue}{\binom s{l-j}}}
_{=\color{orange}{\binom l{l-j}\binom{j}{s-l+j}}}
\\
&=\sum_j\binom n{k+j}\color{orange}{\binom l{l-j}}
\underbrace{\sum_s \color{green}{\binom k{k-s}}\color{orange}{\binom j{s-l+j}}}_{*=\binom{k+j}{k-l+j}=\color{pink}{\binom{k+j}{l}}}\\
&=\sum_j \binom l{l-j}
\underbrace{\binom n{k+j} \qquad \color{pink}{\binom {k+j}l}}
_{=\color{magenta}{\binom nl\binom {n-l}{k+j-l}}}\\
&=\color{magenta}{\binom nl}
\underbrace{\sum_j \binom l{l-j}
\color{magenta}{\binom{n-l}{k+j-l}}}_{*=\color{red}{\binom nk}}\\
&=\color{red}{\binom nk \binom nl}
\end{align}$$
* using the Vandermonde Identity.
