On the integer valueness of the combinations formula

12 Jan 2022

One of the first beginner counting tasks is choosing \(k\) objects from a pool of \(n\) objects, where the order does not matter. This is denoted as \(n \choose k\), and through some combinatorial reasoning we can derive the algebraically equivalent formula: \(\frac{n!}{k!(n-k)!}\).

This post is motivated by a run-on showerthought that I had one day: can I show algebraically that \(\frac{n!}{k!(n-k)!}\) is an integer?

I tried and failed a couple times over the course of maybe a month. Finally, in the trough of my calculus homework procrastination after I had exhausted every other possible distraction I turned once more towards this problem and banged it all out in 10 minutes.

Theorem

\(n \choose k\) is an integer for nonnegative integers \(n, k\).

Proof

First, write out \(n \choose k\).

\[\frac{n!}{k!(n-k)!} = \frac{n \cdot (n-1) \cdot (n-2) ... (k+1)}{(n-k)!}\]

Then let \(m = n - k\) and substitute.

\[\frac{(m+k) \cdot (m+k-1) \cdot (m+k-2) ... (k+1)}{m!}\]

Induction over m

> Base case, m := 0

When \(m = 0\), this means that \(n = k\). Let them both equal some \(a\). Plugging in, we get

\[\frac{n!}{k!(n-k)!} = \frac{a!}{a!(0)!} = 1\]

1 is a nonnegative integer, so we’re good.

> Inductive hypothesis for m

Assuming

\[\frac{(m+k) \cdot (m+k-1) \cdot (m+k-2) ... (k+1)}{m!}\]

is a nonnegative integer, we want to show

\[\frac{(m+1+k) \cdot (m+k) \cdot (m+k-1) ... (k+1)}{(m+1)!}\]

is also a nonnegative integer.

> Inductive step for m

Distribute terms across the \((m+1)+k\)

\[\frac{(m+1) \cdot (m+k) \cdot (m+k-1) ... (k+1)}{(m+1)!} + \frac{k \cdot (m+k) \cdot (m+k-1) ... (k+1)}{(m+1)!}\]

Consider the former summand. The \(m+1\) terms cancel out, and by IH over m it is a nonnegative integer.

Because the sum of two nonnegative integers is a nonnegative integer, if we show the latter summand is always a nonnegative integer, then we are done.

Induction over k

> Base case, k := 0

Plugging in 0, we get

\[\frac{0 \cdot m \cdot (m-1) ... 1}{(m+1)!} = 0\]

0 is a nonnegative integer, so we’re good.

> Inductive Hypothesis for k

Assuming

\[\frac{k \cdot (m+k) \cdot (m+k-1) ... (k+1)}{(m+1)!}\]

is a nonnegative integer, we want to show

\[\frac{(k+1) \cdot (m+k+1) \cdot (m+k) ... (k+2)}{(m+1)!}\]

is also a nonnegative integer.

> Inductive step for k

Rewrite as

\[\frac{(k+1) \cdot (k+(m+1)) \cdot (m+k) ... (k+2)}{(m+1)!}\]

and do the same thing we did before and distribute across the second term, \(k+(m+1)\):

\[\frac{(k+1) \cdot k \cdot (k+m) ... (k+2)}{(m+1)!} + \frac{(k+1) \cdot (m+1) \cdot (k+m) ... (k+2)}{(m+1)!}\]

Mentally rearranging the order of some terms in our heads, we can see:

• The former summand is a nonnegative integer by IH over k
• The latter summand is a nonnegative integer by IH over m when the \(m+1\) terms cancel

Meaning the total sum is a nonnegative integer. Meaning our original induction over m was shown to be a nonnegative integer, and so we are done. \(n \choose k\) was shown to be a nonnegative integer.