Rosen-Advance Counting Technique-26

Question

Find a recurrence relation for the number of bit strings of length $n$ that contain the string $01.$

---

I am getting a recurrence like An = 2^(n-2) + 2A(n-1) - A (N-2) .Answer is not given for this question.Please help and explain your steps.

Answer 1

The strings in complement of A(n) can be of the form:  (4 bit strings assumed)

1111

1110

1100

1000

0000

Thus, A'(n) = n + 1

Thus, A(n) = 2ⁿ - (n+1)

Answer 2

In order to construct a bit string of length $n$, which contain $01$

$(1)$ we could start with $1$ and follow with a string length $n-1$ containing $01$

$(2)$ we could start with $0$ and follow with a string length $n-1$ containing $01$

$(3)$ we could start with $01$ and follow by any string length $n-2$

Therefore recurrence relation will be

$a_{n}=2a_{n-1}+2^{n-2}$