I have to prove by mathematical induction that $\frac{(2n)!}{n!(n+1) !}$ is a natural number for all $n\in\mathbb{N}$.

Question

I have to prove by mathematical induction that $$\frac{(2n)!}{n!(n+1) !}$$ is a natural number for all $n\in\mathbb{N}$.

Any help would be really awesome.

Answer 1

Alternatively, it is quite easy without induction: We know that ${n\choose k}=\frac{n!}{k!(n-k)!}$ is always an integer (namely the number off ways to choose $k$ elements from a set of $n$ elements) and have $$ \frac{(2n)!}{n!(n+1)!}=\frac1{n+1}{2n\choose n}=\frac{1}{2n+1}{2n+1\choose n}.$$ Hence if we write the expression as fraction $\frac ab$ in shortest terms then $b\mid n+1$ and $b\mid 2n+1$. As $\gcd(n+1,2n+1)=1$, the claim follows.

Answer 2

We may try to do induction backwardly.

Let $n \in \mathbb{N}\setminus\{1\}$ be the smallest integer such that $$ \frac{(2n)!}{n!(n+1)!} = \frac{a}{b} $$ for some $a,b \in \mathbb{N}$ such that $(a,b) = 1$ and $a > b$. (Here $n > 1$ because if $n=1$ then the quotient = 1.) Then $$ \frac{(2n-2)!}{(n-1)!n!} = \frac{(2n-1)(2n)n(n+1)(2n-2)!}{n(n+1)(2n-1)(2n)(n-1)!n!} = \frac{n(n+1)}{(2n-1)(2n)}\frac{a}{b} = \frac{n+1}{4n-2}\frac{a}{b} = k $$ for some $k \in \mathbb{N}$. Thus $k = 1$. But then $$ \frac{4n-2}{n+1} = \frac{(2n)!}{n!(n+1)!} = \frac{(2n)\cdots (n+1)}{(n+1)!}, $$ i.e. $$ 1 = \frac{(2n-2)(2n-3)\cdots (n+1)}{(n-1)!}, $$ so $n=1$, a contradiction.