Never mind. My colleague meant , not . Everything is clear now. And the formula I found for , while correct, is not the formula that helped me find the limit.
Instead, I needed a recursive formula. To find that, I count the number of binary sequences of length that do not contain the pattern 001. If the first digit is 1, then any binary sequence of length not containing the pattern 001 that follows will form a valid sequence of length . There are of those.
If the first digit is zero and the second digit is 1, then any valid binary sequence of length that follows will form a valid binary sequence of length . There are of those.
If the first two digits are zero, then the third digit cannot be 1 (or it would form the pattern 001). So, the third digit must be zero. By the same logic, every digit after must also be zero. There is only one binary sequence of length all of whose digits are zero.
So, the recursive formula is . Since , we also have .
This recursive relation has characteristic polynomial which has roots . So an explicit formula is:
There is one empty binary sequence, two binary sequences of length one, and four binary sequences of length two. Obviously, none of them contain the pattern 001.
This gives the system of equations:
Solving this system, . Hence,
Since , so as , . This implies the numerator and denominator both approach infinity, so I can apply L'Hospital's Rule. The derivative of the denominator is one, so it will be ignored:
Note: As since