Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow.

Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive 1s.

Here is my thought process/work, could someone please help me figure out where I'm going wrong?

Knowing that a bit string of length 0 or 1 cannot contain two consecutive bits of any kind, and that only one bit string of length 2 (the string 11) can contain two consecutive ones, I have the initial conditions a(0) = 0, a(1) = 0, and a(2) = 1. I'm now trying to find a formula for the term a(n+2).

I know there are three ways for a bit string of length n + 2 to have two consecutive 1s:

• Condition X: Both n + 1 and n + 2 are 1. count(X) = 2^n because this still leaves n bits unaccounted for.
• Condition Y: Both n and n + 1 are 1. count(Y) = 2^n for the same reason.
• Condition Z: The first n bits contain 11 somewhere. count(Z) = 4 * a(n) because adding 2 bits to the a(n) condition quadruples the number of possible strings.

Since these three conditions are not mutually exclusive,

a(n+2) count(X) + count(Y) + count(Z) - (count(X $\cup$ Y) + count(X $\cap$ Z) + count(Y $\cap$ Z)) + count($X \cap Y \cap Z)$

or

a(n+2) = 2^n + 2^n + 4 * a(n) - (2^(n-1) + a(n) + 2 * a(n-1)) + a(n-1)

This successfully proves the initial condition a(2) = 1 and the next one - a(3) = 3. But when I plug in 4, I get 9. Listing out the possible strings by hand and circling the ones that satisfy the condition gives only 8. What am I doing wrong?

Thanks.

Solution 1:

Here's an alternate way of solving your question.

Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $1$'s. In order to construct such a bit string, one could start with

• $0$ and follow with a string of length $(n-1)$ containing a pair of consecutive $1$'s
• $10$ and follow with a string of length $(n-2)$ containing a pair of consecutive $1$'s
• $11$ and follow with any string of length $(n-2)$

Since these three cases are mutually exclusive and exhaust the possibilities for how such a string might start, we can apply the sum rule and write down the following recurrence relation valid for all $n \ge 2;$

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

(Recall that there are $2^k$ bit strings on length $k$).

Now for the initial conditions:

• $a_0 = 0$
• $a_1 = 0$

Solution 2:

A perhaps less complicated way of solving the problem is to let $b_n$ be the number of length $n$ bit strings with no consecutive $1$'s. It is easy to show that $$b_{n+2}=b_{n+1}+b_n.$$ Since $b_k=2^k-a_k$, substitution and a little simplification give $$a_{n+2}=a_{n+1}+a_n+2^n.$$