2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much. It was very clear. $\endgroup$ – jang Aug 31 '17 at 16:41
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$

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.