# Find a recurrence relation for a quinary string with NO consecutive zeros

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})$.
• We need to find $a_n$. First, we break $a_n$ into two parts $b_n$ and $c_n$. $b_n$ counts the number of $n$ digit valid strings with a $0$ at the end, and similarly no zero at the end for $c_n$. We are not breaking up the string itself. We are just counting valid strings with complementary properties and then adding up to get the total number of valid strings. May 11, 2018 at 5:46
• A string contributes to $c_{n+1}$, that is, is of $n+1$ length and is valid without a $0$ at the end if and only if its last digit is not $0$ and the string formed by its first $n$ digits is valid. Now, the last digit has $4$ non zero choices, namely $1,2,3,4$ and the number of valid strings with $n$ digits is just $a_n$. May 11, 2018 at 5:49