13
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ This is wrong for n=0. $\endgroup$
    – Wok
    Mar 12, 2014 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$ Mar 12, 2014 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, 2014 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$ Mar 13, 2014 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$ Mar 13, 2014 at 15:08

4 Answers 4

31
$\begingroup$

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.

$\endgroup$
14
  • 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, 2014 at 3:16
  • 1
    $\begingroup$ @Wok, $\mathbb{N}$ is commonly understood to exclude $0$. $\endgroup$
    – vadim123
    Mar 12, 2014 at 14:11
  • 2
    $\begingroup$ Not in my country. In France, we call ℕ* the set excluding 0. $\endgroup$
    – Wok
    Mar 12, 2014 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, 2014 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, 2014 at 14:24
27
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .