Find a recursive formula for the number of n bit binary strings
that contain the substring 10. How many such strings of length
8 exist? Find a closed form for the number of n bit binary
strings that contain the substring 10.
i know i have to count the bits that need to be 10 but after that i dont know where to go from there from the 10 point of the bits iv gotten 1, 4, 11
Best Answer
Say that a string is good if it contains the substring $10$, and let $a_n$ be the number of good strings of length $n$. There are two ways to get a good string of length $n+1$.
We can start with a good string of length $n$ and append either a $0$ or a $1$; this produces $2a_n$ good strings of length $n+1$, two for each good string of length $n$.
We can append a $0$ to a bad string of length $n$ that ends in $1$. To see how many good strings of length $n+1$ are of this form, we need to count the bad strings of length $n$ that end in $1$. Show that such a string must be of the form $0^k1^{n-k}$, where $0\le k<n$, then count those strings.
You should find that you have a recurrence of the form $a_{n+1}=2a_n+f(n)$ for some simple function $f$. You’ve probably learned some techniques for finding closed forms for such recurrences; if not, or if you’re not sure of them, you might find my answer to this question helpful.
Finally, you can get $a_8$ either by working up through the recurrence — it’s only four steps, since you already know that $a_4=11$ — or from the closed form, once you have it.