The Art Gallery Guardian

Proof that binomial coefficients are integers

Eagle Fantasy asked how to prove that binomial coefficients are integers without induction or counting. He seek a purely number theoretical proof.

One common way to prove a number is a integer is to show it has a integer factorization. Thus one try to demonstrate that {n \choose k} has such factorization.

Let's start by figure out what is the factorization of n!. Consider any prime p. Certainly all numbers from 1 to n that is divisible by p contribute to the exponent by 1, numbers that divisible by p^2 contribute to the exponent by 1, as we already counted one of the p factor already. Similarly, one apply this for all p^i and result p^{\sum_{i=1}^\infty \floor{\frac{n}{p^i}}} | n!, and by unique factorization theorem, we get that \displaystyle n! =\prod_{k=1}^\infty p_k^{\sum_{i=1}^\infty \floor{\frac{n}{p_k^i}}} where p_k is the k-th prime.

Of course, since we are going to manipulate the sum and the product, it is better to replace \infty to some large N so we don't need to define what we mean by infinite product or why we can switch the order of summation, etc.

Now consider the following inequality, left as an exercise to the reader \floor{a+b}\geq \floor{a} + \floor{b}. Then everything follows by easy algebraic manipulation. \displaystyle \begin{aligned} {n\choose k} &= \frac{n!}{(n-k)!k!}\\ &= \frac{\prod_{k=1}^N p_k^{\sum_{i=1}^N \floor{\frac{n}{p_k^i}}}}{\prod_{k=1}^N p_k^{\sum_{i=1}^N \floor{ \frac{n-k}{p_k^i} }} \prod_{k=1}^N p_k^{\sum_{i=1}^N \floor{ \frac{k}{p_k^i} }} }\\ &= \prod_{k=1}^N p_k^{\sum_{i=1}^N \floor{ \frac{n}{p_k^i} } - \floor{ \frac{n-k}{p_k^i} } - \floor{ \frac{k}{p_k^i} }} \end{aligned} Using the previous inequality, we see every exponent is a integer greater or equal to 0. This shows {n\choose k} is a integer.


This also derive the following result: k!|(m+1)\ldots (m+k) for all m\geq 0. One can use this result to prove that multinomial coefficients are integers.

Posted by Chao Xu on 2012-04-23.
Tags: math.