11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Dec 11 '13 at 21:45
  • $\begingroup$ 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. $\endgroup$ – Thomas Kalinowski Dec 11 '13 at 21:48
2
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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$
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user228113 May 9 '15 at 14:46
  • $\begingroup$ Hey, I fixed my error. Mind explaining what you mean by "re-align" my notation? $\endgroup$ – Kevin Zakka May 9 '15 at 14:51
  • 1
    $\begingroup$ 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. $\endgroup$ – user228113 May 9 '15 at 15:01
  • $\begingroup$ 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? $\endgroup$ – ELLIOTTCABLE Oct 21 '16 at 15:45
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.