# (Alternate Answer To) How Many Binary Strings Of At most Length $6$ have no consecutive zeros

This question is giving me a lot of trouble. It's taking a very long time to solve.

My Work

I'll find how many strings have consecutive zeros and then deduct that from the total amount of strings

Case I: The Length of String is $1$

$0$ of these strings have consecutive $0$

Case II: The Length of String is $2$

$1$ string $00$ has consecutive $0$s

Case III: The Length of String is $3$

The string must contain at least $2$ zeros to have consecutive zeros. There are $2$ strings comprised of $1,0,0$ with consecutive zeros. There is one string comprised of $0,0,0$ that will have consecutive zeros. 3 strings.

Case IV: The Length of String is $4$

When there are two zeros and two 1s there are 3 consecutive strings. When there are 3 zeros and one 1s there must be 4 arrangements with consecutive zeros. When there are 4 zeros there are obviously 1 arrangement with 0. $3+4+1 = 8$ strings with consecutive zeros

Case V: The Length of String is $5$

2 0s and 3 1s. There are 4 strings with consecutive zeros. 3 0s and 2 1s there are 9 strings with consecutive zeros. 4 0s there are 5 strings with consecutive zeros. 5 zeros there is one string with consecutive zeros. $4+9+5+1 = 19$ strings with consecutive zeros.

Case VI: The Length of String is $6$

2 zeros there are 5 strings with consecutive zeros. 3 zeros there are 20 strings with consecutive zeros. 4 zeros and two 1s 15 total strings with consecutive zeros. 5 zeros means there are 6 strings with consecutive zeros. Six zeros means there is 1 string with consecutive zeros. $5+20+15+6+1 = 47$ strings with consecutive 0s.

$2^1+2^2+2^3+2^4+2^5+2^6 = 126$

$0+1+3+8+19+47 = 78$

Total Number of Strings Without Consecutive Zeros = 126-78 = 48

My Question:

Is my answer correct and is there a better way to do this question?

• Length $6$ is much too large, there are only $64$ strings. I would count the empty string, but that's a matter of taste. The numbers with no consecutive $0$'s are Fibonacci numbers. – André Nicolas Jan 10 '15 at 2:35
• @AndréNicolas thanks for the catch. I've edited my answer accordingly. What do you mean they're the Fibonacci Numbers? – Dunka Jan 10 '15 at 2:40
• The answer by Brian M. Scott explains everything. By the way, it is $43$ not $47$ ($64-21$). – André Nicolas Jan 10 '15 at 2:42
• This question is good, will help me prepare for an upcoming quiz today in MACM 201. – Belphegor Jan 14 '15 at 19:57

Look at the numbers of strings of each length without consecutive zeroes:

$$\begin{array}{rcc} \text{Length:}&0&1&2&3&4&5&6\\ \text{Nr. of strings:}&1&2&3&5&8&13&21 \end{array}\tag{1}$$

That bottom row should look familiar: it’s the Fibonacci numbers. Even if you don’t spot that, you should notice that each number is the sum of the previous two. A little thought reveals the reason. Consider the strings of length $n$ without consecutive zeroes. The ones that end in $1$ can all be obtained by adding a $1$ on the end of an allowable string of length $n-1$, and the ones that end in $0$ can all be obtained by adding $10$ to the end of an allowable string of length $n-2$. Thus, if $a_n$ is the number of strings of length $n$ without consecutive zeroes, we have $a_n=a_{n-1}+a_{n-2}$, the same rule that gives the Fibonacci numbers; only the starting point is different. (In fact, $a_n=F_{n+2}$.)

If you see all of this, you can easily write down the bottom row of $(1)$ and add up the entries to get $53$. However, unless you’ve already had a fair bit of experience, it may very well be just as fast to use your approach (though your number for $n=6$ is off).

• By using $\sum_0^m F_k=F_{m+2}-1$ we can show that our number is $F_{10}-2$. – André Nicolas Jan 10 '15 at 3:21
• @André: I was debating whether to mention that. Now I don’t have to debate any more! – Brian M. Scott Jan 10 '15 at 3:22
• Probably you were right, overkill. – André Nicolas Jan 10 '15 at 3:31

A book by Sedgewick and Flajolet, An Introduction to the Analysis of Algorithms, shows a way to count the number of binary strings without consecutive zeros.

Let $\mathcal G$ be a class of binary strings with no two consecutive 0 bits. This kind of a string can either be empty (represented as $\epsilon$), a single 0 bit ($\mathcal{Z}_0$) or a single 1 bit ($\mathcal{Z}_1$) or 01 followed by a string with no two consecutive 0 bits.

This can be symbolically written as $$\mathcal{G} = \epsilon + \mathcal{Z}_0 + (\mathcal{Z}_1 + \mathcal{Z}_0 \times \mathcal{Z}_1) \mathcal{G}$$ and by using the generating functions that enumerate these classes (1 for $\epsilon$ and z for $\mathcal Z$) and the rules for their combination ($A(z) + B(z)$ enumerates $\mathcal A + \mathcal B$ and $A(z)B(z)$ enumerates $\mathcal A \times \mathcal B$) one gets an equation for the generating function $G(z)$ enumerating strings in the class $\mathcal G$ $$G(z) = 1 + z + (z + z^2) G(z) .$$ Solving for $G(z)$ gives $$G(z) = \frac{1 + z}{1 - z - z^2}$$ and by observing that the generating function for the Fibonacci sequence can be written as $$F(z) = \frac{z}{1-z-z^2}$$ one can see that the answer (number of binary strings of length $N$ without consecutive zeros) can be written in terms of the Fibonacci numbers $$G_N = F_N + F_{N+1} = F_{N+2} .$$

The answer to the original question is then $$\sum_{i=0}^6 G_i = \sum_{i=0}^6 F_{i+2} = F_2 + F_3 + F_4 + F_5 + F_6 + F_7 + F_8$$ $$= F_4 + F_6 + 2F_8 = 3 + 8 + 2*21 = 53.$$