next up previous
Next: About this document ...


We prove a linear recursion for the generalized Catalan numbers $C_a(n) := \frac{1}{(a-1)n+1} {an \choose n}$ when $a \geq
2$. As a consequence, we show $p \, \vert \, C_p(n)$ if and only if $n \neq \frac{p^k-1}{p-1}$ for all integers $k \geq 0$. This is a generalization of the well-known result that the usual Catalan number $C_2(n)$ is odd if and only if $n$ is a Mersenne number $2^k-1$. Using certain beautiful results of Kummer and Legendre, we give a second proof of the divisibility result for $C_p(n)$. We also give suitably formulated inductive proofs of Kummer's and Legendre's formulae which are different from the standard proofs.

Jeffrey Shallit 2009-11-04