Factors of Binomial Coefficients

Theorem

For all $r \in \R, k \in \Z$:

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

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

Hence:

$\displaystyle \binom r k = \frac r k \binom {r - 1} {k - 1}$ (if $k \ne 0$)

and:

$\displaystyle \frac 1 r \binom r k = \frac 1 k \binom {r - 1} {k - 1}$ (if $k \ne 0$ and $r \ne 0$)

Also, for all $r \in \R, k \in \Z$:

$\displaystyle \left ({r - k}\right) \binom r k = r \binom {r - 1} k$

from which:

$\displaystyle \binom r k = \frac r {r - k} \binom {r - 1} k$ (if $r \ne k$)

Proof

If $k = 0$ then $\displaystyle \binom r k = \binom {r - 1} {k - 1} = 0$ by definition.

Otherwise:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle k \binom r k\)	\(=\)	\(\displaystyle k \frac {r^{\underline k} } {k!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k \frac {r \left({r - 1}\right) \left({r - 2}\right)\cdots \left({r - k + 1}\right)} {k \left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {r \left({r - 1}\right) \left({r - 2}\right)\cdots \left({r - k + 1}\right)} {\left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle r \frac {\left({r - 1}\right) \left({r - 2}\right)\cdots \left({\left({r - 1}\right) - \left({k - 1}\right) + 1}\right)} {\left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle r \binom {r - 1} {k - 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

If $k \ne 0$, we can divide both sides of:

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

by $k$ to obtain:

$\displaystyle \binom r k = \frac r k \binom {r - 1} {k - 1}$

$\blacksquare$

If $k \ne 0$ and $r \ne 0$, we can divide both sides of:

$\displaystyle \binom r k = \frac r k \binom {r - 1} {k - 1}$

by $r$ to obtain:

$\displaystyle \frac 1 r \binom r k = \frac 1 k \binom {r - 1} {k - 1}$

$\blacksquare$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r \binom {r - 1} k\)	\(=\)	\(\displaystyle r \frac {\left({r - 1}\right) \left({\left({r - 1}\right) - 1}\right) \cdots \left({\left({r - 1}\right) - k + 2}\right) \left({\left({r - 1}\right) - k + 1}\right)} {k \left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {r \left({r - 1}\right) \left({r - 2}\right) \cdots \left({r - k + 1}\right) \left({r - k}\right)} {k \left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({r - k}\right) \frac {r \left({r - 1}\right) \left({r - 2}\right) \cdots \left({r - k + 1}\right)} {k \left({k - 1}\right) \left({k - 2}\right) \cdots 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({r - k}\right) \binom r k\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

Finally:

$\displaystyle \binom r k = \frac r {r - k} \binom {r - 1} k$

follows from the

$\displaystyle \left ({r - k}\right) \binom r k = r \binom {r - 1} k$

by dividing both sides by $r - k$.

$\blacksquare$

Sources

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