证明组合恒等式:
\[\sum_{k=0}^{r}\binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r}
\quad n+m\geq r.\]
\end{example}
\begin{solution}
证法1. (组合分析法)一个班里有$n$个男生, $m$个女生.现需从中选出$r$个人,则有$\binom{n+m}{r}$种选法;另外,若先选出$k\,(0\leq k\leq r)$个男生,再选出$r-k$个女生,则共有$\sum_{k=0}^{r}\binom{n}{k}\binom{m}{r-k}$种选法,所以
\[\sum_{k=0}^{r}\binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r}
\quad n+m\geq r.\]
证法2. (母函数法)因为$(1+x)^n=\sum_{k=0}^{\infty}\binom{n}{k}x^k$,所以$(1+x)^{n+m}=\sum_ {r=0}^{\infty}\binom{n+m}{r}x^r$.又因为
\[(1+x)^{n+m}=(1+x)^n(1+x)^m=\sum_ {k=0}^{\infty}\binom{n}{k}x^k\cdot \sum_ {j=0}^{\infty}\binom{m}{j}x^j
=\sum_ {r=0}^{\infty}\sum_ {k=0}^r\binom{n}{k}\binom{m}{r-k}x^r,\]
所以
\[(1+x)^{n+m}=\sum_ {r=0}^{\infty}\binom{n+m}{r}x^r
=\sum_ {r=0}^{\infty}\sum_ {k=0}^r\binom{n}{k}\binom{m}{r-k}x^r.\]
比较$x^r$的系数可得
\[\sum_ {k=0}^r\binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r}.\]
\end{solution}
如果令$m=r=n$,则
\[\sum_ {k=0}^n\binom{n}{k}\binom{n}{n-k}=\binom{n+n}{n},\]
即
\[\sum_ {k=0}^n\binom{n}{k}^2=\binom{2n}{n},\]
这便是Vandermonde恒等式.
原文：https://www.cnblogs.com/Eufisky/p/12662707.html