Give a recurrence relations & base cases for the number of $n$ digit decimal strings containing an even number of $0$ digits.
My solution is:
Let $a_n$ denote the the number of $n$ digit numbers containing an even number of $0$ digits. $a_n = (9a_{n-1}) + (10^{n-1}-a_{n-1}) = 8a_{n-1}+10^{n-1}$.
Is the solution correct? What is the initial condition?
If you mean decimal strings, where leading zeros are permitted, your recurrence is good. It would be good to explain the logic behind it. The $9a_{n-1}$ term takes a string of length $n-1$ and appends a non-zero digit to it. The $10^{n-1}-a_{n-1}$ term takes an unacceptable string of length $n-1$ (which must have an odd number of zeros) and appends a zero to get an acceptable string of length $n$.
The bases case is just a place to start that you compute some other way. If you imagine computing $a_3$, you need $a_2$ to do that. To compute $a_2,$ you need $a_1$. It is easy to count $a_1$ by hand-there are $9$ strings of length $1$ that have an even number of zeros. That can be your base case. It also works to take $a_0$ as your base case. There is one string of length $0$ that has an even number of zeros-the empty string. It works fine, as it gives $a_1=8(1)+10^0=9$
