Consider the identity \[\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}\]
- Prove this identity using an “algebraic” proof.
\[\binom{n}{m}\binom{m}{k} = \frac{n!}{m!(n-m)!} \cdot \frac{m!}{k!(m-k)!} = \frac{n!}{k!(n-m)!(m-k)!}\]
\[\binom{n}{k}\binom{n-k}{m-k} = \frac{n!}{k!(n-k)!} \cdot \frac{(n-k)!}{(m-k)!\left((n-k)-(m-k)\right)!} = \frac{n!}{k!(n-k)!} \cdot \frac{(n-k)!}{(m-k)!(n-m)!} = \frac{n!}{k!(n-m)!(m-k)!}\]
So both end results are equal.
- Prove this identity using a “combinatorial” proof.
TBD