7
$\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$
  • $\begingroup$ 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 $\endgroup$ – Lost1 Mar 22 '13 at 14:39
  • $\begingroup$ I would like an algebraic proof $\endgroup$ – Roiner Segura Cubero Mar 22 '13 at 14:50
  • $\begingroup$ For an algebraic proof see math.stackexchange.com/questions/335062/… $\endgroup$ – Martin Brandenburg Mar 22 '13 at 15:36
8
$\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$
2
$\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$
1
$\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$
  • $\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 '16 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 '16 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 '16 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 '16 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 '18 at 17:56
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$

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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.