edited by
527 views
1 votes
1 votes

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.

edited by

2 Answers

2 votes
2 votes

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) = 2n - (n+1)

0 votes
0 votes
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}$

Related questions

0 votes
0 votes
2 answers
1
3 votes
3 votes
1 answer
2
Mk Utkarsh asked Mar 7, 2019
518 views
Find the generating function for the sequence $\left \{ a_n \right \} where $$a_n = \Large \binom{10}{n+1} $ for n = 0,1,2,….Sol. $\Large \binom{10}{1} + \binom{10}{2...
1 votes
1 votes
0 answers
3
Pineapple asked Mar 23, 2023
259 views
How many ways are there to distribute five distinguishable objects into three indistinguishable boxes?
1 votes
1 votes
0 answers
4
Aboveallplayer asked Jan 1, 2017
302 views
How to solve this equationan+2-5an+1+6an=2 where a0=1 and a1=2i know how to solve if it is 0 in RHS, but how to take care of this 2?