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

• what have you tried? 1 approach is writing out the factorials, 1 appraoch is to intepret what each of the term means, in combinatoric terms. Take your pick – Lost1 Mar 22 '13 at 14:39
• I would like an algebraic proof – Roiner Segura Cubero Mar 22 '13 at 14:50
• For an algebraic proof see math.stackexchange.com/questions/335062/… – Martin Brandenburg Mar 22 '13 at 15:36

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

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$. – arkeet Oct 5 '16 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. – g------ Oct 5 '16 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$.) – arkeet Oct 5 '16 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. – g------ Oct 5 '16 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$. – g------ Apr 3 '18 at 17:56

$$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}{\left\langle #1 \right\rangle}% \newcommand{\braces}{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}{\displaystyle{#1}}% \newcommand{\equalby}{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}{\,{\rm e}^{#1}\,}% \newcommand{\floor}{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}{\left\vert #1\right\rangle}% \newcommand{\pars}{\left( #1 \right)}% \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}}% \newcommand{\verts}{\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$$

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