10
$\begingroup$

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.

$\endgroup$
1

7 Answers 7

19
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – arkeet
    Oct 5, 2016 at 1:23
  • $\begingroup$ @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. $\endgroup$
    – g------
    Oct 5, 2016 at 1:34
  • 1
    $\begingroup$ 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$.) $\endgroup$
    – arkeet
    Oct 5, 2016 at 1:43
  • $\begingroup$ @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. $\endgroup$
    – g------
    Oct 5, 2016 at 1:48
  • $\begingroup$ @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$. $\endgroup$
    – g------
    Apr 3, 2018 at 17:56
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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 $$
$\endgroup$
0
$\begingroup$

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!!)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .