A string that contains only $0's$, $1's$, and $2's$ is called a ternary string. (a) Find a recurrence relation for the number of ternary strings that do not contain two consecutive $0's$. (b) What are the initial conditions ? (c) How many ternary strings of length six do not contain two consecutive $0's$?
for answer a) Let $a_n$ be the number of ternary strings of length $n$ that do not contain two consecutive $0's$. In order to construct a bit string of length $n$ of this type, we could start with a $1$ or $2$ and follow with a string of length $n−1$ not containing two consecutive $0’s$, or we could start with $01$ or $02$ and follow with a string of length $n − 2$ not containing two consecutive $0's$. Consequently, we have the recurrence relation: $a_n = 2a_{n−1} + 2a_{n−2}$.
for answer b) $a_0 = 0$ (for the empty string), $ a_1 = 3$ (all three strings of length 1 fail to contain two consecutive $0's$).
and Do a and b have a correct answer?and could you help me with( c),I do not know how can I answer it
Thank you