# How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?

How can we prove that

$$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$

(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.

Suppose you have to select n balls from a collection of $R$ black balls and $M$ white balls.

Then we must select $k$ black balls and $n-k$ white balls in whatever way we do.(for $0\le k\le n$)

For a fixed $k\in N,0\le k\le n$ we can do this in $\binom{R}{k}\binom{M}{(n-k)}$ ways.

so to get the total no. of ways we must add the above for all $k:0\le k\le n$

So we have the total no. of ways $=\displaystyle\sum_{k=0}^{n} \binom{R}{k}\binom{M}{(n-k)}$.

But if we think about it in a different way we can say that we have to select $n$ balls from a collection of $R+M$ balls and this can be done in $\displaystyle \binom{R+M}{n}$ ways.

So ,

$$\displaystyle\sum_{k=0}^{n} \binom{R}{k}\binom{M}{(n-k)}=\displaystyle \binom{R+M}{n}$$

(Reproduced from there.)

Since ${R\choose k}$ is the coefficient of $x^k$ in the polynomial $(1+x)^R$ and ${M\choose n-k}$ is the coefficient of $x^{n-k}$ in the polynomial $(1+x)^M$, the sum $S(R,M,n)$ of their products collects all the contributions to the coefficient of $x^n$ in the polynomial $(1+x)^R\cdot(1+x)^M=(1+x)^{R+M}$.

This proves that $S(R,M,n)={R+M\choose n}$.

It can be proven combinatorially by noting that any combination of $r$ objects from a group of $m+n$ objects must have some $0\le k\le r$ objects from group $m$ and the remaining from group $n$.

Consider the $K\times K$ matrix $$B= \left[ \begin{array}{ccccccc} 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 1 & 1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & 1 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ & & & \ddots & & & \\ 0 & 0 & 0 & \cdots & 1 & 1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\ \end{array} \right]$$

When it is multiplied by $K\times 1$ vectors, which starts with k-1st row of Pascals's triangle, the result is a $K\times 1$ vector which contains the 1st $K$ elements of kth row of Pascal's triangle. This is because it effectively mimics addition of elements of k-1st row of Pascal's triangle to produce kth row of Pascal's triangle. Except that it only does it for the 1st $K$ elements of a row. In particular, $$B \times \left[ \begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right] =\left[ \begin{array}{c} 1 \\ 1 \\ \vdots \\ 0 \end{array} \right]$$ $$B\times B \times \left[ \begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right] =B\times \left[ \begin{array}{c} 1 \\ 1 \\ \vdots \\ 0 \end{array} \right] =\left[ \begin{array}{c} 1 \\ 2 \\ 1 \\ \vdots \\ 0 \end{array} \right]$$

It is an easy proof that all powers of $B$ are symmetric with respect to their antidiagonal (just consider $B$ as a sum of $I$ and $N=B-I$ and then look at the expansion of $(I+N)^m$). If we designate $\left[ \begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right]$ as the zeroth row of Pascal's triangle, then the vector containing the 1st $K$ elements of $m$'s row of Pascal's triangle is $$B^m \times \left[ \begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right],$$ which is the 1st column of $B^m$ (and by the symmetry, the last row of $B^m$).

Now set the $K$ (of this answer) equal to $n$ (of the posited question).

Then the left-hand side of the identity can be considered to be the dot product of $nth$ row of $B^R$ and 1st column of $B^M$, which is the $(n,1)$ element of $B^{R+M}$. Which also happens to be the right-hand side of the identity (in the posited question).

• That's a new way of looking at it! We can relate this proof to polynomials: With respect to the basis $\{1,t,t^2,\ldots\}$ of the vector space of polynomials in $t$, $B$ is the linear map that represents multiplication by $1+t$. Then your claim is equivalent to saying that the $t^n$ coefficient of $(1+t)^{R+M}$ is the sum over $k$ of the $t^n$ coefficient of $(1+t)^R t^k$ times the $t^k$ coefficient of $(1+t)^M$. Oct 5, 2016 at 1:23
• @arkeet, I think polynomial calculation comes from Vandermonde's Identity itself. I actually came across this matrix calculation when trying to find a faster way to calculate first k elements of nth row of Pascal's triangle (for arbitrarily large n). Because it reduces to calculating a power of a matrix (which is further simplified by the symmetry), the calculation becomes $O(\log n)$ instead of $O(n)$, where $n$ is the row. Oct 5, 2016 at 1:34
• Yup. You can also do the same with polynomials without appealing to any symmetries, and compute $(1+t)^n$ with $O(\log n)$ operations on polynomials. (And if all you need is the first $k$ elements you can just work modulo $t^k$.) Oct 5, 2016 at 1:43
• @arkeet, actually, yeah, that's pretty good. The polynomial calculation shows how to construct the elements without considering the symmetry while the matrix calculation proves (or at least motivates) why the polynomial calculation works. Oct 5, 2016 at 1:48
• @arkeet, I just realized, that you can incorporate the calculation in terms of $\{t^i\}$ basis directly here. If you put the $t$'s, instead of 1's, below the diagonal in $B$, then you would be able to read off the values of $(1+t)^M$ by multiplying $M$th power of the matrix by $[1\ 0\ ...\ 0]^T$. Apr 3, 2018 at 17:56

Using a coefficient-extractor e.g. $$[z^k] (1+z)^n = {n\choose k}$$, we find

$$\sum_{k=0}^n {R\choose k} {M\choose n-k} = \sum_{k=0}^n {R\choose k} [z^{n-k}] (1+z)^M \\ = [z^n] (1+z)^M \sum_{k=0}^n {R\choose k} z^k.$$

Now we may extend $$k$$ to infinity because the coefficient extractor $$[z^n]$$ makes from a zero contribution from multiples of $$z^k$$ where $$k\gt n.$$ We find

$$[z^n] (1+z)^M \sum_{k\ge 0} {R\choose k} z^k \\ = [z^n] (1+z)^M (1+z)^R = [z^n] (1+z)^{R+M} = {R+M\choose n}.$$

This example is included here to illustrate the coefficient extractor technique which also yields more sophisticated results as shown e.g. at the following MSE link.

$$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$$ \begin{align} \pars{1 + x}^{R + M}&=\sum_{k = 0}^{R + M}{R + M \choose k}x^{k} \\ \pars{1 + x}^{R}\pars{1 + x}^{M} &=\sum_{\ell = 0}^{R}{R \choose \ell}x^{\ell}\sum_{\ell' = 0}^{M}{M \choose \ell'}x^{\ell'}\sum_{k = 0}^{R + M}\delta_{k,\ell + \ell'} \\[3mm]&= \sum_{k = 0}^{R + M}x^{k}\sum_{\ell = 0}^{R}{R \choose \ell} \sum_{\ell' = 0}^{M}{M \choose \ell'}\delta_{\ell',k - \ell} \\[3mm] & = \left.\sum_{k = 0}^{R + M}x^{k}\sum_{\ell = 0}^{R}{R \choose \ell} {M \choose k - \ell}\right\vert_{0 \leq k - \ell \leq M} \end{align}

$$\color{#0000ff}{\large% {R + M \choose k} = \sum_{\ell = 0 \atop {\vphantom{\LARGE A^{a}}k - M \leq\ \ell\ \leq k}} ^{R}{R \choose \ell}{M \choose k - \ell}}\,, \qquad 0 \leq k \leq R + M$$

Here's a different way of doing it! Unfortunately I don't really know how to use latex, so here is the outline

Using the residue theorem, we know that $${n \choose k}$$ equals the contour integral of

$$(1+z)^N / z^{k+1}) {/}(2*pi*i)$$

where $$z$$ is restricted to the unit circle, i.e. its magnitude is 1.

Now we write out the sum, but writing the $${R \choose k}$$ term as its complex integral representation.

Now bring the sum inside the integral. Rearrange, and use the fact that a contour integral of a function without a singularity equals 0 (so you can add terms without singularities at will). You will get the contour integral of

$$(1+z)^{R+M} / z^{N+1}) {/}(2*pi*i)$$

as required.

(I will try and remember to update this when my latex skills improve!!)