Prove that $\frac{1}{n + 1}{2n\choose n}$ is a positive integer for $n \ge 0$.

Question

I attempted to use Pascal's triangle identity to help out, but I do not know how to deal with $\frac{1}{n+1}$.

Answer 1

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.

Answer 2

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