# 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}$ – Random Excess Jul 28 '14 at 23:14
• ignore my nonsense above. Thanks. – Random Excess 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? – JoeyAndres 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. – Gerry Myerson 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 . – ashfaque Aug 23 '16 at 12:17