Generalized Catalan Numbers: Linear Recursion and Divisibility

We prove a linear recursion for the generalized Catalan numbers C-a(n) : = 1/(a-1)n+1 ((an)(n)) when a >= 2. As a consequence, we show p vertical bar Cp(n) if and only if n for not equal 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.