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.

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.

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

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.