3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Maybe it is just me, but I am little confused of how you went in one step from $(m-k)!(n-k-m+k)!$ to $(n-m)!(m-k)!$ $\endgroup$ – imranfat Mar 20 '14 at 19:15
  • 1
    $\begingroup$ @imranfat, $(n−k−m+k)!=(n-m)!$. $\endgroup$ – DKal Mar 20 '14 at 19:16
  • 1
    $\begingroup$ Ok, I see it now, there has been a complete brainfart in my head going on... $\endgroup$ – imranfat Mar 20 '14 at 19:24
  • $\begingroup$ Thanks for the edit Umberto! $\endgroup$ – Jeel Shah Mar 20 '14 at 19:32
2
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ The back of the book suggested that I use the following fact $\binom{n+1}{k+1} = \frac{n+1}{k+1}\binom{n}{k}$. How would I use that? Also, on the second last portion i.e. $(n-m)!$ going to $((n-k)-(m-k))!$ is that because we have $n = n-k$ and $m=m-k$? $\endgroup$ – Jeel Shah Mar 20 '14 at 19:31
  • $\begingroup$ As regards the second question: $$(n-m)!=(n-m+0)!=(n-m+k-k)!=(n-k-m+k)!=((n-k)-(m-k))!$$ $\endgroup$ – Mary Star Mar 20 '14 at 19:34
  • 1
    $\begingroup$ To use the relation $$\binom{n+1}{k+1}=\frac{n+1}{k+1} \binom{n}{k}$$ you could do the following: $$\binom{n}{m}=\frac{n}{m} \binom{n-1}{m-1}=...=\frac{n \cdot ... \cdot (n-k+1)}{m \cdot ... \cdot (m-k+1)} \binom{n-k}{m-k}=\frac{\frac{n!}{(n-k)!}}{\frac{m!}{(m-k)!}} \binom{n-k}{m-k}=\frac{\frac{n!}{k!(n-k)!}}{\frac{m!}{k!(m-k)!}} \binom{n-k}{m-k}= \frac{ \binom{n}{k} }{ \binom{m}{k} } \binom{n-k}{m-k}$$ So $$\binom{n}{m} \binom{m}{k}= \frac{ \binom{n}{k} }{ \binom{m}{k} } \binom{n-k}{m-k} \binom{m}{k}= \binom{n}{k} \binom{n-k}{m-k}$$ $\endgroup$ – Mary Star Mar 20 '14 at 22:41
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.