Binary Combinations Less Repetition

Question

What would the formula be for finding the number of combinations of $n$ binary elements when no $0$ can follow another but there is no restriction on subsequent $1$s. For example, an allowable sequence is $(1,0,1,1,1,0,1,0,1,1)$ but a disallowed sequence is $(1,0,0,1,1,0,1,0,0,1)$. How many allowable sequences are there for length $n$?

I know if there were no restriction, then the answer would be $2^n$. But I want to know how to subtract the repeated zeros.

Answer 1

Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:

---

Reframing the problem: Define the substrings $\mathbf{A}_0, \mathbf{A}_1, \mathbf{A}_2, ...$ and $\mathbf{B}_1, \mathbf{B}_2, \mathbf{B}_3, ...$ by:

$$\begin{matrix} \mathbf{A}_0 = ( 0 ) \\[6pt] \mathbf{A}_1 = ( 1, 0 ) & & & & & \mathbf{B}_1 = ( 1 ) \\[6pt] \mathbf{A}_2 = ( 1, 1, 0 ) & & & & & \mathbf{B}_2 = ( 1, 1 ) \\[6pt] \vdots & & & & & \vdots \\[6pt] \mathbf{A}_n = ( \underbrace{1, 1, ..., 1}_{n \text{ times}}, 0 ) & & & & & \mathbf{B}_n = ( \underbrace{1, 1, ..., 1}_{n \text{ times}} ) \\[6pt] \vdots & & & & & \vdots \\[6pt] \end{matrix}$$

Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.

Answer 2

Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.

Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.

Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion $$a_n = a_{n - 1} + a_{n - 2}$$ Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_n & = a_{n - 1} + a_{n - 2} \end{align*} A familiar sequence will appear when you write out the first several terms.