Is there a closed-form formula for sum of "odd combinations"?

Question

So, I was trying to come with a formula for the sum of below series:

${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$

Thank you.

Answer 1

For any positive integer $k$, you can show that $$\binom{k}{0}+\binom{k}{2}+\binom{k}{4}+\cdots=\binom{k}{1}+\binom{k}{3}+\binom{k}{5}+\cdots$$

(Hint: Use the binomial theorem to expand $(x+y)^k$ with $x=1,y=-1$.)

You can also show that

$$\binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\cdots+\binom{k}{k}=2^k$$

(Hint: Use the binomial theorem to expand $(x+y)^k$ with $x=1,y=1$.)

Can you combine the two to solve your problem?

Answer 2

Another way to prove this is that if you have a set $X$ with $k$ elements, then you can create a $1-1$ correspondence between the subsets with even numbers of elements and the subsets of odd number of elements by picking a fixed element $x\in X$ and pairing $S$ with $S\cup \{x\}$ for each $S$ with $x\not\in S$.

Thus, the odd subsets are half of the subsets, and thus the number is $\frac{2^k}{2}=2^{k-1}$.

Answer 3

Another method which is slightly different from the proposed ones is using the identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ to break up every summand.