Let f(n) be the number of bit strings of length n that contain three consecutive 0's. Note: a string that contains four or more consecutive 0's is also considered to contain three consecutive 0's. We want to define f(n) recursively. we consider n >= 5. We want to express f(n) recursively in terms of f(n-1); f(n-2),...... Here are some hints: (Step 1) If x is a bit string of length n-1 that contains three consecutive 0's, then extending it by a bit 0 or bit 1 will give rise to a string of length n that again contains three consecutive 0's. (Step 2) Consider a bit string x of length n that contains three consecutive 0's, but is not derived by Step 1. Next, answers the following two questions about such string x.

Q1.What can you say about the first n - 4 bits of x? Why can't the first n-4 bits of x contain three consecutive 0's? How many different such prefixes of x with length n - 4 could there be?