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.

  • 2
    $\begingroup$ This is wrong for n=0. $\endgroup$ – Wok Mar 12 '14 at 14:10
  • 5
    $\begingroup$ $\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}$ $\endgroup$ – Kundor Mar 12 '14 at 14:45
  • 1
    $\begingroup$ Wok, true, but $n \in \mathbb{N}$ which excludes $n=0$ in our textbook (I apologize if this was not originally clear). $\endgroup$ – Darrin Mar 13 '14 at 4:30
  • $\begingroup$ @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)) $\endgroup$ – immibis Mar 13 '14 at 10:36
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • 6
    $\begingroup$ @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). $\endgroup$ – Mark S. Mar 12 '14 at 3:16
  • 1
    $\begingroup$ @Wok, $\mathbb{N}$ is commonly understood to exclude $0$. $\endgroup$ – vadim123 Mar 12 '14 at 14:11
  • 2
    $\begingroup$ Not in my country. In France, we call ℕ* the set excluding 0. $\endgroup$ – Wok Mar 12 '14 at 14:13
  • 2
    $\begingroup$ While it's not standard, it is common to have $\mathbb{N}$ not include zero. See this earlier discussion. $\endgroup$ – vadim123 Mar 12 '14 at 14:19
  • 10
    $\begingroup$ It is good policy, when a question is ambiguously stated, to choose the interpretation under which it is correct. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.