Why is the nth Catalan number, , 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 is the number of carries when m and n are added in base p.
Proof. Assuming we already know that the binomial coefficient is an integer, we only need to consider primes p that divide
in order to prove
is an integer. So, suppose p is a prime that divides
. It may be that
, or
, or some higher power of p divides
as well. So let’s let
be the highest power of p that divides
. Since
, the base p representation of
has r zeros at the end. (Similarly, the fact that nine thousand, seven hundred has
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
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
place, for a total of at least r carries. Thus, by Kummer’s Theorem,
is divisible by
. Since we can make a similar argument for all primes p that divide
,
is divisible by
. Therefore,
is an integer.
Pomerance makes this argument in his paper [1] and extends it to divisors and
instead of
. 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
- Carl Pomerance, “On numbers related to Catalan numbers,” preprint.