Kenneth Rosen Edition 7 Exercise 8.1 Question 10 (Page No. 511)

Question

• A.  Find a recurrence relation for the number of bit strings of length $n$ that contain the string $01$.
• B. What are the initial conditions?
• C. How many bit strings of length seven contain the string $01?$

Answer 1

$\begin{align*} &\text{Lets us assume, } \\ \\ &A(n) = \text{Number of strings ends with 1 and has 01 substring} \\ &B(n) = \text{Number of strings ends with 0 and has 01 substring} \\ &\text{and let us call the strings satisfying the property as valid strings.} \\ \\ & \text{We can see that } B(n) = F(n-1) \quad \text{ For } B(n) \text{, We can not get more number of strings} \\ \\ &A(n) = \left [\text{All strings of length }(n - 2) \right ].01 \quad + \\ &\quad \left [\text{All the valid strings of length }(n - 1) \text{ that ends with 1} \right ].1 \\ \\ &A(n) = 2^{n-2} + A(n-1) \\ &A(n) = 2^{n-2} + 2^{n-3} + A(n-2) \\ & ....... \\ &A(n) = 2^{n-2} + 2^{n-3} + .... + 2^{n - (n-1+1)} + A(n - (n-1)) \\ &A(n) = 2^{n-1} - 1 \\ \\ &\Rightarrow F(n) = 2^{n-1} - 1 + F(n-1) \\ \\ &\text{Initial condition, } F(1) = 0 \quad \text{ because valid strings are of atleast length 2} \\ \end{align*}$