I have trouble figuring out these types of problems. Could someone help me out, with the different ways to answer it?
How many bit strings of length six contain three consecutive 1’s?
P.S i thought this recurance relation would be an-1+1 but that is counting out a lot of different factors
You mentioned the possibility of finding a recurrence; that can be done. Call a bit string that has at least one string of $3$ or more consecutive $1$s a good string; a string that isn’t good is bad.
Consider a good bit string $\sigma$ of length $n$, where $n\ge 3$. If the substring consisting of the first $n-1$ bits of $\sigma$ is good, the $n$-th bit can be either $0$ or $1$, so there are $2a_{n-1}$ good bit strings of length $n$ of this type. If the substring consisting of the first $n-1$ bits is bad, the last $4$ bits of $\sigma$ must be $1110$, and the substring consisting of the first $n-4$ bits of $\sigma$ can be any bad string of length $n-4$. There are $2^{n-4}$ bit strings of length $n-4$, $a_{n-4}$ of which are good, so there are $2^{n-4}-a_{n-4}$ bad strings of length $n-4$. Appending $1110$ to each of them produces the $2^{n-4}-a_{n-4}$ good strings of length $n$ whose first $n-1$ bits are a bad string. Altogether, then, $$a_n=2a_{n-1}+2^{n-4}-a_{n-4}\;.\tag{1}$$
Clearly $a_0=a_1=a_2=0$ and $a_3=1$. Applying $(1)$ three times, we find that
$$\begin{align*} a_4&=2\cdot1+2^0-0=3\;,\\ a_5&=2\cdot3+2^1-0=8\,\text{ and}\\ a_6&=2\cdot8+2^2-0=20\;. \end{align*}$$
It’s easier to find $a_6$ directly, as André Nicolas did in his answer, but if you wanted many more terms of the sequence, the recurrence would be the way to go.
We interpret three consecutive $1$'s as meaning at least three.
The string of at least three consecutive $1$'s could begin at the left end. Then the last three can be filled in $2^3$ ways.
The string could begin in the second position. So there is an initial $0$, then three consecutive $1$'s. The rest can be filled in $2^2$ ways.
The string could begin in the third position. So the first entry can be chosen in $2$ ways, then we must have a $0$, then three consecutive $1$'s, with $2$ choices for the last bit, for a total of $2^2$.
Finally, the string could start at position $4$, so a $0$ in position $3$, and the first $2$ entries arbitrary, for a total of $2^2$.
