# Simple combinatorics question - caught off guard!

Prove that ${{2n}\choose{n}}$ is even for $n \in \mathbb{N}$.

This one caught me off-guard when answering (or attempting to answer!) this for a student today. I tried this approach:

$${{2n}\choose{n}}=\frac{(2n)!}{n!n!}=\frac{(2n)(2n-1)(2n-2)\dots (n+1)}{n!}$$

and recognized that rearranging the numerator as $$(2n)(2(n-1))(2(n-2)) \ldots (2n-1)(2n-3) \ldots(n+1)$$

can help, but I don't know, roughly speaking, how far the chain on the left of the dots above goes.

-
This is wrong for n=0. –  Wok Mar 12 '14 at 14:10
$\binom{2n}{n}=\frac{(2n)\dotsm (n+1)}{n\dotsm 1}=\frac{2n}{n}\frac{(2n-1)\dotsm (n+1)}{(n-1)\dotsm 1} = 2 \binom{2n-1}{n-1}$ –  Kundor Mar 12 '14 at 14:45
Wok, true, but $n \in \mathbb{N}$ which excludes $n=0$ in our textbook (I apologize if this was not originally clear). –  Darrin Mar 13 '14 at 4:30
@Kundor isn't that RHS equal to 2*( (2n-1)... n / (n-1)...1 ) ? (no idea how to get math formatting, but n instead of (n+1)) –  immibis Mar 13 '14 at 10:36
@immibis No. Counting down $(n-1)$ terms from $(2n-1)$ ends at the same place as counting down $n$ terms from $2n$. In general, if you go down $b$ terms starting from $a$, you end at $a - b + 1$. –  Kundor Mar 13 '14 at 15:08

$$\binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n}$$ while $$\binom{2n-1}{n-1} = \binom{2n-1}{(2n-1)-(n-1)} = \binom{2n-1}{n}$$ so $$\binom{2n}{n} = 2 \times \binom{2n-1}{n}$$

-

Combinatorial proof: From a set of $2n$ chocolates, choose $n$ to eat. However, these choices come in pairs -- the $n$ I didn't choose I could have equally well chosen. Hence, all ${2n\choose n}$ "menus" can be paired off, so there must be an even number of them.

-
@Darrin I haven't read the book, but this is a direct proof as opposed to a proof by contradiction (or even a proof by induction). –  Mark S. Mar 12 '14 at 3:16
@Wok, $\mathbb{N}$ is commonly understood to exclude $0$. –  vadim123 Mar 12 '14 at 14:11
Not in my country. In France, we call ℕ* the set excluding 0. –  Wok Mar 12 '14 at 14:13
While it's not standard, it is common to have $\mathbb{N}$ not include zero. See this earlier discussion. –  vadim123 Mar 12 '14 at 14:19
It is good policy, when a question is ambiguously stated, to choose the interpretation under which it is correct. –  vadim123 Mar 12 '14 at 14:24

I think @vadim123 has given an excellent proof, but if the OP wants to use only algebraic methods, here goes.

Lemma. If $n$ is a positive integer and $n\le 2^k$ and $$s=\Bigl\lfloor\frac{n}{2}\Bigr\rfloor+\Bigl\lfloor\frac{n}{4}\Bigr\rfloor+\Bigl\lfloor\frac{n}{8}\Bigr\rfloor+\cdots+\Bigl\lfloor\frac{n}{2^k}\Bigr\rfloor\ ,$$ then $2^s$ is a factor of $n!$ and $2^{s+1}$ is not.

Furthermore, \eqalign{s &\le\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots+\frac{n}{2^k}\cr &<\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots+\frac{n}{2^k}+\cdots\cr &=n\ ,\cr} so $n!$ is not a multiple of $2^n$.

Now write \eqalign{\binom{2n}{n} &=\frac{(2n)(2n-2)\cdots(2)}{n!}\frac{(2n-1)(2n-3)\cdots(1)}{n!}\cr &=2^n\,\frac{(2n-1)(2n-3)\cdots(1)}{n!}\ .\cr} The expression has $n$ factors of $2$ in the numerator, and from the above results, not all of them will be cancelled out by the $n!$ in the denominator. So the expression is even.

-

The above answers are already proofs, however I think mine is a simpler one.

Just using the definition of the binomial form:

$$\binom{2n}{n} = \frac{2n*(2n-1)\ *\cdots*(2n-(n-1))}{n!}=$$ $$=\frac{2n*(2n-1)*\cdots*(2n-(n-1))}{n*(n-1)!}=$$ $$=\frac{2n}{n}*\frac{(2n-1)*\cdots*(2n-(n-1))}{(n-1)!}=$$ $$=2*\frac{(2n-1)*\cdots*(2n-(n-1))}{(n-1)!}=$$ $$=2*\binom{2n-1}{n-1}$$ Two times a whole number will be even.

-