Can someone help me prove these two binomial identities using either walks in Pascal's triangle or a committee-selection model?
$(1)$ $\qquad$ $\displaystyle\sum_{k=0}^m {m\choose k}{n\choose r+k}={m+n\choose m+r}$
$(2)$ $\qquad$ $\displaystyle\sum_{k=n-s}^{m-r} {m-k\choose r}{n+k\choose s}={m+n+1\choose r+s+1}$
I couldn't find these identities in another question already asked on here. If I just wasn't looking in the right place, feel free to leave the link to the answer. Thanks!
You can rewrite the lefthand side of the first as
$$\sum_{k=0}^m\binom{m}k\binom{n}{n-r-k}\;;$$
the Vandermonde identity then says that this is equal to
$$\binom{m+n}{n-r}=\binom{m+n}{m+n-(n-r)}=\binom{m+n}{m+r}\;.$$
The linked Wikipedia article has a combinatorial proof of Vandermonde’s identity; try to adapt it to give the desired result. There are also combinatorial proofs of various forms of it on this site; searching for it by name will turn up most of them.
The second identity isn’t quite right: the lower limit of summation should be $s-n$, not $n-s$, making it
$$\sum_{k=s-n}^{m-r} {m-k\choose r}{n+k\choose s}={m+n+1\choose r+s+1}\;;\tag{1}$$
If we let $\ell=n+k$, so that $k=\ell-n$, $(1)$ can be rewritten
$$\sum_{\ell=s}^{m+n-r}\binom{m+n-\ell}r\binom{\ell}s=\binom{m+n+1}{r+s+1}\;.\tag{2}$$
Let $A=\{0,1,\ldots,m+n\}$, and note that $|A|=m+n+1$. Suppose that we’re to select $r+s+1$ elements of the set $A$, and we want to know how many different subsets are possible. (If you like, you can easily rephrase this in terms of selecting a committee of $r+s+1$ from a pool of $m+n+1$ candidates.) Of course the righthand side of $(2)$ is the correct number; our task is to find a way to count these subsets that naturally yields the lefthand side of $(2)$.
Suppose that $S$ is one of these subsets. There is a unique $\ell_S\in S$ such that exactly $s$ elements of $S$ are less than $\ell_S$, and exactly $r$ elements of $S$ are greater than $\ell_S$. Clearly $\ell_S$ must be at least $\ell$, the smallest member of $A$ such $A$ contains $\ell$ smaller numbers. On the other hand, $\ell_S$ cannot be any larger than $m+n-r$, the largest member of $A$ such that $A$ has $r$ larger elements.
For each integer $\ell$ such that $s\le\ell\le m+n-r$ let $\mathscr{S}_\ell$ be the set of all subsets $S$ of $A$ such that $\ell_S=\ell$; you can finish the argument by showing that
$$|\mathscr{S}_\ell|=\binom{m+n-\ell}r\binom{\ell}s\;.$$
