Binomial Identity and Counting A string in $\{0, 1\}*$ has even parity if the symbol $1$ occurs in the word an even number of times; otherwise, it has odd parity.
(a) How many words of length $n$ have even parity?
(b) How many words of length $n$ have odd parity?
It seems to me that correct approach will be to use summations of combinations, and correct answer will yield $2^{n-1}$ in both cases. Is there any way to prove separately that each of them is equal to $2^{n-1}$? Would be happy to know your ideas!
 A: The number of words of length $n$ with exactly $k$ ones is
$$\binom{n}{k}$$
There are $2^n$ binary strings of length $n$ since there are two possible choices for each of the $n$ entries.  Moreover, by the Binomial Theorem,
$$2^n = (1 + 1)^n = \sum_{k = 0}^{n} \binom{n}{k}1^{n - k}1^{k} = \sum_{k = 0}^{n} \binom{n}{k}$$
and
$$0 = 0^n = (1 - 1)^n = \sum_{k = 0}^{n} \binom{n}{k}1^{n - k}(-1)^k = \sum_{k = 0}^{n} (-1)^k\binom{n}{k}$$
Notice that adding the positive terms in the second summation counts all the binary strings of length $n$ with an even number of ones, while adding the negative terms gives the additive inverse of the number of strings of length $n$ with an odd number of ones.  Since this sum is equal to zero, the number of binary strings of length $n$ with an even number of ones is equal to the number of binary strings of length $n$ with an odd number of ones.  Since every binary string of length $n$ must have an even number of ones or an odd number of ones, exactly half the strings of length $n$ have an even number of ones.  Since there are $2^n$ such strings, the number of binary strings of length $n$ with an even number of ones is
$$\frac{1}{2} \cdot 2^n = 2^{n - 1}$$
as is the number of binary strings of length $n$ with an odd number of ones.
This can also be seen algebraically.  If we add the two equations above, we find that
$$2^n = 2\sum_{k = 0}^{n} \binom{n}{2k}$$
since the terms with an odd number of ones cancel.  Hence, the number of binary strings of length $n$ with an even number of ones is
$$2^{n - 1} = \sum_{k = 0}^{n} \binom{n}{2k}$$
where
$$\binom{n}{2k} = 0$$
if $2k > n$.  The number of binary strings of length $n$ with an odd number of ones is found by subtracting $2^{n - 1}$ from $2^n$, which yields
$$2^n - 2^{n - 1} = 2^{n - 1}(2 - 1) = 2^{n - 1}$$
A: Say you want an odd parity. For the first $n-1$ digits, you can choose however you like, but for the last digit, you cannot choose because you need to make the number of $1$s odd. Hence $2^{n-1}$.
The same for even parity.
