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

3 Answers 3

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$
    – user228113
    May 9, 2015 at 14:46
  • $\begingroup$ Hey, I fixed my error. Mind explaining what you mean by "re-align" my notation? $\endgroup$ 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$
    – user228113
    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$ 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.

Not the answer you're looking for? Browse other questions tagged .