Abstract

We prove a linear recursion for the generalized Catalan numbers C_{a}(n) := \frac{1}{(a−1)n+1} \binom{an}{n} when a ≥ 2. As a consequence, we show

p | C_{p}(n) if and only if n ≠ \frac{p^{k}−1}{p−1} for all integers k ≥ 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.