Solution:

(a) Find the recurrence relation

Let $a_n$ represent the number of bit strings of length $n$ that contain the substring "01". The recurrence relation can be derived as follows:

1. Case 1: The string ends in "1".

   • The substring "01" can appear in any string of length $n-1$ that ends in "0". Thus, the count for this case is $a_{n-1}$.

2. Case 2: The string ends in "0".

   • The substring "01" can appear in any string of length $n-1$ that already contains "01". This is $a_{n-1}$.
   • Additionally, a "1" preceding this "0" forms "01". We subtract the number of strings that end in "00" (as they don’t contribute). The number of strings of length $n-2$ without "01" is $2^{n-2} - a_{n-2}$.

By combining these cases, we arrive at the recurrence relation: $a_n = 2a_{n-1} - (2^{n-2} - a_{n-2})$

Simplify: $a_n = 2a_{n-1} + a_{n-2} - 2^{n-2}.$

---

(b) What are the initial conditions?

For small values of $n$, we directly count the bit strings that contain "01":

• For $n = 2$: Only "01" satisfies the condition. So, $a_2 = 1$.
• For $n = 3$: The valid strings are "010", "011", "101", "110". So, $a_3 = 4$.

Initial conditions: $a_2 = 1, \quad a_3 = 4.$

---

(c) How many bit strings of length 7 contain the string "01"?

Using the recurrence relation $a_n = 2a_{n-1} + a_{n-2} - 2^{n-2}$, we compute $a_7$ step by step:

1. $a_2 = 1$
2. $a_3 = 4$
3. Compute $a_4$: $a_4 = 2a_3 + a_2 - 2^{4-2} = 2(4) + 1 - 4 = 9.$
4. Compute $a_5$: $a_5 = 2a_4 + a_3 - 2^{5-2} = 2(9) + 4 - 8 = 23.$
5. Compute $a_6$: $a_6 = 2a_5 + a_4 - 2^{6-2} = 2(23) + 9 - 16 = 55.$
6. Compute $a_7$: $a_7 = 2a_6 + a_5 - 2^{7-2} = 2(55) + 23 - 32 = 101.$

Thus, the number of bit strings of length 7 containing "01" is: $\boxed{101}.$

---

Follow-Up Questions:

1. How does the recurrence relation change for a substring other than "01"?
2. Can you generalize the formula for $a_n$ without using recurrence relations?
3. What is the total number of bit strings of length $n$ that do not contain "01"?
4. What happens to the recurrence relation if "01" must appear at least twice?
5. How would this problem change if we allow bit strings of infinite length?

Tip: Always start with small cases to verify the recurrence relation works for edge cases.