# Find the recurrence relation for the number of bit strings that contain the string $01$.

Question:
Find the recurrence relation for the number of bit strings that contain the string $01$.

Attempt:
Since $01$ can appear in a lot of places, I focused on instances without $01$ first.

Bit strings without $01$ in a bit string of length $n$. Let $XX\dots X$ be bit string without $01$:

• $XX\dots X0$
• $1XX\dots X$

Thus we know we acquire twice more bit string without $01$ from length of $n-1$ to $n$. Let $a_n$ be the count of bit strings without $01$ at length $n$, recurrence relation of this is the following:

$$a_n = 2a_{n-1}, a_2 = 1$$

The inverse of this is then the recurrence relation with $01$. Let $P_n$ be the recurrence relationship of the number of bit string with length $n$ with $01$, thus,

$$P_n = 2^n - a_n = 2^n - 2a_{n-1}, a_2 = 1$$

Since $P_n = 2^n - a_n$, then, $a_n = 2^n - P_n$, thus

$$P_n = 2^n - 2*(2^{n-1} - P_{n-1})$$ $$\iff P_n = 2^n - 2^n + 2P_{n-1}$$ $$P_n = 2P_{n-1}, P_2 = 1$$

Problem:
I've also played around with the n-combination to solve this. The format of a bit string without $01$ is the following,

$$1\dots10\dots0$$

Adding $0$ or $1$ to either side adds a $01$, thus we can only add either $1$ on the left and $0$ on the right. Another way to view this is,

$1^p0^q, p, q \geq 1$

The number of bit strings without $01$ is for a bit string of length $n$,

$${2 + n - 2 - 1\choose n-2} = \\ {n-1 \choose 1} = \\ n-1$$

The inverse of this is,

$$2^n - n+1$$

Which is the number of bit string with $01$ at length $n$.

If we solve the recurrence relation above for $P_n$,

$$P_3 = 2P_2 = 2$$ $$P_4 = 2*2\\ \vdots\\ P_n = 2^{n-2}$$

Which is inconsistent with the $n$-combination solution to solve this. Where did I get it wrong??

• starting with n = 2 there is exactly 1 string containing 01. Then for any n > 1 denote the number of such strings as $a_{n}$ then the number without 01 will be $2^n - a_{n}$ and half of them will end in a zero. When looking at $a_{n+1}$ you will have the $2a_{n}$ strings with initial segments from the length $n$ strings plus you will have the initial strings without a 01 that ended in a 0 now with a 1 tacked on. That is recurrence relation should be $a_{n+1} = \frac{3}{2}a_{n} + 2^{n-1}$ Jul 28 '14 at 23:14
• ignore my nonsense above. Thanks. Jul 28 '14 at 23:22

Where did I get it wrong??

The number of bit-strings of length $n$ without 01 is: $n+1$. (Not $n-1$.)

You have the pattern $\underbrace{1\cdots 1}_{k}\underbrace{0\cdots 0}_{n-k}$, where the number of 1 bits, $k$, can range from $0$ to $n$.

Thus the number of $n$ length bit-strings with at least 1 substring of 01 is: $2^n-n-1$.

Thus we know we acquire twice more bit string without 01 from length of $n−1$ to $n$.

Let $a_n$ be the count of bit strings without 01 at length n , recurrence relation of this is the following:

$$a_n =2a_{n−1} ,a_2 =1$$

You are over counting. Adding 0 to the end of 110 gives the same result as adding 1 to the start of 100: namely 1100. Just count the ways to add 0 or 1 to the end of the strings and remain valid. You can viably add 0 to every valid $n-1$ length string; but there is only one viable target to which you can add 1 (the one with all 1s).

Also there are three string of length 2 which do not contain 01: namely 00, 10, 11.

$$a_n = a_{n-1}+1, a_2=3$$

Thus the valid 3-length strings are: 000, 100, 110, and 111. $a_n=4$ as expected.

(Always test your logic on the simplest examples. )

The inverse of this is then the recurrence relation with 01 . Let $P_n$ be the recurrence relationship of the number of bit string with length $n$ with 01 , thus,

Applying the correct formula: \begin{align} P_n & = 2^n - a_{n} \\ & = 2\cdot 2^{n-1} - (a_{n-1} + 1) \\ & = P_{n-1} + 2^{n-1} - 1 \\[2ex] P_2 & = 1 & 2^2-3 \\P_3 & = 1+4-1 = 4 & 2^3-4 \\P_4 & = 4+8-1 = 11 & 2^4 - 5 \\ \text{et cetera} \end{align}

• The solution to my recurrence relation is $P_n = 2^{n-2}$, I don't think that equals $2^n - n - 1$. Do you know what's wrong with my recurrence relation? Jul 28 '14 at 23:14
• For one thing, Joey, you write $a_2=1$, when in fact there are 3 strings of length 2 without 01. Now write down the three strings of length 2, and do your construction on them to get strings of length 3, and see what you miss. Jul 29 '14 at 0:25

Every following "form" is a $$n$$ bit string.

Bit strings of the form ....$$\_$$ $$\_0$$ contributes $$a_{n-1}$$ to the total count.

Bit strings of the form ....$$\_$$ $$\_01$$ contributes $$2^{n-2}$$ to the total count.

Bit strings of the form ....$$\_$$ $$\_011$$ contributes $$2^{n-3}$$ to the total count.

$$\vdots$$

Bit strings of the form $$011...1$$ contributes $$2^{n-n}$$ to the total count.

Bit strings of the form $$111...1$$ contributes nothing to the total count.

All the bit strings of length $$n$$ have been considered.

Therefore, $$a_{n}= a_{n-1}+2^{n-2}+2^{n-3}+...+2^{n-n}$$

applying sum of G.P,we get,

## $$a_{n}= a_{n-1}+2^{n-1}-1$$

I believe the problem with your recurrence relation is that you are overcounting the $a_n$.

For example, the strings of length 3 without 01 are 111, 000, 100, and 110;

but there are only 5 strings of length 4 without 01: 1111, 0000, 1000, 1100, and 1110.

Notice that 1|110 gives the same result as 111|0, so the string 1110 is getting counted twice in your recurrence relation.

If we let $d_n$ be the number of bit strings of length n with 01, $e_n$ be the number of such bit strings ending with 0, and $f_n$ be the number of such strings ending in 1, then

$d_n=e_n+f_n$, $e_n=d_{n-1}$, and $f_n=d_{n-1}+2^{n-2}-e_{n-1}$,

(since a string of length n containing 01 and ending in 1 either has 01 in the first n-1 bits, has any bits in the first n-2 places and a 0 in the n-1 spot, or satisfies both conditions).

This should yield a recurrence relation for $d_n$.

Case 1: starts with $1$ followed by strings of length $n-1$ containing $01$

Case 2: starts with $01$ followed by any string of length $n-2$, for which there are $2^{n-2}$ possibilities.

So we have $a_n = 2^{n-2} + a_{n-1}$ for $n\ge 2$.

• There are bit strings that would start with 001, 0001,... and so on. The two cases you gave are not exhaustive .. the recurrence relation would then be given by a_{n}= a_{n-1}+2^{n-2}+2^{n-3}+...+2^{n-n} a_{n}= a_{n-1}+2^{n-1}-1 . Aug 23 '16 at 12:17