$\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.
 A: 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.  
A: 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.
A: 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$.
A: 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.
