Exercise $1(15$ points$)$

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

b$)$ What are the initial conditions?

c$)$ How many bit strings of length seven contain the string $01?$

d$)$ Solve this recurrence relation.