We prove a linear recursion for the generalized Catalan numbers when . As a consequence, we show if and only if for all integers . This is a generalization of the well-known result that the usual Catalan number is odd if and only if is a Mersenne number . Using certain beautiful results of Kummer and Legendre, we give a second proof of the divisibility result for . We also give suitably formulated inductive proofs of Kummer's and Legendre's formulae which are different from the standard proofs.