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)

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