# Math Help - Counting Strings

1. ## Counting Strings

Let $a_n$ be the number of strings of length n in which every $0$ is immediately followed by three consecutive $1's$. So for example, the string $101111$ is allowed but $01110$ is not.

Find a recurrence relation and initial conditions for $a_n$.

I know the first initial condition has to have 4 places because the $0$ need three $1's$ after it. From there I am lost.

2. Originally Posted by minkyboodle
Let $a_n$ be the number of strings of length n in which every $0$ is immediately followed by three consecutive $1's$. So for example, the string $101111$ is allowed but $01110$ is not.

Find a recurrence relation and initial conditions for $a_n$.

I know the first initial condition has to have 4 places because the $0$ need three $1's$ after it. From there I am lost.