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?


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.