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})$.