1. ## Counting Strings

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

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

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

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

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

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