Verify the following identity algebraically

Question

Verify the following identity algebraically (writing out the binomial coefficients as factorials).$${n \choose k}{k \choose m} = {n \choose m}{n-m \choose k-m}$$

So far, these are my steps:

1. $$\frac{n!}{k!(n-k)!} \cdot \frac{k!}{m!(k-m)!}= \frac{n!}{m!(n-m)!} \cdot \frac{(n-m)!}{(k-m)!([n-m]-[k-m])!}$$

2. $$\frac{n!k!}{k!m!(n-k)!(k-m)!} = \frac{n!(n-m)!}{m!(n-m)!(k-m)!([n-m]-[k-m])!}$$

3. $$\frac{n!}{m!(n-k)!(k-m)!} = \frac{n!}{m!(k-m)!(n-k)!}$$

These two equations equal each other, but can I stop my algebraic proof here, or is there more that I need to elaborate on? Is there something I'm missing?

Answer 1

While your intuition is correct, when you actually present the proof, you need to start off with #3 first and then work your way up to #1. At the moment, you're assuming #1 is already true which is false.

1. $\frac{n!}{m!(n-k)!(k-m)!} = \frac{k!n!}{k!m!(n-k)!(k-m)!} = \frac{n!}{k!(n-k)!} \cdot \frac{k!}{m!(k-m)!} = {n \choose k}{k \choose m} $

2. $\frac{n!}{m!(n-k)!(k-m)!} = \frac{n!(n-m)!}{m!(n-m)!(k-m)!(n-m)!} = \frac{n!(n-m)!}{m!(n-m)!(k-m)!([n-m]-[k-m])!} = \frac{n!}{m!(n-m)!} \cdot \frac{(n-m)!}{(k-m)!([n-m]-[k-m])!} = {n \choose m}{n-m \choose k-m}$

$\therefore {n \choose k}{k \choose m} = {n \choose m}{n-m \choose k-m}$

Answer 2

BirdKr is correct in saying that the argument needs to be reorganized. As it stands, you appear to be arguing that since we can deduce a true statement from the desired equality, that equality must be true. Of course this isn’t generally the case: if we start with $1=-1$, we can square both sides to get the true statement $1=1$, but we can’t therefore conclude that $1=-1$. It’s not true, however, that you need to start off with $(3)$ and work back to $(1)$, though that is certainly a fine way to present the argument. There are at least two other very natural ways to present it.

First, you can simply point out that each step in your derivation is reversible: not only does $(1)$ imply $(2)$, for instance, but also $(2)$ implies $(1)$. If you add this observation, you don’t need to reverse the order of presentation.

Alternatively, you can work down one side and up the other:

$$\begin{align*} \binom{n}k\binom{k}m&=\frac{n!}{k!(n-k)!}\cdot\frac{k!}{m!(k-m)!}\\ &=\frac{n!k!}{k!m!(n-k)!(k-m)!}\\ &=\frac{n!}{m!(n-k)!(k-m)!}\\ &=\frac{n!(n-m)!}{m!\big((n-m)-(k-m)\big)!(k-m)!(n-m)!}\\ &=\frac{n!}{(n-m)!}\cdot\frac{(n-m)!}{(k-m)!\big((n-m)-(k-m)\big)!}\\ &=\binom{n}m\binom{n-m}{k-m} \end{align*}$$

The main point to remember is that the organization of the proof need not (and often cannot) be the same as the train of thought or calculation that led you to it. It’s a good idea to bear in mind that finding a proof and then organizing it correctly and readably for presentation are separate tasks.

In this case my own preference is for the last alternative that I suggested: it shows pretty clearly how the natural rewritings of the two sides meet in the middle and seems to me to be closer to the intuition than the approach of starting at $(3)$ and working both sides upwards. My first alternative is fine if one is sufficiently experienced, but it can be a little risky for a beginner: there’s a temptation to assert reversibility without actually checking to make sure that all of the steps actually are reversible.