Here I have an example question. I'm not asking the actual question but the logic behind it.
Find a recurrence relation for the number of bit strings of length n that contain the string 01
In such questions we start from -for example- the case that string has the length of n-2. And adding up 0's or 1's. Does it matter to add these substrings to front or end of the the string of length n-2 to cover all the possible cases ?
The basic idea is that as soon as we have a zero anywhere in the string, the only thing we can put after it is another zero, we can always add a zero to the end of any valid string, and any sting of ones is a valid string.