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.

Jeffrey Shallit 2009-11-04