Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
This is wrong for n=0. –  Wok Mar 12 at 14:10
5  
$\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 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 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 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 at 15:08

4 Answers 4

up vote 27 down vote accepted

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

share|improve this answer

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.

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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