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