2n choose n [Solution]

The problem was to show that the binomial coefficient $\binom{2n}{n}$ is divisible by $n+1$.

Solution

---

Let $$C = \dfrac{\binom{2n}{n}}{n+1}  = \dfrac{2n!}{n! (n+1)!}$$

$C$ is actually a well known number, it is called a Catalan Number and has numerous combinatorial interpretations. Picking any one such would prove that $C$ is an integer.

But since this is an easy puzzle we will give a short proof.

Now

$$(n+1)C = \dfrac{2n!}{n! n!} = \binom{2n}{n}$$

and

$$nC = \dfrac{2n!}{(n-1)! (n+1)!} = \binom{2n}{n+1}$$

Thus $C = (n+1)C - nC$ is the difference of two binomial coefficients, and is thus an integer.

We can also phrase this as a consquence of:

If $r$ is a rational and $a,b$ are two relatively prime integers such that both $ar$ and $br$ are integers, then $r$ is also an integer.