Consider bitstrings that contain at least one occurrence of $000$. Let $S_n$ be the number of such strings having length $n$. Which of the following is true for $n ≥ 4$?
Answer: $S_n = S_{n−1} + S_{n−2} + S_{n−3} + 2^{n−3}$
I cannot understand this answer. If a bitstring must have a $000$, then the possible ways to build this bistrings would be:
- Starts with: $0 \implies S_{n-1}$
- Starts with: $1000 \implies S_{n-4}$
- The rest: Any combination of 1's or 0's $\implies 2^{n-4}$
It can't start with $10$ for example, because then there is a posibility of the whole string being a repetition of $10$ which wouldn't satsify the problem.
So, $S_n = S_{n-1} + S_{n-4} + 2^{n-4}$
According to myself, putting these in any order will ensure a $000$ if $n ≥ 4$ but it is clearly the wrong answer.
I used to be great at these but I am rusty now!
You are starting off backwards. The $S_{n-1}$ term comes from strings that start with $1$. That doesn't help you with $000$ so all these strings that you want to count have to have $000$ in the last $n-1$ places. The $S_{n-2}$ term comes from the strings that start $01$. Again the $01$ doesn't help, so the $000$ has to be in the last $n-2$ places. The $S_{n-3}$ is the same with $001$. Finally we have the strings that start with $000$, after which we can do anything.