Problem
COM-B2-M09-P007 Strings with an Even Number of Ones
#7
★★★☆☆ Level 3 of 5
Prove that for \(n\ge 1\), the number of binary strings of length \(n\) with an even number of ones is \(2^{n-1}\).
The sum of even binomial coefficients is obtained from \((1+1)^n\) and \((1-1)^n\).
The number of strings with \(k\) ones is \(\binom{n}{k}\). Thus we need the sum of coefficients of even powers in \((1+x)^n\). It equals \(\frac{(1+1)^n+(1-1)^n}{2}\). For \(n\ge 1\), this is \(\frac{2^n+0}{2}=2^{n-1}\).
A first clean parity filter.