# Formal proof $\binom{n}{k}$ is an integer

In mathematics one defines:

$\left(\begin{array}{c}n\\k\end{array}\right)=\displaystyle\frac{n!}{k!\cdot (n-k)!}$

This is the number of combinations of $k$ elements from a collection of $n$ elements.

I was wondering if it is possible to prove that the result is an integer in a formal way. It's easy to see that $k!$ in the denominator divides the numerator, but how do you prove that the denominator $k!$ also divides the product of all elements between $n-k+1$ and $n$?

• Basically what you want to know is why $$k!\: | \: n(n-1)(n-2)\cdots(n-k+1)$$ right? One approach is looking at prime factors. Show that for any prime, among all $k$ long products of consecutive (natural) numbers, $k!$ is (tied for) the one with least divisibility by $p$. Oct 7, 2013 at 13:42
• Hint: Apply complete mathetical induction to prove $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$ Oct 7, 2013 at 13:44
• You say that $\binom{n}{k}$ is the number of combinations of $k$ elements from a collection of $n$ elements [1]. If $x$ is equal to an integer, is it not a proof that $x$ itself is an integer? A formal way to express [1] is Newton's binomial theorem. Oct 7, 2013 at 13:47
• Excuse my naivety, but for a list of consecutive numbers of length N, won't there alway be a number in the list divisible by each of $1 \dots N$ ? Oct 7, 2013 at 13:50
• @stevemarvell when I stumbled into this problem last year, and searched for a non-combinatorial solution, I eventually used the counting argument for numbers of the form $p^m$ (you need also power of primes: for example for $n=13$ you first show that there is one multiple of 8, then that there are a total of three multiples of 4, and last that there are a total of six multiples of 2)
– mau
Oct 9, 2013 at 7:59

$$\frac{n!}{k!\cdot (n-k)!} =\frac{n(n-1)\cdots(n-k+1)}{k!} =\frac{(n-k+k)(n-1)\cdots(n-k+1)}{k!}\\ =\frac{(n-1)\cdots(n-k)}{k!}+ \frac{(n-1)\cdots(n-k+1)}{(k-1)!}$$ Now use (double) induction.
This is the relation that defines Pascal's triangle: $${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.$$