prove $\sum_{k = 0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}$ prove $\sum_{k = 0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}$ Attempt:I was thinking of trying to prove this through induction, but I am having trouble with a base case: base case: let $n = 2$: $$LHS = \binom{2}{0} \binom{m-2}{2} + \binom{2}{1} \binom{m-2}{1} + \binom{2}{2} \binom{m-2}{0} \\\ = \frac{(m-2)[(m-3) + 2!2!(m-3)!] + 2!}{2!} \ (after\ simplification)$$ $$RHS = \frac{m!}{2!(m-2)!}$$ But I am stuck as what to try next to at least equate these two expressions. Note: I took a look at Vandermonde's identity on wikipedia and the ensuing proof, but the proof still leaves out how to make the transition between the two initial expressions

Use Pascal’s identity a few times:

$$\begin{align*} \binom20\binom{m-2}2+\binom21\binom{m-2}1+\binom22\binom{m-2}0&=\binom{m-2}2+2\binom{m-2}1+\binom{m-2}0\\\ &=\left(\binom{m-2}2+\binom{m-2}1\right)+\\\ &\qquad\qquad\left(\binom{m-2}1+\binom{m-2}0\right)\\\ &=\binom{m-1}2+\binom{m-1}1\\\ &=\binom{m}2\;. \end{align*}$$

But why start at $n=2$? Starting at $n=0$ makes the base case very simple.