A computer system considers a string of decimal digits a valid codeword if it contains an even number of $0$ digits. Let $a_n$ be the number of valid n-digit codewords. Find the recurrence relation for $a_n$.
The total possibilities for a binary string is $2^n$ for a binary string. What else do I need to consider to come up with a recurrence relation to relate the concepts?
Best Answer
If we know the first digit is $1$ then we need the rest of the $n-1$ digits to be valid on there own. There are $a_{n-1}$ of those.
If we know the first digit is $0$, then we need the rest not to be valid on their own (that way they contain an odd amount of zeros). Then the question becomes how many $n-1$ bit strings are not valid on there own. That is $2^{n-1}-a_{n-1}$.
$$a_{n}=a_{n-1}+2^{n-1}-a_{n-1}=2^{n-1}$$
This gives the recursion,
$$a_{n}=2a_{n-1}$$