# $\sum_{k=0}^{n/2} {n\choose{2k}}=\sum_{k=1}^{n/2} {n\choose{2k-1}}$, Combinatorial Proof:

How am I supposed to prove combinatorially:

$$\sum_{k=0}^{n/2} {n\choose{2k}}=\sum_{k=1}^{n/2} {n\choose{2k-1}}$$

$${n\choose{0}}+{n\choose{2}}+{n\choose{4}}+\dots={n\choose{1}}+{n\choose{3}}+{n\choose{5}}+\cdots$$

Absolutely clueless.

• @user84413: That should be an answer. – Henning Makholm Aug 3 '13 at 21:52
• @user84413 : Definitely post that as an answer. It's better than the posted answer that already has five up-votes. – Michael Hardy Aug 3 '13 at 21:55
• @user84413, just noticed you have already mentioned that after I edited my answer oh derp ... ya that's definitely a better answer! – user67258 Aug 3 '13 at 22:05

Just let $x=-1$ in the binomial theorem:

$$(1+x)^n=\sum^n_{k=0}{n\choose k}x^k$$

Edited: Think about the number of even subsets and the number of odd subsets.

• But is that done "combinatorially"? I think often that term means a bijective argument is used. – Michael Hardy Aug 3 '13 at 21:52
• Can i know what does the instructor really mean by "prove combinatorially" on my problem set? – user88880 Aug 3 '13 at 22:03
• Wikipedia page ... en.wikipedia.org/wiki/Combinatorial_proof – user67258 Aug 3 '13 at 22:14
• Although this Wikipedia page states: "The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics.". I disagree that this is the common sense and if the instructor specifically asks for a combinatorial proof, then I don't think that this suffices. – Tomas Aug 3 '13 at 22:19

If you want to do this without the Binomial Theorem, you can define a bijection between the even-numbered subsets of $\{1,\cdots , n\}$ and the odd-numbered subsets of $\{1,\cdots , n\}$ by $A\mapsto A\oplus 1$, where $A\oplus 1=A-\{1\}$ if $1\in A$, and $A\oplus 1=A\cup \{1\}$ if $1\notin A$.

• To rephrase what is above, think about this also in binary. There are $2^n$ bit strings of length $n$. Either they have an even number of ones or an odd number of ones. Consider the invertible map $f(x) = x \oplus 1$. This will always change the number of ones up one or down one. But the map is invertible, so it divides evenly between the strings with an even number of 1s and the ones with an odd number. – abnry Aug 5 '13 at 3:57

Let $n$ be odd. Throw $n$ distinct coins on the table. There are $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots +\binom{n}{n-1}$ ways that there can be an even number of heads showing.

I forgot to mention that the table is a glass coffee table, and there is a small person under the table. (Don't ask.) Whenever the person looking down sees an even number of heads, the person below sees an odd number of heads, and vice-versa. But the number of ways to get an odd number of heads is $\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots +\binom{n}{n}$.

Unfortunately, the coffee table argument does not work for odd $n$.

However, we can use the coffee table idea in a more complicated way. Let $n$ be even, and suppose we throw $n$ distinct coins on the table, $n-1$ of them pennies and one of them a dime.

We have an even number of heads if the dime shows a tail and there is an even number of heads among the pennies, or if the dime shows a head and there is an odd number of heads among the pennies.

We have an odd number of heads if the dime shows a head and there is an even number of heads among the pennies, or if the dime shows a tail and there is an odd number of heads among the pennies.

By the coffee table argument, there are just as many ways to have an even number of heads among the pennies as there are of having an odd number of heads. It follows that there are the same number of ways to have an even number of heads among our $n$ coins as there are of having an odd number.

The question as currently posed can be answered by looking at the symmetry of the rows of Pascal's triangle corresponding to odd $n$ (which have an even number of elements). By definition

$\large{n\choose{k}\large}=\frac{n!}{k!(n-k)!}$.

Therefore ${n\choose{0}}={n\choose{n}}$, ${n\choose{1}}={n\choose{n-1}}$, and in general ${n\choose{k}}={n\choose{n-k}}$. Thus, the set of odd indexed elements and the set of even indexed elements in each row are identical.