Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$, not containing $2$ consecutive $0$'s. I've determined the total number of possible bit strings of length $8$ with $2^8$, but after that I become confused as to what approach I should take.
I've counted the number of strings that contain $2$ consecutive $0$'s at every position in the string ex:
$$00111111\\
10011111\\
11001111\\
11100111\\
11110011\\
11111001\\
11111100$$
But I'm not sure how to count the bit strings left that are NOT all $1$'s in every other position, because I'm basically just counting how many are bitstrings of length $6$ do not contain $2$ consecutive $0$'s. This has led me to the conclusion that I likely need to utilize a recurrence relation, but I am unsure of how to proceed from here.
Any help is much appreciated, thanks.
Best Answer
As Farnight and Andre noted, the number of sequences which don't contain consecutive zeroes will turn out to be Fibonacci numbers. Here is an alternate approach which yields a nice combinatorial identity for Fibonacci numbers.
Suppose we are looking at length $n$ binary sequences of $0$'s and $1$'s. Instead of thinking of it as $0$'s and $1$'s however, imagine it as $[\color{blue}{01}]$'s and $\color{red}{1}$'s with a possible $0$ at the far right. In other words, imagine we glued a 1 to the right of every 0 in order to forcibly avoid having two 0's in a row.
Either the furthest right entry in the sequence will be a 1 or a 0.
There can be anywhere from zero to $\lfloor\frac{n}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ be the number of $[\color{blue}{01}]$'s. Then there are $n-2k$ copies of $\color{red}{1}$'s to place. Thus, for a specific $k$, we have a total of $k+n-2k=n-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-k}{k}$. Ranging over all possible $k$, we find that there are $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}$ possible sequences in the first case.
There can be anywhere from zero to $\lfloor\frac{n-1}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ again be the total number of $[\color{blue}{01}]$'s. Then there are $n-1-2k$ copies of $\color{red}{1}$'s to place. Thus for a specific $k$, we have a total of $k+n-1-2k=n-1-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-1-k}{k}$ possibilities. Ranging over all $k$, we find there are $\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$ sequences in the second case.
Thus combining the cases, we have a total of $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$.
Noting that this answers the same question in a different form than the other answers, it gives us the identity for $n\geq 0$:
$F_{n+2} = \sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$
For your specific example of length 8 binary sequences, my form gives:
$$\sum\limits_{k=0}^{\lfloor\frac{8}{2}\rfloor}\binom{8-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{8-1}{2}\rfloor}\binom{8-1-k}{k}\\ =\sum\limits_{k=0}^{4}\binom{8-k}{k}+\sum\limits_{k=0}^{3}\binom{7-k}{k}\\ =\binom{8}{0}+\binom{7}{1}+\binom{6}{2}+\binom{5}{3}+\binom{4}{4}+\binom{7}{0}+\binom{6}{1}+\binom{5}{2}+\binom{4}{3}\\ =1+7+15+10+1+1+6+10+4= 55$$
and $55$ is the $10^{th}$ Fibonacci number.
(note also, I count the Fibonacci sequence with $F_0=0, F_1=1, F_2=1,F_3=2,\dots$ whereas it seems Farnight above me counts $F_0=1,F_1=1,F_2=2,\dots$.)
A much cleaner approach which yields the same answer:
In a binary sequence of length $n$ without, there will be between $0$ and $\lfloor\frac{n}{2}\rfloor$ zeroes. Supposing that there are $k$ zeroes, then there are $n-k$ ones. Set up $n-k$ ones on a line. There are then $n-k+1$ spaces between or to the far left or right of the ones in which a zero may be placed. Pick $k$ of them to be occupied with a zero.
Ranging over all values of $k$, you get $\sum\limits_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n-k+1}{2}$, which again equals the same as the other answers. For $n=8$ you have $\sum\limits_{k=0}^4\binom{9-k}{k}=\binom{9}{0}+\binom{8}{1}+\binom{7}{2}+\binom{6}{3}+\binom{5}{4} = 1+8+21+20+5 = 55$
Of course, to complete the problem, note the numbers and formulae we came up with were counting how many sequences did not have consecutive zeroes. To count how many sequences do have consecutive zeroes, apply inclusion-exclusion. There are $2^n$ different length-$n$ binary sequences, so there are $2^n-F_{n+2}$ sequences which do have consecutive zeroes (or depending on how you define the starting values for the Fibonacci sequence, $2^n-F_{n+1}$). In our current example, there are then $2^8-55=256-55=201$.
To find the probability, take that number and divide by the size of the sample space, in our case $2^n$. Hence the probability for our example is $\frac{201}{256}$.