Rosen 7e Exercise-8.1 Question no-10 Page no-511

Question

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

Comments

https://math.stackexchange.com/questions/881005/find-the-recurrence-relation-for-the-number-of-bit-strings-that-contain-the-stri

this might be helpful

---

I couldn't understand that solution

Answer 1

Two types of equation are needed to get a confirmed answer

Though taking  $01$ means, we have got those string which have some substring with $01.$

but actually that will give a huge number of strings

So, at first we try, the string that donot have substring $01.$

Say string can be $1XXX...XXXX$ or $XXX....XXXX0$, that means start with $1$ and end with $0.$

What is recurrence relation for it?

Here ans. will be $a_{n}=a_{n-1}+1$

Now take some example and check

$a_{2}=a_{1}+1=3$ because $a_{1}=2$ either $0$ or $1.$

$a_{3}=a_{2}+1=4$ and those are $000,100,110,111$

Now, take it's converse how many string that not containing $a_{n}$

Say it is $P_{n}$

then $P_{n}=2^{n}-a_{n}$

Now derive it with proper answer

$P_{n}=2.2^{n-1}-(a_{n-1}+1)$

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

Now check $P_{n}=2^{n-1}+{\color{red}{2^{n-1}-a_{n-1}} }-1$

then $P_{n}=2^{n-1}+P_{n-1}-1$

So ans will be $P_{n}=P_{n-1}+2^{n-1}-1$

Hope it is clear now.

https://math.stackexchange.com/questions/881005/find-the-recurrence-relation-for-the-number-of-bit-strings-that-contain-the-stri

Answer 2

Suppose A(n) denotes the number of strings that have 01 as substring

then first symbol in string of length n may be 0 or 1.

If it is 1 then number of strings possible now is due to first symbol being 1 becomes A(n-1).

If it is 0 then two cases may arise based on the second symbol in string.

case 1: if second symbol is 0 then number of strings possible now is due to first symbol being 0 and second also being 0  becomes A(n-2).

case 2 : If second symbol is 1 then desired substring has already occurs . so number of string possible due to this case is 2^(n-2)

so , required recurrence relation is

A(n) = A(n-1) + A(n-2) + 2^(n-2).

Comments

this is wrong method  – A(n) = A(n-1) + A(n-2) + 2^(n-2).