Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$

Question

Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$

I used induction, for $n=k$ assume that

$\frac{(2k)!}{k!(k+1)!}\in \mathbb{N}$

For $n=k+1$

$\frac{(2k+2)!}{(k+1)!(k+2)!}\in \mathbb{N}$

$x=\frac{(2k+2)!}{(k+1)!(k+2)!}\cdot \frac{k!(k+1)!}{(2k)!}\notin \mathbb{N}$

If $x \notin\mathbb{N}$ then how to prove $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$

Answer 1

The Catalan numbers: $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ satisfy the recurrence relation: $$ C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} $$ hence they are integers, since $C_0=C_1=1$.

Answer 2

$$\frac{(2n)!}{n!(n+1)!} = \frac{(n+2)\cdots (n+n)}{n!}$$

since for every number $k\le n$ there exists a number $m$ such that $ n+2 \le mk\le2n$, for any factor in the denominator there is that factor (and then some) in the numerator. Hence it's an integer

---

Here is why I don't think induction is a good idea:

$$\frac{(2k+2)!}{(k+1)!(k+2)!} = \frac{(2k+2)(2k+1)(2k)!}{(k+1)(k+2)(k+1)!k!} = \frac{(2k+2)(2k+1)}{(k+1)(k+2)} \cdot \frac{(2k)!}{(k+1)!k!} = $$$$= \frac{2(2k+1)}{k+2} \cdot \frac{(2k)!}{(k+1)!k!}$$

Now if $\displaystyle \frac{2(2k+1)}{k+2}$ was an integer, induction would work perfectly. But it's not an integer! So you need to show somehow that $k+2$ divides the factor on the right.. But then the induction hypothesis is useless and you are better off just proving the result directly! ;-)