# Simple proof that the Catalan numbers are integers

As the Catalan numbers are defined as $$C_n = \frac{1}{n+1} \binom{2n}{n},$$ it is not immediately clear that they are integers.

To show that they are, there's a relatively basic approach involving some binomial identities, but I wanted to avoid most of these, so I tried the following.

To show that $$C_n$$ is integer, it obviously suffices to show that $$n + 1 \mid \binom{2n}{n}$$. Given $$n$$, we can see that $$\binom{2n}{n+1} = \frac{n}{n+1} \binom{2n}{n}$$ by manipulating the fractions a little. Thus, $$\binom{2n}{n+1} (n+1) = n \binom{2n}{n},$$ and therefore $$n + 1 \mid n \binom{2n}{n}$$. Since $$n$$ and $$n+1$$ are coprime, $$n+1 \mid \binom{2n}{n}$$, which should complete the proof.

Is this proof correct? For some reason, it feels like there's something off with it, although I can't see any mistakes.

• It looks ok and natural to me, except that $\binom{n}{2n}$ should be $\binom{2n}{n}$
– lhf
Commented Sep 24, 2021 at 10:48
• – lhf
Commented Sep 24, 2021 at 10:50
• It would have been nice if you would have shown the $2-3$ steps to derive the given idendity, but the conclusion at the end is utterly valid. Commented Sep 24, 2021 at 10:54
• @Peter: Yeah, I will probably add them later Commented Sep 24, 2021 at 11:16
• A simpler deduction from the second displayed equation is: $$C_n = \binom{2n}n - \binom{2n}{n + 1}.$$ (In fact, this is the first proposition in the Wikipedia link given by @lhf. Still, it's worth repeating here.) Commented Sep 24, 2021 at 13:27