Combinatorial Proof For Counting All Binary Strings The Question
Provide a combinatorial proof for the following:
For $n \ge 1$,
$$2^n = \binom{n+1}1+\binom{n+1}3+\ldots+\begin{cases}
\binom{n+1}n,&\text{if }n\text{ is odd}\\\\
\binom{n+1}{n+1},&\text{if }n\text{ is even}
\end{cases}$$
My Work
Parts a,b of the question involved counting strings. This lead me to notice that $2^n$ is actually all $n$-bit binary strings. Which means the series on the right is somehow counting all total binary strings of length $n$. I'm kind of stumped as to how the series works though. I tried writing out some examples of it.
$2^1 = \binom{1+1}{1} = \binom{2}{1} = 2$
$2^2 = \binom{3}{1}+\binom{3}{3} = 4$
$2^3 = \binom{4}{1}+\binom{4}{3} = 8$
$2^4 = \binom{6}{1}+\binom{6}{3}$ This is where I realized I must be doing it wrong because $2^4 = 16$ and $\binom{6}{3} = 20$
My Question
I'm trying to understand the problem. How does the series work? How would I write out $2^5$ as the $RHS$ series for example? And then how does it count the total amount of $n$ length binary strings.
 A: Your $n=4$ line should read
$$2^4=\binom51+\binom53+\binom55=5+10+1=16\;.$$
The upper number in each of the binomial coefficients is $n+1$, which is $5$ in this case, and the lower number runs through all of the odd numbers less than or equal to $n+1$.
HINT: 
$$\binom{n+1}1+\binom{n+1}3+\ldots+\begin{cases}
\binom{n+1}n,&\text{if }n\text{ is odd}\\\\
\binom{n+1}{n+1},&\text{if }n\text{ is even}
\end{cases}\tag{1}$$
is the number of subsets of $\{1,2,\ldots,n+1\}$ that have an odd number of elements. Show that exactly half of the subsets of $\{1,2,\ldots,n+1\}$ have an odd number of elements. Then use your observation that a set of $m$ elements has $2^m$ subsets altogether to complete the proof that $(1)$ is equal to $2^n$.
A: Take a look at Pascal's triangle. The $k^{\mathrm{th}}$ entry in the $n^{\mathrm{th}}$ row is $n\choose k$, which is also the number of weight-$k$ binary strings of length $n$ ($k$ running from 0 to $n$). You're counting every other entry in the $(n+1)$th row. The sum of the elements in this row is $2^{n+1}$ because the number of all length-$(n+1)$ binary strings is $2^{n_+1}$, and because you're taking half of these elements, their sum is $2^n$. 
