Provide a combinatorial argument for the following: $2^n = \sum_{k\text{ odd}} \binom{n+1}{k}$ I'm trying to find a combinatorial proof (and algebraic too but that's optional) of the following result:
Let $S = \{2k+1 | 0 < 2k+1 ≤ n+1\}$
$$2^n = \sum_{k\in S} \binom{n+1}{k}$$
I was thinking for the algebraic proof of using the identity:
$$2^{n+1} = \sum_{k=0}^n \binom{n+1}{k}$$
In the following way:
$$2^{n+1}+(1-1)^{n+1} = \sum_{k=0}^n \binom{n+1}{k} + \sum_{k=0}^n (-1)^{k}\binom{n+1}{k} = 2\sum_{k\in S}^n \binom{n+1}{k} $$
And dividing both sides by 2 gives us:
$$2^n =\sum_{k\in S}^n \binom{n+1}{k} $$
Is my algebraic proof correct? Is there any other one you can provide? Also I've made no progress towards a combinatorial argument pls help :)
 A: That's a pretty cool proof. I think that I do have a slightly simpler one
\begin{align*}
&\sum_{k\in S} \binom{n+1}{k} \\
&=\sum_{l=0}^{n/2} \binom{n+1}{2l+1} \\
&=\sum_{l=0}^{n/2} \binom{n}{2l} + \binom{n}{2l+1} \\
&=\sum_{k=0}^{n} \binom{n}{k} \\
&= 2^n
\end{align*}
A: 
If $S$ is a finite non-empty set then the number of subsets of $S$ that have even cardinality equals the number of subsets of $S$ that have odd cardinality.

Proof:
If the number of elements of $S$ is odd then subsets $A$ having even cardinality correspond one to one with subsets $A^c$ having odd cardinality.
If the number of elements of $S$ is even then place an arbitrary element $s\in S$ apart and split up in subsets of $S-\{s\}$ (this set has odd cardinality so we can apply what is written above) and subsets of $S$ that contain $s$.

So if $|S|=n+1$ then there are $\frac12\times2^{n+1}=2^n$ subsets that have odd cardinality.

(In fact it can be proved that the principle of inclusion/exclusion is completely based on this statement)

Addendum (in request of OP):
Let $I$ be a non-empty finite set and let $K\subseteq I$. If $C$
is some conditional statement then let $\left[C\right]$ denote the
function that takes value $1$ if this condition is satisfied and
takes value $0$ otherwise.
Then by equality $$\sum_{J\subseteq I\wedge\left|J\right|\text{ even}}\left[J\subseteq K\right]=\sum_{J\subseteq I\wedge\left|J\right|\text{ odd}}\left[J\subseteq K\right]\tag1$$
it is stated that the number of subsets of $K$ that have even cardinality
equals the number of subsets of $K$ that have odd cardinality. As
shown above this is a true statement if $K$ is not empty. The following
modification of $(1)$ however is true for every $K\subseteq J$:$$\left[K\neq\varnothing\right]+\sum_{\varnothing\neq J\subseteq I\wedge\left|J\right|\text{even}}\left[J\subseteq K\right]=\sum_{J\subseteq I\wedge\left|J\right|\text{odd}}\left[J\subseteq K\right]\tag2$$
With this in mind let $\Omega$ be a set and let set $I$ serve as
index set for some subsets $B_{i}\subseteq\Omega$.
Now fix some $\omega\in\Omega$
and let: $$K_{\omega}=\left\{ i\in I\mid\omega\in B_{i}\right\} $$ Then $J\subseteq K_{\omega}\iff\omega\in\bigcap_{i\in J}B_{i}$
so that: $$\left[J\subseteq K_{\omega}\right]=1_{\bigcap_{i\in J}B_{i}}(\omega)$$ for
every $J\subseteq I$.
Also $K_{\omega}\neq\varnothing\iff\omega\in\bigcup_{i\in I}B_{i}$
so that: $$\left[K_{\omega}\neq\varnothing\right]=1_{\bigcup_{i\in I}B_{i}}(\omega)$$
This works for every fixed $\omega\in\Omega$ so we can rewrite true statement $(2)$ as: $$1_{\bigcup_{i\in I}B_{i}}+\sum_{\varnothing\neq J\subseteq I\wedge\left|J\right|\text{even}}1_{\bigcap_{i\in J}B_{i}}=\sum_{J\subseteq I\wedge\left|J\right|\text{odd}}1_{\bigcap_{i\in J}B_{i}}\tag3$$
Now if $\mu$ denotes a measure then integration wrt $\mu$ on both
sides yields: $$\mu\left(\bigcup_{i\in I}B_{i}\right)+\sum_{\varnothing\neq J\subseteq I\wedge\left|J\right|\text{even}}\mu\left(\bigcap_{i\in J}B_{i}\right)=\sum_{J\subseteq I\wedge\left|J\right|\text{odd}}\mu\left(\bigcap_{i\in J}B_{i}\right)\tag4$$If
the measures $\mu\left(\bigcap_{i\in J}B_{i}\right)$ on LHS are finite then we can transpose them to RHS: $$\mu\left(\bigcup_{i\in I}B_{i}\right)=\sum_{\varnothing\neq J\subseteq I}\left(-1\right)^{\left|J\right|-1}\mu\left(\bigcap_{i\in J}B_{i}\right)\tag5$$and in $(5)$ we recognize the principle of inclusion/exclusion.
