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

Question

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 dierence 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?

Answer 1

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)$.