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 :)
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.