Prove that $\frac{1}{n + 1}{2n\choose n}$ is a positive integer for $n \ge 0$. I attempted to use Pascal's triangle identity to help out, but I do not know how to deal with $\frac{1}{n+1}$.
 A: Approach 1:
Note that
$$
\frac{2n+1}{n+1}\overbrace{\ \ \binom{2n}{n}\ \ }^{\large\frac{(2n)!}{n!\,n!}}=\overbrace{\binom{2n+1}{n+1}}^{\large\frac{(2n+1)!}{(n+1)!\,n!}}
$$
Then, because $\frac1{n+1}=2-\frac{2n+1}{n+1}$, we have
$$
\begin{align}
\frac1{n+1}\binom{2n}{n}
&=2\binom{2n}{n}-\frac{2n+1}{n+1}\binom{2n}{n}\\
&=2\binom{2n}{n}-\binom{2n+1}{n+1}
\end{align}
$$

Approach 2:
Note that
$$
\frac{n}{n+1}\overbrace{\ \ \binom{2n}{n}\ \ }^{\large\frac{(2n)!}{n!\,n!}}=\overbrace{\binom{2n}{n+1}}^{\large\frac{(2n)!}{(n+1)!\,(n-1)!}}
$$
Then, because $\frac1{n+1}=1-\frac{n}{n+1}$, we have
$$
\begin{align}
\frac1{n+1}\binom{2n}{n}
&=\binom{2n}{n}-\frac{n}{n+1}\binom{2n}{n}\\
&=\binom{2n}{n}-\binom{2n}{n+1}
\end{align}
$$
A: The combinatorial approach is to notice that $\frac1{n+1} \binom{2n}{n}$ is the $n^{\text{th}}$ Catalan number, so it's an integer because it counts something.
Algebraically, one possible approach is to notice that
$$
   \frac1{n+1} \binom{2n}{n} = \frac{(2n)!}{n!\,(n+1)!} = \frac1{2n+1} \binom{2n+1}{n}.
$$
From the left expression, we know the denominator of the fraction is a divisor of $n+1$. From the right expression, we know the denominator is a divisor of $2n+1$. 
But the only positive integer that's a divisor of both $n+1$ and $2n+1$ is $1$: one way to see this is that a divisor of $n+1$ and $2n+1$ is a divisor of $2(n+1)-1(2n+1) = 1$. So the denominator can only be $1$; the fraction is an integer.
