Induction proof: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.

Question

Prove using induction: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.

I tried but I can't do it.

Answer 1

Check out this question, as $$ \binom{n}{k} = \frac{n^{\underline{k}}}{k!} $$ where $u^{\underline{k}} = u (u - 1) \ldots (u - k + 1)$, this implies that all binomial coefficients are integers.

Answer 2

Here I've assumed that $\binom{2n}{n+1}$ is an integer for the proof...

We induct on two things: $1)$ $n+1 \mid \binom{2n}{n}$ and $2)$ $\binom{2n}{n}$ is an integer.

These are both easily checked for $n=1,$ so now we assume it holds for $n-1$. Then for $\binom{2n}{n} = \frac{(2n)!}{n!n!} = \frac{(2n-2)!(2n-1)(2n)}{(n-1)!(n-1)! n^2} = \binom{2n-2}{n-1}\frac{2(2n-1)}{n},$ we have by the inductive hypothesis that $n$ divides $\binom{2n-2}{n-1},$ so we are done. Now it suffices to show that $n+1 \mid \binom{2n}{n},$ but this follows from $\frac{n}{n+1}\binom{2n}{n} = \binom{2n}{n+1},$ so we are done.

Answer 3

This is one instance of a strange phenomenon: proving something seemingly more complicated makes things simpler.

Show that $\binom{n}{k}$ is an integer for all $0\leq k\leq n$, and that will show what you want. To do so, show by induction on $n$ that $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}.$$

Answer 4

We could cheat and prove a more general result. Suppose that for all $k$ with $-\le k\le n$, the binomial coefficient $\binom{n}{k}$, or more properly $\frac{n!}{k!(n-k)!}$ is an integer. Then from the easily verified "Pascal" identity $$\binom{n+1}{j}=\binom{n}{j}+\binom{n}{j-1},$$ the desired result holds for $\binom{n+1}{j}$ for all $j$ with $0\le j\le n+1$.

Of course we should not use binomial coefficient notation, and should instead manipulate factorials. So the Pascal identity should be proved the clumsy way, not by using its definiton in terms of "choosing."