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 (nk){n \choose k} has such factorization.

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

Of course, since we are going to manipulate the sum and the product, it is better to replace \infty to some large NN 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 a+ba+b\floor{a+b}\geq \floor{a} + \floor{b}. Then everything follows by easy algebraic manipulation. (nk)=n!(nk)!k!=k=1Npki=1Nnpkik=1Npki=1Nnkpkik=1Npki=1Nkpki=k=1Npki=1Nnpkinkpkikpki\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 00. This shows (nk){n\choose k} is a integer.

Remark

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

Posted by Chao Xu on .
Tags: math.