# Recurrence relation of binary strings

I have a question:

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)

• $(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). – JMoravitz Jun 5 '17 at 3:41
• @JMoravitz ahh thanks for that! – Maxxx Jun 5 '17 at 3:45

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$.
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?