# Problem regarding recurrence relation with several criteria

Basically, i have a question as such where: I have completed (i) and (ii) but am having trouble solving part (iii). The answer is as such:

(i) $r_1 = 2$, $r_2 = 4$, $r_3 = 7$ and $r_4 = 13$
(ii) $r_n=2r_{n−1}−r_{n−4}$


I'm having trouble solving the third part of the question where there are few criteria. it contains the criteria of the first recurrence relation where "do not contain three consecutive 1s". i suppose that the earlier obtained relation in part (ii) must be used as well?

## 1 Answer

The number of strings of the second type is the number of strings of the first type minus the number of strings which don't have three consecutive $1$s but do have one of the other forbidden configurations. There are three types of such string:

• strings of the form $110x01$
• those of the form $10x011$
• those of the form $110y011$

where $x$ can be any string of length $n-5$ with no three consecutive $1$s, and $y$ any string of length $n-6$ with this property. So for $n\geq 6$ you get $s_n=r_n-2r_{n-5}-r_{n-6}$. (Here we define $r_0=1$ since there is one string of length $0$, which certainly doesn't have three consecutive $1$s.)

You can then use the recurrence relation for $r$ to get rid of the $r_{n-6}$ term - you'll need to check the answer still works for $n=5$, though!