Prove that $(2n)!$ is always divisible by $n!\cdot(n+1)!$

Question

Prove that $(2n)!$ is always divisible by $n!(n+1)!$.

Context: I am a beginner in number theory. To build up my foundation I am following the book Higher Algebra by S. Barnard and J.M. Child.

I know that the problem could be easily solved by doing simple algebraic manipulation and arguing that Catalan numbers are always integers, but I am wondering if there is another approach to attack this problem, particularly using Legendre's formula.

Answer 1

Write it in lowest terms; what is its denominator?

Since it is $\frac1{n+1}\binom{2n}n$, the denominator must divide $n+1$.

Since it is $\frac{1}{2n+1}\binom{2n+1}n$, the denominator must divide $2n+1$.

Since $n+1$ and $2n+1$ are coprime, the denominator must be $1$.

Answer 2

Because $$\frac{(2n)!}{n!(n+1)!}=4\binom{2n-1}{n}-\binom{2n+1}{n}$$