What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's? 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.
 A: I would like to contribute an answer which is more of a dynamic programming approach.


*

*Let $a_i$ denote the number of bit-strings with length $i$ which end in $1$.  

*Let $b_i$ denote the number of bit-strings with length $i$ which end in $0$.
Now, we want a string with no two consecutive zeros.
So, for the string of length ($i+1$), we can append $0$ or $1$ to a string ending in $1$.
But we can append only $1$ to a string ending in $0$.
This creates the recurrence relation as follows:
\begin{cases} 
a_{i+1}& = a_{i}+b_{i}\\
b_{i+1}& = a_{i}
\end{cases} 
Base cases:
$a_1 = 1$, $b_1 = 1$. (String of length $1$: $0$ or $1$)  
$a_2 = a_1 + b_1 = 1 + 1 = 2$
$b_2 = a_1 = 1$
$a_3 = a_2 + b_2 = 3$
$b_3 = a_2 = 2$
Similarly,
$a_4 = $5, $b_4 = 3$
$a_5 = $8, $b_5 = 5$
$a_6 = $13, $b_6 = 8$
$a_7 = $21, $b_7 = 13$
$a_8 = $34, $b_8 = 21$     
Hence the total number of strings with no consecutive zeros is
$a_8 + b_8 = 34 + 21 = 55$.  
The total number of possibilities $=2^8=256$.
Total favourable cases $=256-55 = 201$.
Hence, probability $= 201/256$.
A: Let $C_n$ be the number of $n$ length bit strings that don't contain two consecutive zeros. If we have one of length $n+2$ satisfying this condition, then if the first bit is $1$, the rest must not have any consecutive zeros ($C_{n+1}$ possibilities). If it is $0$, then the second one is $1$ and the rest must satisfy that same condition ($C_{n}$). So $C_{n+2}=C_{n+1}+C_n$ ; $C_1=2$ ; $C_2=3$.
$$C_n=F_{n+1}$$
Where $(F_n)_{n\in \Bbb N}$ is the Fibonacci sequence
