# 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. – Manan May 11 '18 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$. – Manan May 11 '18 at 5:49