# Words of length $n$ containing an odd number of zeros

Let $$a_n$$ be the number of words of length $$n$$ with letters from the alphabet $$\{0, 1, 2, 3\}$$ containing an odd number of zeros.

I have already verified that this is given by the recurrence relation: $$a_{n+1} = 2 a_n + 4^n.$$ where $$a_0=0$$.

I then used the method of a generating function to solve this and arrive at: $$a_n= 2^{2n-1} - 2^{n-1}.$$ Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.

This problem can also be solved alternatively, using a new sequence $$B_n$$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.

Another way to fi nd the same result is as follows:

1) Consider the set $$B_n$$ of words of length $$n$$ with at least one $$0$$ or $$1$$.

How many of those are there? I am not sure how to express this in terms of $$a_n$$

2) In this set there are exactly as many words with an even number of zeros as there are with an odd number of zeros. Just change the first occuring $$0$$ or $$1$$ with its di erence with $$1$$ $$\dots$$ (not sure what is meant here, the wording is a bit vague)

I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?

For (1), we have $$|B_n| = 4^n - 2^n$$ since there are $$4^n$$ total strings over the alphabet, and $$2^n$$ of them have no zeros and no ones.
To expand on (2), let $$O_n \subset B_n$$ be the subset of strings with an odd number of zeros and $$E_n \subset B_n$$ be the subset with an even number of zeros. Note that the function $$f : O_n \to E_n$$ which on input $$x$$ replaces the first $$0$$ or $$1$$ in $$x$$ with $$1$$ or $$0$$, respectively, is a bijection. Thus $$a_n = |O_n| = |E_n|$$, and further, $$O_n$$ and $$E_n$$ partition $$B_n$$, so each has size $$\frac{1}{2}(4^n - 2^n)$$.