How many words at the length of n above {0,1} alphabet the amount of zeros is even.
I understand the answer is $2^{n-1}$. I'm trying to come up with a reasonable explanation for why that is.
If I could prove that the amount of even and uneven numbers is always the same, I could arrive to the conclusion that even numbers are $2^{n-1}$. Help?
HINT: If you're given a word and you change the last letter, what happens to the number of zeros?
EDIT: This hint can give the answer without induction. Let $E_n$ be the number of words of length $n$ with an even number of $0$'s and $O_n$ the number of words of length $n$ with an odd number of $0$'s. Define $\phi:\{0,1\}^n \to \{0,1\}^n$ to flip the last letter of the word. Then $\phi^2 = \text{id}$ with $\phi(E_n) \subset O_n$ and $\phi(O_n) \subset E_n$. This immediately implies that $|E_n| = |O_n|$ Since there are $2^n$ total words, this implies $|E_n| = |O_n| = 2^{n-1}$.
A proof by induction could be done:
If $n=1, 2^n = 2^0 = 1$ and $1$ word of length $1$ has an even amount of $0$s, which is the word $1$.
Now imagine you have a sequence of length $k-1$. If it has an odd number of $0$s, then you can append a $0$ to the end of it. If it has an even number of $0$s, you can append a $1$ to it.
Assume then that it is true that, for words of length $k$, there are $2^{k-1}$ words with an even number of $0$s.
To those $2^{k-1}$ which have an even number of $0$s you add a $1$, making $2^{k-1}$ words of length $k+1$ that have an even amount of $0$s. To the other $2^{k-1}$ that have an odd number of $0$s, you add a $0$, making another $2^{k-1}$ words that have an even number of $0$s and length $k+1$. Therefore, you have a total of $2^{k-1} + 2^{k-1} = 2\cdot2^{k-1} = 2^k$ words, of length $k+1$, with an even number of $0$s, concluding your proof.
What you are considering are numbers $0000\dots0$ to $1111\dots1$ in binary. Indeed in total there are $2^n$ numbers.
Now, notice it is true for $n=1$. Assume it might be true for the number before your favourite natural number $k-1$.
Now, consider the possibilities for $k$. The last digit is either $0$ or $1$. So the total amount with even number when last is $0$, is all the $k-1$ length strings with odd amount, i.e. $2^{k-1}$. When last is $1$, we seek all the $k-1$ length strings with even amount, i.e. $2^{k-1}$.
Now, the total number would be $2^{k-1} + 2^{k-1} = 2^k$. So it's true for all the numbers you care about.
Two cases: If $n$ is odd, then any word of length $n$ containing an odd number of zeros is a word containing an even number of ones. So under the mapping that turns every one into a zero and every zero into a one, every word that contains an odd number of zeros corresponds to a word with an even number of zeros. That implies that half the words have an even number of zeros.
If $n$ is odd, then omit the last digit of the word. Note that half the words in that $n-1$ universe have an even number of zeros, and will pair with an last digit of zero to give an even number. And half the words in that $n-1$ universe have an odd number of zeros, and will pair with an last digit of oneto give an even number. So the fraction of words of length $n$ with an even number of zeros is $\frac12\cdot \frac12 + \frac12\cdot \frac12 = \frac12$.
