# 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

## 4 Answers

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