Question: Consider bitstrings that do not contain $110$. Let $S_n$ be the number of such strings having length $n$. What is $S_n$ for $n \ge 4$?
Answer: $S_n = S_{n-1} + S_{n-2} + 1$
Attempt: I tried writing out all the bitstrings for $n=2$, and $n=3$.
$n=3$ I got: $000, 001, 011, 111, 100, 010, 101$
$n=2$ I got: $00, 01, 10, 11$
$n=4$ seems to large to do this by hand. According to the answer, it should be
$S_4 = S_3 + S_2 + 1$.
$S_4 = 7 + 0 + 1 = 8$? Assuming $S_n$ is the number of strings without $110$, so since $n=3$ has one $110$ I just exclude that and get $7$. $n=2$ has no $110$.
I'm not sure how the formula was derived. The bitstring counting logic I struggle with, any guidance on how to appriach these would help a lot.
Best Answer
This is not going to be an answer, but I don't have enough reputation to comment, so I apologize in advance.
My thought is to try thinking about your placement of the $110$. For the case of $n=3$, you saw that there was only one place to put it - as the whole thing.
Now consider the case of $n=4$. The approach will be to consider the possibilities which contain the string you are looking to avoid, find out how many such unique strings there are and subtract it from the total.
There are two places to put the string $110$, namely the beginning $110\bullet$ or the end $\bullet110$. There are $2^4$ total four-digit bitstrings, and there are four which match these placement patterns $1100, 1101$ and $0110, 1110$. Just to check, we should make sure all four of these are different, which is clear for this many (just look at the third digit) but might not be so clear on a larger scale. So as I see it there are $2^4 - 4 = 12$ ways to do this. This is $16-4=12 \neq 8$.
I agree with your logic for finding $S_3, S_2$, and hence $S_4 = 8$. Do you see any errors in my logic?
If you agree with my logic, is it possible that the question is not being asked the way you have asked it here? Alternatively are you sure the solution you have is correct?