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

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

I tried but I can't do it.

• What methods did you try? – joejacobz May 6 '13 at 1:43
• @joejacobz I tried the conventional method, asumming for $k$ then trying to prove for $k+1$ but not works, then I tried using a stronger hypotesis "is an integer satisfying some property $P$" to get a stronger hypotesis but not works. Maybe I didn't use an adequate $P$. – Gaston Burrull May 6 '13 at 1:45

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.

• Perfect! Thanks. – Gaston Burrull May 6 '13 at 2:38

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

• Thanks, so clever! Answered at the same time as Andre Nicolas. :) – Gaston Burrull May 6 '13 at 1:59

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."

• Yes, the choice notation probably confuse someone that there is nothing to prove. – Gaston Burrull May 6 '13 at 2:03

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.

• this is a little unsatisfying because of that assumption, though – cats May 6 '13 at 1:52
• When I tried to proof, I tried to induct in these two things here $n+1|\dbinom{2n}{n}$ was my adittional $P$. If you can prove the assumption with induction, we are done but I think that is the same difficulty. – Gaston Burrull May 6 '13 at 1:54