## Integrality of the Catalan Numbers via Kummer’s Theorem

Why is the nth Catalan number, $\binom{2n}{n}/(n+1)$, an integer?  If you know one of its combinatorial interpretations, then the answer is clear, but how do you get integrality strictly from this formula?  In this post I’m going to discuss how one can use Kummer’s Theorem to prove that the Catalan numbers are integers.

Kummer’s Theorem states that the highest power of a prime p dividing the binomial coefficient $\binom{n+m}{n}$ is the number of carries when m and n are added in base p.

Proof.  Assuming we already know that the binomial coefficient $\binom{2n}{n}$ is an integer, we only need to consider primes p that divide $n+1$ in order to prove $\binom{2n}{n}/(n+1)$ is an integer.  So, suppose p is a prime that divides $n+1$.  It may be that $p^2$, or $p^3$, or some higher power of p divides $n+1$ as well.  So let’s let $p^r$ be the highest power of p that divides $n+1$.  Since $p^r | (n+1)$, the base p representation of $n+1$ has r zeros at the end.  (Similarly, the fact that nine thousand, seven hundred has $10^2$ as the highest power of 10 that divides it means that its base 10 representation, 9700, has two zeros at the end.)  This means that the base p representation of n has r instances of $p-1$ at the end.  (In the previous example, we see this with the fact that 9699 has two copies of 9 at the end.)  When n is added to itself in base p, then, we get carries in the ones place, the p‘s place, and so forth, up through at least the $p^{r-1}$ place, for a total of at least r carries.  Thus, by Kummer’s Theorem, $\binom{2n}{n}$ is divisible by $p^r$.  Since we can make a similar argument for all primes p that divide $n+1$, $\binom{2n}{n}$ is divisible by $n+1$.  Therefore, $\binom{2n}{n}/(n+1)$ is an integer.  $\square$

Pomerance makes this argument in his paper [1] and extends it to divisors $n+k$ and $n-k$ instead of $n+1$.  Tom Edgar and I have a paper that will soon be appearing in the Journal of Integer Sequences that generalizes it in another way – to generalized Fuss-Catalan numbers that are formed from generalized binomial coefficients.

References

1.  Carl Pomerance, “On numbers related to Catalan numbers,” preprint.