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.

  • 3
    $\begingroup$ It looks ok and natural to me, except that $\binom{n}{2n}$ should be $\binom{2n}{n}$ $\endgroup$
    – lhf
    Commented Sep 24, 2021 at 10:48
  • 1
    $\begingroup$ See also en.wikipedia.org/wiki/Catalan_number#Properties $\endgroup$
    – lhf
    Commented Sep 24, 2021 at 10:50
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Sep 24, 2021 at 10:54
  • $\begingroup$ @Peter: Yeah, I will probably add them later $\endgroup$
    – univalence
    Commented Sep 24, 2021 at 11:16
  • 2
    $\begingroup$ 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.) $\endgroup$ Commented Sep 24, 2021 at 13:27


You must log in to answer this question.

Browse other questions tagged .