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.
Like this:
Like Loading...
Related
