Generalized Catalan numbers: linear recursion and divisibility

Sury, B.

Journal of integer sequences, Tome 12 (2009) no. 7

Résumé

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.

Détail

Classification : 05A10, 11B83
Keywords: generalized Catalan numbers, linear recursion, divisibility