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

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?

Answer 1

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

Answer 2

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.

Answer 3

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