Question

Find a recurrence relation for the number of bit strings of length n that contain a pair of consecutive 0s. Find also the initial conditions?

Answer 1

Let $a_n$ represents the number of bit strings of length n that contain a pair of consecutive 0's.

a) First Case: The bit string is a sequence ending in 1, then the bit string of length n-1 (ignore the last 1) has $a_{n-1}$ possible strings that contain a pair of consecutive 0's.

Second case: The bit string is a sequence ending in 10, then the bit string of length n-2 (ignore the last two digit 10) has $a_{n-2}$ possible strings that contain a pair of consecutive 0's.

Third case: The bit string is a sequence ending in 00. There are $2^{n-2}$ bit strings of length n-2 and thus there are $2^{n-2}$ bit of string n-2 followed by 00.

Adding the number of sequences of all three cases, we then obtain:

$a_n = a_{n-1}+a_{n-2}+ 2^{n-2}$ .

b) When $n=0$, there are exactly 0 bit strings with a pair consecutive 0's (since the empty string does not contain a pair of consecutive zeros).

$a_0 = 0$.

When $n=1$, there are exactly 0 bit strings with a pair of consecutive 0's (since the string contains only 1 element).

So, $a_1 = 0$.

When $n=2$ , there is exactly 1 bit string with a pair consecutive 0's (namely the bit string 00). When we use the recurrence relation in part(a), we note that $a_2 = a_1+a_0 +2^{2-2} = 0 + 0 +1 = 1$. Thus the recurrence relation holds for $n=2$ and thus $n=2$ does not need to be an initial condition.