Let be the number of strings of length n in which every is immediately followed by three consecutive . So for example, the string is allowed but is not.
Find a recurrence relation and initial conditions for .
I know the first initial condition has to have 4 places because the need three after it. From there I am lost.