Basically, i have a question as such where:

enter image description here

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 1


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!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .