Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

Question

I need to prove the following:

If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then

$$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$.

I did the following steps:

\begin{align} \require{cancel} \binom{n}{m}\binom{m}{k} &= \binom{n}{k}\binom{n-k}{m-k} \\ \frac{n!}{m!(n-m)!}\cdot \frac{m!}{k!(m-k)!} &= \frac{n!}{k!(n-k)!}\cdot \frac{(n-k)!}{(m-k)!(n-k-m+k)!}\\ \frac{n!}{\cancel{m!}(n-m)!}\cdot \frac{\cancel{m!}}{k!(m-k)!} &= \frac{n!}{k!\cancel{(n-k)}!}\cdot \frac{\cancel{(n-k)}!}{(m-k)!(n-k-m+k)!} \\ \frac{n!}{k!(n-m)!(m-k)!} &= \frac{n!}{k!(n-m)!(m-k)!} \end{align}

The question is: is my proof correct? Are all my steps valid?

Thanks

Answer 1

It is correct!

An other way to prove this is the following:

$$\binom{n}{m}\binom{m}{k} = \frac{n!}{m!(n-m)!} \frac{m!}{k!(m-k)!}= \frac{n!}{(n-m)!} \frac{1}{k!(m-k)!}=\frac{n!}{k!} \frac{1}{(m-k)!(n-m)!}=\frac{n!}{k!(n-k)!} \frac{(n-k)!}{(m-k)!(n-m)!}=\binom{n}{k}\frac{(n-k)!}{(m-k)!((n-k)-(m-k))!}=\binom{n}{k} \binom{n-k}{m-k}$$

Answer 2

You appear to do this in a non-standard way, but it looks alright (reading the equations from top to bottom instead of left to right).

Ever thought of a combinatoric proof?

Answer 3

Looks correct to me. Alternatively, you can give a combinatorial proof: both sides of the equation count the number of options to choose subsets $K\subseteq M\subseteq N$, where $N$ is a set of $n$ elements, $M\subseteq N$ is a subset of $m$ elements, and $K\subseteq M$ is a subset of $k$ elements. On the LHS you choose $M$ and then choose $K$ in $M$. On the RHS you choose $K$ in $N$ first, and then determine $M$ by choosing $m-k$ more elements from $N\setminus K$.