# 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)

I found an identity

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

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.

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