For n ≥ 0 let a(n) be the number of quinary strings (only contain digits among 0 . . . 4) of length n and do not contain the string 00. Find a recurrence relation and give initial conditions for the sequence a0 , a1, ...
Completely confused with this question, how do I go about find a recurrence relation for a quinary string?
Let a string be called valid when it has your property. Let $a_n$ denote what you mentioned. Let $c_n$ denote the number of $n$ digit quinary strings without $00$ with the additional condition that the string does not have a $0$ at the end. Let $b_n$ denote the number of $n$ digit quinary strings without $00$ with the additional condition that the string has a $0$ at the end. It is easy to see that $a_n=b_n+c_n$. Also, one has these relations: $$b_{n+1}=c_n$$ $$c_{n+1}=4a_n=4(b_n+c_n)$$ The first one comes from the fact than any valid string with no $0$ at its end can be extended to a valid string with a $0$ at the end by appending a $0$. For the second one, if we have any valid string then we can append one of $1,2,3,4$ at its end to get a valid string without a $0$ at its end. Using this, we get $c_{n+1}=4(c_n+c_{n-1})$ and $b_{n+1}=4(b_n+b_{n-1})$ and on adding we get $a_{n+1}=4(a_n+a_{n-1})$.