Give a recurrence relations & base cases for the number of n digits decimal strings containing no two consecutive zeros. How can i find a solution?

Question

So, in this part I learn that if the question “Find a recurrence relation for a number of bit strings of length $n$ without two consecutive zero” I got this solution is $$a_n=a_{n-1} + a_{n-2}$$ by the way. The problem turns to $n$ digit decimal strings , so this makes me confuse so much.

Answer 1

For the binary case, there are two possibilities: either the first bit is $1$, giving $a_{n-1}$ possibilities, or the first bit is $0$, giving $a_{n-2}$ possibilities.

For decimals, there are $10$ options for the first digit. $9$ of these (any first digit other than $0$) each give $a_{n-1}$ possibilities, and the final option gives $9a_{n-2}$ possibilities as there are $9$ possible second digits (thanks Si Warak for pointing out the earlier mistake here!). So this time the relation is $$a_n=9a_{n-1}+9a_{n-2}.$$