Sum over odd $k$

#odd k#sum#alternation

Statement

Show that $\sum_{k\text{ odd}}\binom{n}{k}=2^{n-1}$ for $n\ge1$ .

Hint

Same as even case; subtract.

Show solutionHide solution

Compute. $\sum_{k\text{ odd}}\binom{n}{k}=2^n-2^{n-1}=2^{n-1}$ .

Conclusion. Half the subsets have odd size.