13
$\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$
3
  • 1
    $\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$ Commented Dec 11, 2013 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$ Commented Dec 11, 2013 at 21:48
  • $\begingroup$ This is in oeis.org/A008466, where the recurrence is in a formula. $\endgroup$ Commented Feb 10, 2022 at 13:27

3 Answers 3

Reset to default
8
$\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$
4
  • $\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$ Commented May 9, 2015 at 14:46
  • $\begingroup$ Hey, I fixed my error. Mind explaining what you mean by "re-align" my notation? $\endgroup$ Commented May 9, 2015 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$ Commented May 9, 2015 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$ Commented Oct 21, 2016 at 15:45
4
$\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$
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.