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. 
 A: 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.
A: $$\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} $$
A: 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.
A: 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.
