0

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}$

user300045
  • 3,449
  • 1
    These are the Catalan numbers . See for example here : https://en.wikipedia.org/wiki/Catalan_number –  Oct 17 '15 at 20:14

2 Answers2

2

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$.

Jack D'Aurizio
  • 353,855
-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! ;-)

Ant
  • 21,098
  • For $2k$ to be in the numerator you need $2k \geq n+2$ or $k \geq \frac{n}{2}+1$ but you claim that this works for every $k \leq n$ . –  Oct 17 '15 at 20:21
  • @ComplexPhi ops, you're right! I fixed :-) – Ant Oct 17 '15 at 20:24
  • There is still a gap .There are $n-1$ numbers in the numerator and $n$ numbers in the denominator so you can't "pair" the terms like this because there are less terms in the numerator . To convince yourself try for some small example : $n=5$ .You'll see what I mean . –  Oct 17 '15 at 20:30
  • @ComplexPhi while it's not rigorous, I believe it works. You have $n$ numbers in the denominator but one of them is $1$, (so already we have $n-1$ terms on both sides) and another one of them is $2$, of which we have plenty of factors. – Ant Oct 18 '15 at 09:50