Practice Problems Sheet VIII

$($Recurrence Relations$)$

Q$1$

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

$3$ consecutive $0$s$.$ What are the initial conditions?

$($b$)$ Find a recurrence relation for the number of bit strings of length n that do not

contain $3$ consecutive $0$s$.$ What are the initial conditions?

$($c$)$ Using recurrences of parts $($a$)$ and $($b$)$ above calculate the number of bit strings

of length $7$ that do and do not contain $3$ consecutive $0$s$.$