Exponential/permutation combinatorics problem for leisure

Question

I've been trying to solve the problem below for over an hour doing everything but writing it out by hand. I've tried looking for patterns in strings of lengths $2, 3, 4,$ and $5$ which have probabilities $1/4, 3/8, 8/16,$ and $19/32$, respectively, of having two or more consecutive $1$s.

I'm more interested in the formula and theory behind solving the problem than the answer itself. I've searched online for permutation and probability problems without success.

Problem:

For the purposes of this puzzle, a "string" means a sequences of zeros and ones, e.g. $1011$.

Consider all the different strings of length eight — a good first step would be to figure out how many of these exist.

If you pick a length-eight string uniformly at random, what's the probability that it contains two (or more) consecutive 1s?

Problem is from the app below: https://play.google.com/store/apps/details?id=atorch.statspuzzles

Answer 1

Let's try to solve the opposite problem first: counting the number of bitstrings with no consecutive ones.

Let $A_n$ be the set of bit strings of length $n$ with no consecutive $1$'s and let $a_n = |A_n|$, i.e., $a_n$ is the number of bit strings of length $n$ with no consecutive $1$'s. Clearly, $a_1 = 2, a_2 = 3$.

Consider a bit string in $A_n$. Then it can be formed in the following ways:

1. $0$ followed by any bit string in $A_{n-1}$.
2. $10$ followed by any bit string in $A_{n-2}$.

Thus, it follows that: $$a_n = a_{n-1} + a_{n-2}.$$

Using standard techniques for solving recurrence relations, you should be able to find a formula for $a_n$. If we let $b_n$ be the number of bit strings that have consecutive $1$'s, then since there are a total of $2^n$ bitstrings of length $n$, then $a_n+b_n = 2^n \implies b_n = 2^n-a_n$. Thus, the probability of getting a bitstring with consecutive $1$'s is:

$$\frac{2^n-a_n}{2^n} = 1-\frac{a_n}{2^n}.$$