Direct combinatorial proof that adding every other term in row of Pascal's triangle is $2^{n-1}$?

Question

By examination, it's evident that adding every other term in a row of Pascal's triangle gets you $2^{n-1}$. This either follows by induction, properties of Pascal's triangle, the binomial theorem, etc. However, I am wondering if there is a direct combinatorial way to see this.

Answer 1

When you add every other term of row $n$, you count all the subsets of an $n$-set with odd size, or all the subsets with even size. But there are as many odd-size subsets as there are even-size subsets: if $n$ is odd then the complement is a bijection, if $n$ is even the same result can be obtained by fixing a particular element (remove-the-special-element is a bijection between odd-size subsets with the special element and even size subsets without the special element; add-the-special-element is a bijection between odd-size subsets without the special element and even-size subsets with the special element). Thus the sum is half the total number of subsets of an $n$-set.

Answer 2

Using the binomial theorem, we have

$\displaystyle (1 + 1)^n = 2^n = \sum_{k=0}^{n} { n \choose k} $

and

$\displaystyle (1 - 1)^n = 0 = \sum_{k=0}^{n} {n \choose k } (-1)^k $

Adding the two equations and dividing by $2$ , we obtain

$ \displaystyle \sum_{k \text{ even} } {n \choose k} = 2^{n-1} $

From which, we also obtain,

$ \displaystyle \sum_{k \text{ odd} } {n \choose k } = 2^{n-1} $