Number of bitstrings with $000$ as substring

Solution 1:

Let $G_n$ be the number of bit stings of length $n$ that have no $000$. We will find a recurrence for $G_n$, and use it to get a recurrence for $F_n$. The last part will be relatively easy, since $F_k+G_k=2^k$.

It is useful to introduce an informal abbreviation. Call a bit string bad if it has no $000$.

Let $n\ge 4$. A bad string of length $n$ can begin with $1$. There are $G_{n-1}$ such bad strings, since appending any bad string of length $n-1$ to $1$ will do the job.

A bad string can begin with $01$. There are $G_{n-2}$ such bad strings.

A bad string can begin with $001$. There are $G_{n-3}$ such bad strings.

That's all! So $$G_n=G_{n-1}+G_{n-2}+G_{n-3}.$$ It follows that $$2^n-F_n=(2^{n-1}-F_{n-1})+(2^{n-2}-F_{n-2})+(2^{n-3}-F_{n-3}).$$ This can be rearranged to $$F_n=F_{n-1}+F_{n-2}+F_{n-3}+2^{n}-2^{n-1}-2^{n-2}-2^{n-3}.$$ But $2^{n}-2^{n-1}=2^{n-1}$ and $2^{n-1}-2^{n-2}=2^{n-2}$ and $2^{n-2}-2^{n-3}=2^{n-3}$. We conclude that $$F_n=F_{n-1}+F_{n-2}+F_{n-3}+2^{n-3}.$$

Solution 2:

You can also use the positive break-down. Consider the first bit as either 1 or 0. For one, there are no extra results and you get $a_{n-1}$. For 0, you get a bonus set of cases where the first 3 are zero, which occurs $2^{n-3}$ times. Repeating the process for the second and third digits - without adding cases already counted in $2^{n-3}$ - and you get the rest of the argument you were requested to prove.

You can also prove this by induction (Base case n=4)