Combinatorial Proof For Counting All Binary Strings

Question

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.

Answer 1

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$.

Answer 2

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$.