# 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.

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.

• The standard way is to find a recurrence for the number $b_n$ of bit strings that have no two consecutive $1$'s, then $a_n=2^n-b_n$. – André Nicolas Dec 11 '13 at 21:45
• In your approach, $count(Y\cap Z)$ looks wrong. For a direct approach you could count (1) the n-bit strings with two consecutive 1's that start with 0, (2) the n-bit strings with two consecutive 1's that start with 10, and (3) the n-bit strings with two consecutive 1's that start with 11. – Thomas Kalinowski Dec 11 '13 at 21:48

Your count of $Y \cap Z$ requires that the two $1$'s in $Z$ be in the first $n-1$ bits. For $n=4$ it does not include $001110$

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$
• The OP had "two consecutive $1$s", actually: you might want to re-align your notation. Also, the third should probably be "$00$ and follow with any string of length $(n-2)$". I could be wrong, so check it. – user228113 May 9 '15 at 14:46
• Hey, I fixed my error. Mind explaining what you mean by "re-align" my notation? – Kevin Zakka May 9 '15 at 14:51
• I meant "change it into the same as the OP". I probably should have said "align", but I'm not Paul Auster when it comes to English. – user228113 May 9 '15 at 15:01
• This doesn't seem to handle the case of $01$, followed by a string of length $(n-1)$ that starts with $1…$; which seems to be the crux of this problem, AFAICT? – ELLIOTTCABLE Oct 21 '16 at 15:45

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.$$