Journal of Integer Sequences, Vol. 12 (2009), Article 09.7.5

Generalized Catalan Numbers: Linear Recursion and Divisibility

B. Sury
Stat-Math Unit
Indian Statistical Institute
8th Mile Mysore Road
Bangalore 560059


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A000108.)

Received May 21 2009. revised version received October 28 2009. Published in Journal of Integer Sequences, November 4 2009.

Return to Journal of Integer Sequences home page