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.
 A: (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}$.
A: 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).
A: 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$.
A: 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}$$
A: $\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
$$

A: 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.
A: 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!!)
