0
$\begingroup$

I have a question:

enter image description here

and I'm really confused on how recurrence relation works mathematically so i gave it a shot.

(i) r1 = 2
    r2 = 4
    r3 = 7
    r4 = 12

(ii) #I'm not sure if (i) is correct hence, i couldn't do this part.

Since the question says the number of binary strings of length n that DO NOT contain three consecutive 1s, does it mean i have to list out all the possibilities? I'm terribly bad at recurrence and having trouble understanding part (i)

$\endgroup$
  • 1
    $\begingroup$ $(i)$ is almost correct. The set of length $4$ strings not satisfying your conditions are 1111, 1110, 0111, so we have $r_4=16-3=13$ not $12$. (you might have doublecounted $1111$ in your calculation). $\endgroup$ – JMoravitz Jun 5 '17 at 3:41
  • $\begingroup$ @JMoravitz ahh thanks for that! $\endgroup$ – Maxxx Jun 5 '17 at 3:45
0
$\begingroup$

For $r_n$, we have $$r_n = 2r_{n-1}-r_{n-4}$$ which is because for any acceptable sequence of length $n-1$, we can put $0$ and $1$ at the end. However, in the case of putting $1$ at the end, it is possible that the final three digits are $1$. so we subtract $r_{n-4}$ to get our result. This final step is because all the sequences we have to subtract can be constructed by adding $0111$ to all the possible sequences of length $n-4$.

$\endgroup$
  • $\begingroup$ much thanks! just would like to seek a little assistance for (iii) where it mentions "do not contain three consecutive 1s" together with all the bunch of criteria. For that particular expression for Sn, do i use the Rn relation to be subtracted? since i suppose they correspond to each other. $\endgroup$ – Maxxx Jun 5 '17 at 4:17
0
$\begingroup$

The idea of finding the recurrence relation is to say that an acceptable string of length $n$ can start with any string of some shorter length and be built up to length $n$. For example, here you can take any string of length $n-1$ and append a $0$ because appending a $0$ can never create three $1$s in a row. You can't say it would also include strings of length $n-1$ to which you append a $1$ because the base string could be acceptable but end in $11$. The previous construction got all the strings that end in $0$. How about all the ones that end in exactly one $1$? Can you see a place to get them? You also need ones that end in exactly two $1$s. Where do they come from?

$\endgroup$

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.