Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

Question

can you help me with this excercises..

Proof that expression is integer,

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

I've tried for induction!!

$p(1):\frac{(2)!}{2}=1 $

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

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

where,

$$\frac{(2k+2)(2k+1)(2k)!}{(k+1)(k!)(k+2)(k+1)!}=\frac{2(k+1)(2k+1)(2k)!}{(k+1)(k+2)(k!)(k+1)!}$$For hypothesis: $$\frac{2(2k+1)}{(k+2)},$$

how can I follow??

help me??

Answer 1

See $$\frac{(2n)!}{n!(n+1)!} = \frac{(2n)!}{n!n!(n+1)} = {2n \choose n}\frac 1{n+1}$$ Then look at Wikipedia Catalan number.

Answer 2

From wikipedia, I am picking out the relevant part that lends itself to proof by induction -

$C_n$ is the number of ways to correctly match $n$ pairs of brackets (Dyck Language) in a string word consisting of these $n$ pairs of brackets. This means that the number of opening brackets is never less than the number of closing brackets in any substring derived out of the original string starting from its beginning and that the number of opening brackets is equal to the number of closing brackets. We denote a (possibly empty) correct string with $c$ and its inverse (where "$[$" and "$]$" are exchanged) with $c^+$. Since any c can be uniquely decomposed into $c = [ c_1 ] c_2$, summing over the possible spots to place the closing bracket immediately gives the recursive definition -

This definition can be used to easily prove the hypothesis using strong induction principle