Proof of $\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity)

Question

I found an identity

$\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$

from https://en.wikipedia.org/wiki/Binomial_coefficient#Sums_of_the_binomial_coefficients.

I can prove this in a combinatorial way: from $n+1$ balls, choose one ball as a boundary and pick up $j$ balls from the left and $k-j$ balls from the right, for every possible boundary balls. And then I can prove this is identical to choosing $k+1$ balls from $n+1$ balls.

On the other hand, the wiki says that you can prove this by using negative binomial series expansion. I have tried few attempts but wasn't very successful. Could anyone share a proof using binomial series expansion?

Thank you.

Answer 1

Recall that $$ (1-x)^{-s} = \sum_{t=0}^{\infty} \binom{s+t-1}{t} x^t . $$ Recall also the notation that for a (formal) power series $f$, $[x^a]f$ denotes the coefficient of $x^a$ in $f$. In particular $[x^t](1-x)^{-s} = \binom{s+t-1}{t}$. And specifically, $$ [x^{m-j}](1-x)^{-(j+1)} = \binom{m-j+j}{m-j} = \binom{m}{j} $$ and $$ [x^{n-m-k+j}](1-x)^{-(k-j+1)} = \binom{n-m}{k-j} . $$ Multiplying these and summing over $m$ gives the coefficient of $$ x^{(m-j) + (n-m-k+j)} = x^{n-k} $$ in $(1-x)^{-(k+2)}$, thus $$ \begin{multline*} \sum_{m=0}^{\infty} \binom{m}{j}\binom{n-m}{k-j} = [x^{n-k}](1-x)^{-(k+2)} = \binom{(k+2)+(n-k)-1}{n-k} \\= \binom{n+1}{n-k} = \binom{n+1}{k+1}. \end{multline*} $$ The limits of summation for $m$ don't matter too much; the terms are only nonzero for $j \leq m \leq n-k+j$ anyway, and $n-k+j \leq n$, so it doesn't make a difference whether we sum up to $n$ or up to $\infty$.

Answer 2

Wiki says that you can prove this by using negative binomial series expansion.

Here is the way:

$$\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\sum_{m=j}^{n}\binom{m}{m-j}\binom{n-m}{n-m-k+j}$$$$=\sum_{m=j}^{n}\left(-1\right)^{m-j}\binom{-j-1}{m-j}\left(-1\right)^{n-m-k+j}\binom{-k+j-1}{n-m-k+j}$$ Setting $m-j \mapsto m$ yields:

$$=\left(-1\right)^{n-k}\sum_{m=0}^{n-j}\binom{-j-1}{m}\binom{-k+j-1}{n-m-k}$$$$=\left(-1\right)^{n-k}\binom{-k-2}{n-k}$$$$=\binom{n+1}{n-k}=\binom{n+1}{k+1}$$

So we showed that :

$$\bbox[5px,border:2px solid #00A000]{\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}}$$

Which is the claim.

---

Note:

Here Vandermonde's convolution is generalized:

$$\large\sum_{k=0}^{\large\sum_{\mu=1}^{i}n_\mu}\binom{\large\sum_{\mu=1}^{i}n_\mu}{k}x^{k}=\left(1+x\right)^{\large\sum_{\mu=1}^{i}n_\mu}$$$$=\large\prod_{\mu=1}^{ i}\left(1+x\right)^{n_\mu}=\prod_{\mu=1}^{ i}\sum_{k_{\mu }=0}^{n_{\mu }}\binom{n_\mu}{k_\mu}x^{k_\mu}$$$$=\large{\sum_{k=0}^{\large\sum_{\mu=1}^{i}n_\mu }\sum_{\sum_{\mu=1}^{i} v_\mu=k}^{ }}\;\;{\prod_{\mu=1}^{ i}}a_{v_\mu}\large x^{k}$$

Where: $$\large a_{v_\mu}=\binom{n_\mu}{v_\mu}$$

Comparing the coefficient of $x^k$ on the both sides follows:

$$\bbox[5px,border:2px solid #00A000]{\binom{\large\sum_{\mu=1}^{i}n_\mu}{k}=\large\sum_{\sum_{\mu=1}^{i}v_{\mu}=k}^{ }\;\;\prod_{\mu=1}^{i}\large \binom{n_\mu}{v_\mu}}$$

Regular Vandermonde's convolution is a special case of this relation which can be derived by setting $i \mapsto 2$