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?

  • $\begingroup$ You really don't need to think of it as an infinite sum, since only finitely many values are non-zero. $\endgroup$ – Thomas Andrews Aug 3 '17 at 16:19
  • $\begingroup$ Vandermonde's identity and its proofs might provide some insight. $\endgroup$ – Greg Martin Aug 3 '17 at 16:57

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

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

  • $\begingroup$ Nice answer! (+1) $\endgroup$ – Markus Scheuer Aug 3 '17 at 19:17
  • 1
    $\begingroup$ thanks Markus, I learned from your suggestions to explicitate the steps. $\endgroup$ – G Cab Aug 3 '17 at 19:44

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.

  • $\begingroup$ This approach is with respect to this specific binomial identity as cool as it is an overkill! :-) Big fat (+1) $\endgroup$ – Markus Scheuer Aug 5 '17 at 13:41
  • $\begingroup$ Observation registered. What I find interesting here is that the double integral has a very nice symmetry which however we could not exploit during evaluation. Solving this one by taking advantage of the symmetry seems like an interesting challenge. $\endgroup$ – Marko Riedel Aug 5 '17 at 20:33
  • $\begingroup$ I agree, but I have no idea how to make good use of it. An interesting aspect right at the beginning was your first substitution. It was presumably intended to synchronise upper and lower part of the first binomial coefficient $\binom{t+k+l}{k+l}$ - clever, as there was no negative side effect on the other binomial coefficients. $\endgroup$ – Markus Scheuer Aug 5 '17 at 21:52
  • $\begingroup$ Kind of you to notice. Since you are asking, what happened here was I did not think of this substitution at first and evaluated the sum as given, which gave me the double integral, which I expanded into a sum, which in turn gave the substituted version. I then realized I could omit the entire first part of the calculation and keep only the substitution. $\endgroup$ – Marko Riedel Aug 5 '17 at 21:58
  • $\begingroup$ Ahh! I see. Thanks for the info. $\endgroup$ – Markus Scheuer Aug 5 '17 at 21:59

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.