How many bit strings that begin with 1 and contain two consecutive 1s

Question

Find a recurrence relation for the number of bit strings of length n that contain two consecutive 1s and start with 1? The answer in my book is $a_{n} = a_{n-1} + a_{n-2} + 2^{(n-3)}$, however I am not sure whether this is correct as well as didn't understand why they have this answer. I know how to find number of bit strings containing two consecutive 1s only. Can anyone explain for me? Thanks.

Answer 1

Let's call good a string that starts with $1$ and contains two consecutive ones.

To obtain a good string of length $n$ we can certainly take a good string of length $n-1$ and add a $1$ on the left.

We may as well take a good string of length $n-2$ and add $10$ on the left.

Note that there is no intersection between the strings obtained this way, but unfortunately we don't obtain all the possible strings. Which good strings aren't we counting?

Well, we are not counting the strings that start with $11$ and have no other consecutive ones and the good strings that start with $100$. Note that in the first case we may as well suppose the string start with $110$ because if it started with $111$ the second and third one would form a consecutive pair. It follows that we need all the sequences of $n-3$ bits that either contains no consecutive ones (for the first case) or contains consecutive ones (for the second case). The total sum is clearly $2^{n-3}$ and by adding everything together you obtain the result.

Edit: The partition is the following:

1. Strings starting with $11$ that have at least another pair of consecutive ones. Note that all the string starting with $111$ are here;

2. Strings starting with $101$ that have a pair of consecutive ones;

3. Strings starting with $110$ that have no other pairs of consecutives ones;

4. Strings starting with $100$ that have a pair of consecutive ones.

These subsets cover the set of the good strings and have no intersection, so they are indeed a partition. Now we count the cardinality:

1. The first set is in correspondence with the good strings of length $n-1$. The correspondence is given by adding/eliminating a $1$ on the left side. It's cardinality is $a_{n-1}$;

2. The second set is in correspondence with the good strings of length $n-2$. The correspondence is given by adding/eliminating a $10$ on the left side. It's cardinality is $a_{n-2}$;

3. The third set is in correspondence with the strings of length $n-3$ that contain no pair of consecutive ones. The correspondence is given by adding/eliminating a $110$ on the left side

4. The fourth set is in correspondence with the strings of length $n-3$ that contain at least a pair of consecutive ones. The correspondence is given by adding/eliminating a $100$ on the left side.

Note that the union of the third and fourth set correspond to all the string of length $n-3$. The correspondence is given by adding $110$ on the left if the string contains no pair of consecutive ones and $100$ otherwise. It follows that the total cardinality of the third and fourth set is $2^{n-3}$.