Algebraic proof In general, the product of two
polynomials with degrees
m and
n, respectively, is given by :\biggl(\sum_{i=0}^m a_ix^i\biggr) \biggl(\sum_{j=0}^n b_jx^j\biggr) = \sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r a_k b_{r-k}\biggr) x^r, where we use the convention that
ai = 0 for all integers
i >
m and
bj = 0 for all integers
j >
n. By the
binomial theorem, :(1+x)^{m+n} = \sum_{r=0}^{m+n} {m+n \choose r}x^r. Using the binomial theorem also for the exponents
m and
n, and then the above formula for the product of polynomials, we obtain :\begin{align} \sum_{r=0}^{m+n} {m+n \choose r}x^r &= (1+x)^{m+n}\\ &= (1+x)^m (1+x)^n \\ &= \biggl(\sum_{i=0}^m {m\choose i}x^i\biggr) \biggl(\sum_{j=0}^n {n\choose j}x^j\biggr)\\ &=\sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r {m\choose k} {n\choose r-k}\biggr) x^r, \end{align} where the above convention for the coefficients of the polynomials agrees with the definition of the binomial coefficients, because both give zero for all
i >
m and
j >
n, respectively. By comparing coefficients of
xr, Vandermonde's identity follows for all integers
r with 0 ≤
r ≤
m +
n. For larger integers
r, both sides of Vandermonde's identity are zero due to the definition of binomial coefficients.
Combinatorial proof Vandermonde's identity also admits a combinatorial
double counting proof, as follows. Suppose a committee consists of
m men and
n women. In how many ways can a subcommittee of
r members be formed? The answer is :{m+n \choose r}. The answer is also the sum over all possible values of
k, of the number of subcommittees consisting of
k men and
r −
k women: :\sum_{k=0}^r{m \choose k}{n \choose r-k}.
Geometrical proof Take a rectangular grid of
r x (
m+
n−
r) squares. There are : \binom{r+(m+n-r)}{r}=\binom{m+n}{r} paths that start on the bottom left vertex and, moving only upwards or rightwards, end at the top right vertex (this is because
r right moves and
m+
n-
r up moves must be made (or vice versa) in any order, and the total path length is
m +
n). Call the bottom left vertex (0, 0). There are \binom{m}{k} paths starting at (0, 0) that end at (
k,
m−
k), as
k right moves and
m−
k upward moves must be made (and the path length is
m). Similarly, there are \binom{n}{r-k} paths starting at (
k,
m−
k) that end at (
r,
m+
n−
r), as a total of
r−
k right moves and (
m+
n−
r) − (
m−
k) upward moves must be made and the path length must be
r−
k + (
m+
n−
r) − (
m−
k) =
n. Thus there are : \binom{m}{k}\binom{n}{r-k} paths that start at (0, 0), end at (
r,
m+
n−
r), and go through (
k,
m−
k). This is a
subset of all paths that start at (0, 0) and end at (
r,
m+
n−
r), so sum from
k = 0 to
k =
r (as the point (
k,
m−
k) is confined to be within the square) to obtain the total number of paths that start at (0, 0) and end at (
r,
m+
n−
r). == Generalizations ==