You are given all n-digit strings in which each digit is 0, 1, or 2. Using the product rule and/or the sum rule, count the number of these strings that have an odd number of 0’s when n (the number of digits in the string) is equal to
(a) 1
I got $1$ string, which is $0$
(b) 2
$2\times1 = 2$ and $1 \times 2 = 2.$
Then $2+2=4$ strings.
(c) 3
We can have 1 or 3 $0$'s.
For 1: $1\times2\times2=4$ and $2\times1\times2=4$ and $2\times2\times1=4$
For 3: $1\times1\times1=1$
Then, $4+4+4+1=13$ strings.
(d) 4.
We can have 1 or 3 $0$'s.
For 1: $1\times2\times2\times2=8$ and $2\times1\times2\times2=8$ and$2\times2\times1\times2=8$ and $2\times2\times2\times1=8$
For 3: $1\times1\times1\times2=2$ and $1\times1\times2\times1=2$ and $1\times2\times1\times1=2$ and $2\times1\times1\times1=2$
Then, $8+8+8+8+2+2+2+2=40$ strings.
Using recurrence relations, count the number of these strings that have an odd number of 0’s in all n-digit strings. Once you get the (closed-form) formula, verify that your answers to (a) through (d) are correct.
Hint: Let $E(n)$ be the number of strings with an even number of zeros and $O(n)$ be the number with an odd number of zeros. Can you write an equation for $E(n)$ in terms of $E(n-1), O(n-1)$ and similarly for $O(n)?$ If you have string of length $n-1$ with an even number of zeros and extend it by one digit...
Added: a string of $n$ digits with an odd number of $0$'s can come from a string of length $n-1$ with an odd number of $0$'s that we add a $1$ or a $2$ to, or from a string of length $n-1$ with an even number of $0$'s that we add a $0$ to. The recurrence is then $O(n)=2O(n-1)+E(n-1)$. Similarly we have $E(n)=2E(n-1)+O(n-1)$. The base condition is $O(0)=0,E(0)=1$ because the empty string has an even number of $0$'s.
We know $E(n)+O(n)=3^n$ because every string of length $n$ has either an even or odd number of $0$'s. We then have $$O(n)=2O(n-1)+3^{n-1}-O(n-1)\\O(n)=3^{n-1}+O(n-1)$$ and we can sum the geometric series to get $$O(n)=\frac 12(3^n-1)\\E(n)=\frac 12(3^n+1)$$