Product of r Choose m with m Choose k

Theorem

Let $r \in \R, m \in \Z, k \in \Z$.

Then:

$\displaystyle \binom r m \binom m k = \binom r k \binom {r - k} {m - k}$

where $\displaystyle \binom r m$ is a binomial coefficient.

Proof

Let $r \in \Z$.

Integral Index

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \binom r m \binom m k\)	\(=\)	\(\displaystyle \frac {r^{\underline m} } {m!} \frac {m^{\underline k} } {k!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {r! m!} {m! \left({r - m}\right)! k! \left({m - k}\right)!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {r! \left({r - k}\right)!} {k! \left({r - k}\right)! \left({m - k}\right)! \left({r - m}\right)!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \binom r k \binom {r - k} {m - k}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\Box$

Real Index

Both sides of the above equation are polynomials in $r$.

Since these polynomials agree for all $r \in \Z$, they must agree for all $r \in \R$.

$\blacksquare$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968) $\S 1.2.6 \ \text {H} \ (20)$