Number of bitstrings with $000$ as substring I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$?  Now there are many  ways to go about this but if I choose starting a $n-3$ bit string and append it with $000$ how would I show that?
 A: 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}.$$
A: 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)
