Recurrence Relation with Strings

Question

Q. How many strings in {0,1,2,3} have an even number of 1's.

The answer provided uses the recurrence relation $a_{n+1} = 3a_n + (4^n - a_n)$.

The hint given was that consider the last string of length $n+1$ is :
$0$ - Number of strings that can proceed is $a_n$.

I'm assuming that $a_n$ is the number of legal strings that can follow $0$.
So if there was a string $02123210$, since this string has an even number of ones ($a_n$), then $a_n$ strings can proceed the previous string.

Then it would be the same for $2,3$ resulting in the $3a_n$. I don't know however how the $(4^n-a_n)$ came about.

I've tried looking at What is the recurrence relation in this problem?. Since it looks similar to this problem.

Answer 1

Suppose $a_n$ is the number of GOOD strings of length $n$. By GOOD we mean the strings that satisfies the given criterion (i.e it has even number of $1's$). Then consider a GOOD string of length $n+1$. It can be made in two ways:

1. Case 1: we start with a GOOD string of length $n$ and then add $0$ or $2$ or $3$ at the $n+1^{\text{st}}$ place. This way we have not changed the number of $1's$ that were already there in the string of length $n$.
2. Case 2: we start with a BAD string of length $n$ (so it will have odd number of $1's$). Then we add a $1$ for the $n+1^{\text{st}}$ place. Thus converting it into a GOOD string of length $n+1$.

The number of strings from case 1 will be $3a_n$ (because of $3$ choices of ending a GOOD string of length $n$).

The number of strings from case 2 will be = the number of BAD strings of length $n$. This is same as total strings of length $n$ - the number of GOOD strings of length $n$.

The total number of strings of length $n$ made up of four symbols is $4^n$ and the number of GOOD strings of length $n$ is $a_n$. Therefore the total number of BAD strings of length $n$ is $4^n-a_n$.

I hope this helps.